Использование хеширования для поиска подстрок сдвигом

Год

Оглавление

Аннотация. 3

Введение. 4

Задание на курсовую работу. 5

Описание алгоритма. 5

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

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

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

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

Обоснование выбора типа интерфейса и описание основных форм ввода-вывода. 11

Тестирование программы.. 12

Заключение. 14

Список литературы.. 14

Приложение 1………………………………………………………………………………………15

Приложение 2………………………………………………………………………………………20

Приложение 3………………………………………………………………………………………22

Приложение 4………………………………………………………………………………………27

Аннотация

Количество листов документа: 27

Количество приложений: 4

Цель работы: разработка программы "Поиск подстроки в строке" . В программе реализован алгоритм Рабина-Карпа.

Введение

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

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

Задание на курсовую работу

Заданием на курсовую работу является «Разработать программное обеспечение для полнотекстового поиска строк по введённому пользователем шаблону в файлах, находящихся в указанной пользователем директории. Алгоритм поиска – Алгоритм Рабина-Карпа».

Описание алгоритма

Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом.

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

Основной проблемой алгоритма является нахождение постоянной строки длины m, называемой образцом, в тексте длины n; например, нахождение строки "sun" в предложении "Hello sunshine in this vale of tears". Один из простейших алгоритмов для этой задачи просто ищет подстроку во всех возможных местах:

1 function NaiveSearch(string s[1..n], string sub[1..m])

For i from 1 to n

For j from 1 to m

4 if s[i+j-1] ≠ sub[j]

Jump to next iteration of outer loop

Return i

Return not found

Этот алгоритм хорошо работает во многих практических случаях, но совершенно не эффективен например на поиске строки из 10000 "a", за которыми следует "b" в строке из 10 миллионов букв "a". В этом случае он показывает своё худшее время исполнения Θ(mn).

Алгоритм Кнута — Морриса — Пратта уменьшает это время до Θ(n) только однажды используя предвычисления для каждого символа текста; Алгоритм Бойера — Мура пропускает не один символ, а столько сколько максимально возможно для того, чтобы поиск удался, эффективно уменьшая количество итераций через внешний цикл, поэтому количество символов, с которыми производится сравнение, может быть сравнимо с n/m в лучшем случае. Алгоритм Рабина-Карпа вместо этого фокусируется на ускорении строк 3-6.

Использование хеширования для поиска подстрок сдвигом

Вместо того, чтобы использовать более умный пропуск, алгоритм Рабина-Карпа пытается ускорить проверку эквивалентности образца с подстроками в тексте используя хэш-функцию. Хэш-функция — это функция, которая преобразует каждую строку в числовое значение, называемое хэш-значение; например, мы можем иметь hash("hello")=5. Алгоритм использует тот факт, что если две строки одинаковы, то и их хэш-значения также одинаковы. Таким образом, всё что нам нужно, это посчитать хэш-значение той подстроки, которую мы ищем и затем найти подстроку с таким же хэш-значением.

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

Вот так выглядит алгоритм (исходный код приложения):

1 function RabinKarp(string s[1..n], string sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 for i from 1 to (n-m+1) 5 if hs = hsub 6 if s[i..i+m-1] = sub 7 return i 8 hs := hash(s[i+1..i+m]) 9 return not found

Строки 2, 3, и 6 каждая, требуют время Ω(m). Однако, строки 2 и 3 исполняются только один раз, а строка 6 выполняется только в случае, когда хэш-значения совпадают, что не может произойти чаще, чем несколько раз. Строка 5 выполняется n раз, но всегда требует постоянного времени. Теперь рассмотрим вторую проблему: строку 8.

Если мы наивно пересчитываем хэш-значение для подстроки s[i+1..i+m], это будет требовать время Ω(m), и так как это делается в каждом цикле, алгоритм будет требовать время Ω(mn), т.е. такое же, как и наиболее простые алгоритмы. Приём для решения этой задачи заключается в том, что переменная hs уже содержит хэш-значение для s[i..i+m-1]. Если мы сможем использовать его для подсчёта следующего хэш-значения за постоянное время, тогда наша задача будет решена.

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

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

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

Заметим, что если мы очень неудачливы, или имеем очень плохую хэш-функцию, такую как постоянную функцию, строка 6 очень вероятно будет выполняться n раз, на каждую итерацию цикла. Так как она требует время Ω(m), алгоритм полностью будет требовать время Ω(mn).