12. Строки

Программы выполняют самые разнообразные операции со строками. Строки можно сортировать, искать, анализировать. Распространенной задачей является формирование частотного словаря слов. Поиск повторяющихся подстрок лежит в основе многих архиваторов. Для выявления плагиатов находят длинные повторяющиеся подстроки в разных файлах. В данном разделе рассматриваются основные алгоритмы поиска заданной подстроки в тексте.

Многие задачи связаны с проблемой нахождения нужных слов в тексте. Современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов. Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня. Чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне.

В готовых подпрограммах далеко не всегда и не все написано лучшим образом. Во-первых, в стандартных функциях не обязательно используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте. Работа простейшего спам– фильтра, заключается в нахождении в тексте письма таких сочетаний слов, как ”работа с высокой оплатой” или "похудание за неделю”. Все вышесказанное говорит об актуальности проблемы, затрагиваемой в этом разделе.

Поставим сначала задачу в несколько упрощенном виде.

Поиск подстроки. Заданы две последовательности символов. Нужно определить все вхождения первой из них (назовем ее образец) во вторую (текст).

Ввод из файла INPUT.TXT. Первая строка файла является образцом и имеет длину от 1 до 255. Вторая строка является текстом и имеет длину от 1 до 210⁹.

Вывод в файл OUTPUT.TXT. Вывести через пробел последовательность номеров позиций в тексте, начиная с которых в него входит образец. Нумерация начинается с 1. Если вхождений нет, вывести No.

Пример

Ввод

AA

AAABAA

Вывод

1 2 5

Из условия ясно, что образец можно запомнить в массиве символов, а текст – нельзя. Однако сначала для удобства предположим, что и образец, и текст хранятся в массивах P и T соответственно. Пусть M – длина образца, N – длина текста (M ≤ N).

Иногда требуется найти только первое вхождение образца. Дополнительным условием может быть отсутствие пересечений находимых подстрок текста.

Самое очевидное решение – сравнить образец с каждой из подстрок длины M, начинающихся в позициях 1, 2, …, N – M + 1. Такой алгоритм носит название последовательного или прямого [9]. Общее количество сравнений символов оценивается величиной O(M(N-M+1)). При заданных размерностях трудоемкость алгоритма допустима, но с ростом M и N быстро растет. Большинство сравнений в действительности лишнее. Например, если в каком-то многомегабайтном файле будет искаться последовательность длиной 100 Кб, то придется ждать очень долго.

Алгоритм Рабина [9] представляет собой модификацию линейного алгоритма. Он основан на весьма простой идее. Вырежем "окошечко" размером M и будем двигать его по тексту. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по всем буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины M. Тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам. Ошибка: источник перёкрестной ссылки не найден

Этот алгоритм выполняет линейный проход по образцу (M шагов) и линейный проход по всему тексту (N шагов), стало быть, общее время работы есть O(M+N). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда время работы алгоритма линейно зависит от размера строки и текста, значит, программа работает быстро. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые ”напоминают” образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию Hash, которая должна:

• легко вычисляться;

• как можно лучше различать несовпадающие строки;

• Hash( T[i+1 , i+m] ) должна легко находиться по Hash( T[i , i+m-1]).

Во время поиска будем сравнивать Hash(P) с Hash(T[i, i+M-1]) для i от 1 до N-M+1 включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

Приведем пример удобной для вычисления функции. Заменим все буквы в тексте и образце их кодами, представляющими собой целые числа. Тогда удобной функцией является сумма кодов. При сдвиге "окошечка" нужно добавить новое число и вычесть "пропавшее".

Однако, проблема в том, что искомая строка может быть длинной. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими, и работать с ними будет также неудобно. Но какой интерес работать только с короткими строками? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы.

Выберем некоторое число C (желательно простое) и некоторое натуральное число X (X< C). Каждое слово длины M будем рассматривать как последовательность целых чисел, заменив буквы их кодами. Эти числа будем считать как коэффициенты многочлена степени M - 1. Вычислим значение этого многочлена по модулю С в точке X. Это и будет одна из функций семейства (для каждой пары C и X получается своя функция). Сдвиг "окошечка" на одну позицию соответствует вычитанию старшего члена, умножению на X и добавлению свободного члена.

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число C фиксировано, а S и T - два различных слова длины M. Тогда им соответствуют различные многочлены. Совпадение значений функции означает, что в точке X эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени M-1 и имеет не более M-1 корней. Таким образом, если M много меньше C, то случайному значению X мало шансов попасть в "неудачную" точку. Строго говоря, время работы всего алгоритма в целом, есть O(M+N+AMN), но значение константы A достаточно невелико, так что сложность работы почти линейная.

Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими предварительными трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются оптимальными, поэтому мы перейдём к следующему классу алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска.

Алгоритм Кнута – Морриса – Пратта (КМП) [3, 9, 10] более полно использует информацию, полученную во время сканирования (алгоритм последовательного поиска ее просто выбрасывает). После сдвига образца по тексту стоит вести сравнение посимвольно. Если не совпал первый символ, нет смысла переходить к следующему. Хотелось бы сдвигать образец так, чтобы обеспечить совпадение максимального числа начальных символов образца и подстроки из «окошка». Оказывается, это можно обеспечить путем предварительного исследования образца. Будем следовать описанию алгоритма в [3], объясняя некоторые этапы.

Пусть в i-й позиции текста отмечено несовпадение с текущим символом образца, а в предыдущих j позициях символы текста и образца совпадают. Иными словами, P_j+1 ≠ T_i, а P₁P₂. . . P_j = T_i-jT_i-j+1. . .T_i-1. На какое максимальное число позиций можно сдвинуть образец, не рискуя пропустить его вхождение в текст? Очевидно, нужно найти в позициях текста от i – j + 1 до i -1 максимальное совпадение с началом образца. Но поскольку текст в этих позициях совпадает с символами образца, то это эквивалентно нахождению самого длинного начала образца P₁P₂. . .P_k (1< k < j), которое повторяется в оставшейся части образца, т.е. P₁P₂. . .P_k = P_s+1P_s+2. . .P_s+k .

Если сдвинуть образец на s позиций, то мы обеспечим совпадение в позициях текста от i – j + s до i – j + s + k. Докажем, что полное совпадение может быть только в том случае, когда подстрока P₁P₂. . .P_k входит как в начало, так и в конец строки P₁P₂. . .P_j, т.е. s+k=j. Предположим обратное: после сдвига на s позиций образец полностью совпадает с подстрокой текста и s+k < j, как это показано на рисунке.

……

Ti-j .…...........

Ti-j+s ………... Ti-j+s+k …Ti-1

Ti…

P1P2…….....Ps

Ps+1. . .. Ps+k

Ps+k+1 … Pj

Pj+1…

P1. . ….. Pk

Pk+1 ….. Pj-s

Pj-s+1…

Итак, подстрока P₁P₂…P_k входит как в начало, так и в конец строки P₁P₂. . .P_j. Сдвинем образец сразу на j - k позиций. Поскольку k < j, первые k символов образца и текущего "окошка” совпадут. Это состояние показано на следующем рисунке.

……

Ti-j …………

Ti-j+s…………………… Ti-1

Ti…

P1P2………Ps

Ps+1. . ………………... Ps+k

Pj+1…

P1. . …………………… Pk

Pk+1…

Эти свойства образца можно рассчитать заранее. Если для каждой позиции j образца известна максимальная длина f(j) < j начала образца, совпадающая с концом строки P₁ P₂…P_j, то возможен сдвиг образца вперед на j - f(j) позиций без последующего возврата назад. Отсутствие возвращений в тексте позволяет не запоминать его в массиве.

Функция f(j) называется функцией возвратов. Она показывает, к какому символу P_f(j) нужно возвратиться в образце, когда P_j+1 ≠ T_i. Это эквивалентно сдвигу образца вправо относительно текста на j - f(j) позиций и следующему сравнению P_f(j) с T_i.

Как вычислять функцию возвратов? Очевидно, f(1)=0. Пусть вычислены f(1),…, f(j-1) и f(j-1) = k. Если P_j = P_k+1, то конец строки P₁P₂. . .P_j совпадает с ее началом длины k+1, поэтому f(j) = k+1. Если P_j ≠ P_k+1, то «следующим концом» строки может быть подстрока P₁P₂…P_f(k) P_f(k)+1, поскольку именно P₁P₂. . . P_f(k) является самым длинным концом P₁P₂. . .P_k образца, совпадающим с его началом. Если и эта строка не годится, то следующей подстрокой может быть P₁P₂. . .P_f(f(k))+1 и т. д. Таким образом, или будет найдено начало длины r, при котором P₁P₂. . .P_r является концом P₁P₂…P_j, и тогда f(j) = r, либо такого начала найдено не будет, и тогда f(j) = 0.

Приведем пример. В первой строке содержится текст, во второй – образец, в третьей значения функции возврата

a b a c a b a с a b c a b a c a b a b b

a b a c a b a b

0 0 1 0 1 2 3 2

Ниже представлена последовательность сдвигов. Слева показана разность j - f(j), определяющая величину сдвига, а справа – позиция образца, с которой будет продолжено последующее сравнение с текстом

a b a c a b a a b a b a b a c a b a b b

a b a c a b a b

7-3=4 a b a c a b a b позиция 4

3-1=2 a b a c a b a b позиция 2

1-0=1 a b a c a b a b позиция 1

3-1=2 a b a c a b a b позиция 2

3-1=2 a b a c a b a b позиция 2

Представим образец массивом символов P, функцию возвратов целочисленным массивом F и опишем ее вычисления в следующем фрагменте программы:

F[1]:=0;

For i:=2 to M do

begin

While (k>0) and (P[i]<>P[k+1]) do k:=F[k];

if P[i]=P[k+1] then k:=k+1;

F[i]:=k;

end;

F[i] ≤ F[i-1] – w(i) +1, то есть w(i) ≤ F[i-1] – F[i] + 1

Тогда после суммирования w(2) + w(3) +…+ w(M) ≤ M – 1. Общая трудоемкость построения функции возвратов составляет O(M).

Поиск подстроки можно реализовать следующей программой. В ней опущены некоторые технические детали, связанные с вводом и выводом данных.

Var

P: array[1..255] of char;

F: array[1..255] of integer;

C: char; {очередной символ текста}

pp: integer; {текущая позиция в образце}

tp: integer; {текущая позиция в тексте}

Fin, Fout: text; {входной и выходной файлы}

Begin

{ввод образца, построение массива F:

значений функции возвратов}

pp:=0;

tp:=0;

While not eof(Fin) do

Begin

tp:=tp+1;

Read(Fin,C); {очередной символ текста}

While (pp>0) and (P[pp+1]<>C) do

pp:=F[pp]; {следующее ‘начало-конец’}

if P[pp+1]=C then pp:=pp+1;

if pp = M then {совпал последний символ образца}

begin

Write(Fout,tp-M+1,' ');

{позиция первого символа}

pp:=F[pp];

{подготовка к поиску следующего вхождения}

end;

End;

End.

Алгоритм КМП обеспечивает во всех случаях линейную сложность, но не является самым эффективным алгоритмом.