Delphi в Internet

• 28Jul

  Поиск в строках. Наивный алгоритм на Delphi

  Основы Delphi
  Эта статья будет полезна в первую очередь тем, кто часто имеет дело со сравнением и анализом строковых переменных. Также, думаю, что этот алгоритм смогут использовать в своей работе и люди, занимающиеся парсингом.

  Цель: найти в двух строках самую длинную повторяющуюся подстроку.

  ' '
  

  Для решения подобной задачи было разработано достаточно алгоритмов, каждый из которых имеет свои преимущества и недостатки. На мой взгляд, самым простым и эффективным является так называемый “наивный алгоритм”.

  1. Суть наивного алгоритма

  Алгоритм основан на матрице совпадений M размерности n х n. Элементы этой матрицы определяются следующим образом:

  

  Такая матрица симметрична относительно главной диагонали. Поэтому надо вычислить только элементы над ней или под ней. Диагонали из смежных ‘1’, за исключением главной, представляют повторения в строке y, там-то и нужно искать максимальные повторяющиеся подстроки. Вот пример матрицы совпадений для строки PABCQRABCSABTU.

  	j	1	2	3	4	5	6	7	8	9	10	11	12	13	14
  i		P	A	B	C	Q	R	A	B	C	S	A	B	T	U
  1	P	1	0	0	0	0	0	0	0	0	0	0	0	0	0
  2	A	0	1	0	0	0	0	1	0	0	0	1	0	0	0
  3	B	0	0	1	0	0	0	0	1	0	0	0	1	0	0
  4	C	0	0	0	1	0	0	0	0	1	0	0	0	0	0
  5	Q	0	0	0	0	1	0	0	0	0	0	0	0	0	0
  6	R	0	0	0	0	0	1	0	0	0	0	0	0	0	0
  7	A	0	1	0	0	0	0	1	0	0	0	1	0	0	0
  8	B	0	0	1	0	0	0	0	1	0	0	0	1	0	0
  9	C	0	0	0	1	0	0	0	0	1	0	0	0	0	0
  10	S	0	0	0	0	0	0	0	0	0	1	0	0	0	0
  11	A	0	1	0	0	0	0	1	0	0	0	1	0	0	0
  12	B	0	0	1	0	0	0	0	1	0	0	0	1	0	0
  13	T	0	0	0	0	0	0	0	0	0	0	0	0	1	0
  14	U	0	0	0	0	0	0	0	0	0	0	0	0	0	0

  Из приведенной выше матрицы можно видеть, что максимальными повторяющимися подстроками в данном примере являются ABC, с вхождениями y(2, 4) и y(7, 9), и AB, с вхождениями y(2, 3), y(7, 8) и y(11, 12). Легко выбрать более длинную из них, а именно, ABC.

  Как уже упоминалось, поскольку матрица симметрична, достаточно вычислить элементы над главной диагональю, M(1…n-1,i+1…n), то есть всего n(n-1)/2 элементов. Таким образом, оценивание матрицы требует времени, пропорционального O(n²).

  Уяснив для себя общие черты алгоритма, можно смело приступать к программированию. Я, не долго заморачиваясь, написал небольшую программку на Delphi, которая демонстрирует работу наивного алгоритма.

  2. Наивный алгоритм в действии

  Запускаем Delphi, создаем новый проект и укладываем на форму 2 Edit’а, 1 кнопку и 1 label. Должно получиться примерно следующее:

  

  главная форма приложения

  В Edit’ы будем вписывать анализируемые стоки и выводить в Label результат сравнения. Функция, реализующая работы наивного алгоритма выглядит следующим образом (с краткими комментариями):

  function TForm1.GetSequence(str1, str2: string): string;
  var i,j,max, max_i,max_j:integer;
  Matrix: array of array of integer;
  begin
  //устанавливаем размерность массива
  SetLength(Matrix, Length(str1));
  for I:=0 to length(Matrix)-1 do
  SetLength(Matrix[i],length(str2));
  //строим матрицу
  max:=0;
  for i:=0 to length(Matrix)-1 do
  for j:=0 to length(Matrix[i])-1 do
  begin
  if (i=0)or(j=0) then
  Matrix[i,j]:=0
  else
  if str1[i]<>str2[j] then
  Matrix[i,j]:=0
  else
  begin
  Matrix[i,j]:=Matrix[i-1,j-1]+1;
  if Matrix[i,j]>max then
  begin
  max:=Matrix[i,j];
  max_i:=i;
  max_j:=j;
  end;
  end;
  end;
  //Составляем строку по str1 i
  result:='';
  for I:=max_i-max+1 to max_i do
  Result:=result+str1[i];
  end;

  Как видите, все достаточно просто. Берем один динамический массив, устанавливаем его размеры и, применяя формулу, представленную вышезаполняем массив нулями и единицами. В последнем цикле прозодимся по элементам и выбираем необходимую подстроку.

  Результат работы программы представлен на рисунке:

  

  Результат работы наивного алгоритма

  Можно бесконечно долго совершенствовать алгоритмы поиска и анализа строк, но, на мой взгляд, наивный алгоритм наиболее подходящее решения для работы небольших программ. За сим откланиваюсь. Будут вопросы, пожелания – пишите :)

  Мой блог находят по следующим фразам

  • как работать без мышки в интернете
  • защита темы wordpress от воровства
  • программа для авторизации на сайте на дельфи
  • Ribbon Delphi
  • problem with check box in openoffice
  • Как получить заголовок ответа сервера Delphi

  ---------------------------
  Сколько раз сталкивался с ситуацией, когда человек говорил "Я ищу работу, но не могу никак найти. Что делать не знаю". Теперь знайте - просто оставьте свое резюме на KeyWork.ru и работодатели найдут Вас сами.
  ---------------------------

  Related posts:

  Автор Vlad в 5:10 am

  Метки: алгоритм, массив, матрица, наивный алгоритм, сравнение строк, строки

Ваш ответ