Главная | Обратная связь | Поможем написать вашу работу!

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

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

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

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

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

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

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

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

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

Пусть исходный тест записан в массиве , а шаблон описан массивом , о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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒