Рабин-Карп и поиск множества образцов

Алгоритм Рабина-Карпа в поиске одиночного образца хуже алгоритма Кнута — Морриса — Пратта, алгоритма Бойера — Мура и других быстрых алгоритмов поиска строк по причине его медленного поведения в худшем случае. Алгоритм Рабина-Карпа можно также использовать для поиска множественных образцов с трудоемкостью, линейной в лучшем случае и квадратичной в труднодостижимом худшем случае. Но и здесь он проигрывает алгоритму Ахо - Корасик, имеющему линейное время работы в худшем случае.

Таким образом, если мы хотим найти любое из большого набора, скажем длины k, образцов фиксированной длины в тексте, мы можем создать простой вариант алгоритма Рабина-Карпа, который использует хэш-таблицу или любую другую структуру данных множества (set data structure) для проверки того, когда хэш данной строки принадлежит набору хэш значений образцов, которые мы ищем:

function RabinKarpSet(string s[1..n], set of string subs, m) { set hsubs := emptySet for each sub in subs insert hash(sub[1..m]) into hsubs hs := hash(s[1..m]) for i from 1 to n if hs ∈ hsubs if s[i..i+m-1] = a substring with hash hs return i hs := hash(s[i+1..i+m]) return not found }

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

Другие алгоритмы могут искать одиночный образец за время O(n), и следовательно, они могут быть использованы для поиска k образцов за время O(n k). В противоположность им, вариант алгоритма Рабина-Карпа выше может найти все k образцов за ожидаемое время O(n+k), потому что хэш-таблица, используемая для проверки случая когда хэш подстроки равен хэшу любого из образцов использует O(1) времени.

 

Логическая структура программы

1. Открываем программу

2. В диалоговом окне выбираем текстовый файл, после выбора которого, текст выведется в окне в RichEdit1

3. В Edit1 под текстом вводим строку для поиска

4. Нажимаем кнопку «Найти»

4.1 Если такая строка есть, то она выделится красным цветом в тексте

4.2 Если строки нет, то будет выведено сообщение «Такой строки нет»

5. Для очистки окна с текстом выберете Файл -> очистить

5.1 Для очистки выделения текста выберете Файл -> очистить выделение

6. Для вывода справки по работе нажмите Справка -> Руководство к работе

7. Для завершения работы нажмите крестик в правом верхнем углу или нажмите Файл -> Закрыть

Обоснование выбора языка программирования

Моя программа написана на языке программирования Object Pascal, в среде программирования Delphi 7. Я выбрал этот язык программирования и эту среду, так как всё это мне очень хорошо известно и я уже больше года работаю здесь.

Преимущества Delphi по сравнению с аналогичными программными продуктами:

- быстрота разработки приложений;

- высокая производительность разработанного приложения;

- низкие требования разработанного приложения к ресурсам компьютера;

- наращиваемость за счет встраивания новых компонентов и инструментов в среде Delphi;

Система программирования Delphi рассчитана на программирование различных приложений и представляет большое количество компонентов для этого.

Обоснование выбора структур данных для решения задачи

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

 

Таблица идентификаторов:

 

Наименование	Обозначение	Тип данных
Текстовый файл	DATE	Структурный(TextFile)
Строка поиска	str_poiska	Строковый(String)
Текст	str_text	Строковый(String)
Число элементов в строке поиска	dlina_poiska	Целочисленный(integer)
Число элементов в тексте	dlina_text	Целочисленный(integer)
Счётчики в массивах	i, vid_text	Целочисленный(integer)
Хеш строки поиска и текста	hashpoisk, hashtext	Целочисленный(integer)
Часть текста	bufer_text	Строковый(String)

Спецификации программных модулей

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

Unit1 является основным модулем программы. В нем описываются все основные процедуры и функции. Но в программе есть ещё Unit2 и Unit3.

Заголовок процедуры или функции	Выполняемое действие
procedure TForm1.Button1Click	Редактирование текста, поиск строки, выделение цветом
procedure TForm1.Timer1Timer	Скрывает первую форму
procedure TForm1.N7Click	Очистка цвета шрифта
procedure TForm1.N3Click	Загрузка файла
procedure TForm1.N4Click	Выводит справку
procedure TForm1.N5Click	Закрытие программы
procedure TForm1.N6Click	Очистка RichEdit1 и Edit1
procedure TForm3.Timer1Timer	Скрывает третью форму и показывает первую
procedure TForm2.FormCreate	Выводится в Memo1 текст