4.5. Поиск подстрок

Одной из наиболее часто решаемых задач является поиск информации в текстовых файлах. С подобной задачей приходится сталкиваться в текстовых редакторах и в базах данных. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте. Поскольку объемы перерабатываемой информации велики, то большое значение имеет построение эффективных алгоритмов поиска в последовательных структурах. Эта задача известна как задача поиска подстрок.

Задачу поиска подстрок можно сформулировать следующим образом: во множестве всех фиксированной длины подстрок некоторой строки найти подстроку, совпадающую с определенным образцом-шаблоном. Конечно, имеется тривиальный алгоритм последовательного перебора всех подстрок, пока не будет найден объект поиска, но подобная стратегия приводит к алгоритму сложности , где- длина строки, в которой ведется поиск, а- длина строки – образца. С другой стороны понятно, что множество подстрок, в котором ведется поиск, организовано определенным образом, и при сравнении новой подстроки с шаблоном имеется возможность использовать информацию, полученную на предыдущих шагах поиска. Например, найдя подстроку babb и обнаружив несоответствие в четвертом символе (совпало только bab), алгоритм полного перебора начнет сравнивать образец, начиная со следующего символа текста (с подстрокойabb…), хотя видно, что этого не надо делать. Кроме того, следует отметить, что очень часто в поиске образец описан неточно (необходимо уметь найти вариант из множества возможных претендентов). Сформулируем задачу более формально:

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

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

4.5.1. Алгоритм Рабина-Карпа

Как уже упоминалось, с каждой предлагаемой структурой данных мы связываем набор операций, который выполняется на элементах структуры. Для ЭВМ, базовые структуры данных в основном определяются для чисел разных форматов, сложность выполнения операций над которыми занимают константное время. В связи с этим можно рассмотреть взаимно-однозначную функцию , где черезобозначено множество всех непустых цепочек в алфавите, а- множество натуральных чисел. Тогда операцию сравнения подстрок может быть заменена на операцию сравнения чисел, которая является более комфортной для ЭВМ. Пусть. Рассмотрим сначала случай, когда значения функциине очень большие и размещаются в ячейке памяти ЭВМ. Вопросы, связанные со сравнением больших чисел оставим пока для дальнейшего обсуждения.

Положим ,, и. Оценим время вычисления функции. Используя схему Горнера

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

.

Константа вычисляется один раз заранее (время вычисления не превышает). Тогда при условии, что сравнения значений функциизанимают один машинный такт, имеем алгоритм сложности.

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

Выберем наибольшее простое число , так чтобы произведениепомещалось в машинном слове. Внесем изменение в функцию, положив

В таком виде представляет хеш-функцию для искомого слова. Поскольку, то все вычисления можно проводить по модулю. Примем. При таком способе кодирования теряется однозначность (две разные последовательности могут иметь одно и то же значение), но различие значений функцииозначает несовпадение сравниваемых последовательностей. Для совпадающих хеш-значений требуется дополнительная операция сравнения текущей подпоследовательности с шаблоном, что требуетопераций. Худшая оценкаполучается в случае, когда все подпоследовательности и шаблон имеют одно и то же значение хеш-функции. Однако в большинстве случаев при подходящем выборе константыследует ожидать, что число последовательностей, для которых совпадают кодовые значения, будет минимальным и в среднем алгоритм показывает хорошие результаты. В качестве довода можно привести следующие соображения: Совпадение значений многочленов степенипри двух различных аргументах означает, что разность полиномов для соответствующих точек равна нулю. Поскольку разность представляет полином степени не более, то он имеет не болеекорней. Поэтому при выборе значениянамного большего чем, можно предполагать, что вероятность для случайных входов иметь одно и то же хеш-значение будет достаточно маленькой. Можно, конечно, выбирать и другие функции хеширования (например,- в этом случае также легко строится рекуррентное соотношение для вычисления новых значений через имеющиеся), но при этом необходимо следить, чтобы сложность ее вычисления была не болееO(m)¹⁶.

Приведем процедуру сравнения алгоритма Кнута-Карпа

Пусть исходный тест записан в массиве , а шаблон описан массивом , оrd(a) означает код символа а.

Procedure Rabin_Karp(A,D.n,m)

Var h,s,val_kod,z:integer;

Begin

h ;

s:=0;

val_kod:=0;

for i:=1 to m do begin

s:=(s*q+ord(d[i])) mod p;

val_kod:=(val_kod*q+ord(a[i])) mod p;

end;

for j:=1 to n-m+1 do begin

if val_kod=s then begin

z:=0;

while (z<m) and (a[j+z]=d[z+1]) do z:=z+1;

if (z=m) then

Print(‘образец входит в текущую последовательность в позиции:’,j);

end else

if j<n-m then begin

val_kod:= val_kod –ord(a[j])*h mod p;

if val_kod<0 then val_kod:=val_kod+p;

val_kod:=( val_kod*q+ ord(a[m+j])) mod p;

end;

end;

end;

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

Под языком в конечном алфавитебудем понимать любое (в частности, и пустое) подмножество слов в этом алфавите. Обозначим буквойпустое слово, не содержащее символов алфавита. Введем операции над языками:

1. объединение:

2. конкатенация:

3. итерация: , где--я степень языка(по конкатенации), а.

Обозначим через Ø пустое множество. Регулярные выражения и представляемые ими языки определяются следующим образом:

1. Ø является регулярным выражением и представляет пустой язык

2. является регулярным выражением и представляет язык

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

4. если и- регулярные выражения, представляющие языкиито таковыми являются выражения,и, которые соответственно представляют языки,и.

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

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

Возникает вопрос: как по регулярному выражению построить алгоритм позволяющий распознавать цепочки, входящие в соответствующее регулярное множество? Для ответа на данный вопрос рассмотрим понятие конечного детерминированного автомата (КДА).

Под КДА будем понимать пятерку , гдеи- конечные алфавиты,- функция,и. Множество- множество входных символов,- множество состояний,- функция переходов состояний,- начальное состояние автомата,- множество допускающих состояний. Автомат работает в дискретные моменты времени. В начальный момент времени автомат находится в состоянии. На вход автомата подается некоторая последовательностьсимволов алфавита. Функционирование автомата заключается в изменении состояний по закону, определяемому функцией:. Используя оператор суперпозиции, нетрудно получить. Поэтому функцияиндуцирует оператордля которого

С каждым автоматом свяжем язык, представимый этим автоматом множеством допускающих состояний. Положим. Языкпредставляет собой множество слов в алфавите, переводящих автомат из начального состояния в одно из допускающих. Обозначим класс языков, представимых в КДА через. Очевидно, автомат является конструктивным объектом, и можно легко промоделировать его работу на ЭВМ.

Ослабим несколько требования, налагаемые на автомат.

Под недетерминированным конечным автоматом (НКА) будем понимать пятерку , гдеи- конечные алфавиты,,, - и. Множество- множество входных символов,- множество состояний,- отображение парв множество подмножеств множества,- множество начальных состояний,- множество его допускающих состояний. Автомат работает в дискретные моменты времени. В начальный момент времени автомат находится в одном из состояний множества. При подаче на вход автомата словав алфавите, автомат меняет свои состояния согласно определению оператора. При этом автомат параллельно проверяет все возможные траектории, связанные со словом, и, по существу, работает с подмножествами состояний. Языкопределяется как множествоØ для некоторого. Другими словами в язык входят все последовательности в алфавите, для которых, по меньшей мере, одна из траекторий, которая начинается взавершается в одном из состояний множества. При этом можно расширить входной алфавит пустым символом, который удовлетворяет следующему соотношению: для любого словавыполняется. Переход по пустому символу из состоянияв состояниеозначает, что автомат переходя в состояниеодновременно переходит и в состояние. Обозначим класс языков представимых в НКА через.

В теории формальных языков [25] установлено, что ==.

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