Меню сайта
Категории каталога
Алгоритмы [5]
Мини-чат
Главная » Статьи » Программирование » Алгоритмы

Часть 4. Поиск подстроки в строке. Алгоритм Рабина-Карпа

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

Алгоритм не широко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность
O(nm), что является одной из причин того, почему он не используется широко. Однако, он имеет уникальную особенность быть способным находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.

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


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

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

 1 function NaiveSearch(string s[1..n], string sub[1..m])
2 for i from 1 to n
3 for j from 1 to m
4 if s[i+j-1] ≠ sub[j]
5 jump to next iteration of outer loop
6 return i
7 return not found

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

Алгоритм Кнута-Морриса-Пратта уменьшает это время до O(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
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], это будет требовать время O(m), и так как это делается в каждом цикле, алгоритм будет требовать время O(m), т.е. такое же, как и наиболее простые алгоритмы. Приём для решения этой задачи заключается в том, что переменная hs уже содержит хэш-значение для s[i .. i+m-1 ]. Если мы сможем использовать его для подсчёта следующего хэш-значения за постоянное время, тогда наша задача будет решена.

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

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

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

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


Используемая хеш-функция

Ключом к производительности алгоритма Рабина-Карпа является эффективное вычисление хэш-значения последовательных подстрок текста. Одна популярная и эффективная кольцевая хэш-функция интерпретирует каждую подстроку как число в некоторой системе счисления, основание которой является большим простым числом. Например, если подстрока "hi" и основание системы счисления 101, хэш-значение будет 104 × 1011 + 105 × 1010 = 10609 (ASCII код 'h' - 104 и 'i' - 105)

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

Например, если мы имеем текст "abracadabra" и ищем образец длины 3, мы можем рассчитать хэш подстроки "bra" из хэша подстроки "abr" (предыдущая подстрока), вычитая число добавленное для первой буквы 'a' из "abr", т.е. 97 × 1012 (97 - ASCII для 'a' и 101 - основание, которое мы используем), умножение на основание и наконец добавляя последнее число для "bra", т.е. 97 × 1010 = 97. Если подстроки в запросе длинны, этот алгоритм достигает большой экономии сравнимо с многими другими схемами хэширования.

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


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

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

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



Источник: http://ru.wikipedia.org
Категория: Алгоритмы | Добавил: chas (18.09.2008) | Автор: Александр Чигиринский
Просмотров: 3655 | Рейтинг: 3.0/2 |
Всего комментариев: 0

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Основной сайт
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Copyright CHAS © 2017
Бесплатный хостинг uCoz