Как алгоритмы KMP и Boyer-Moore улучшают поисковые системы
Привет, Хабр!
Поисковые системы — без них не представить сегодняшний мир, они облегчают доступ к информации и улучшают пользовательский опыт. Однако, чтобы поисковая система работала эффективно, необходимы некоторые алгоритмы для обработки строк. Одни из них — Knuth-Morris-Pratt и Boyer-Moore.
Их мы и рассмотрим в сегодняшней статье, начнем с первого.
Алгоритм Knuth-Morris-Pratt (KMP)
Алгоритм Knuth-Morris-Pratt был разработан Дональдом Кнутом, Джеймсом Моррисом и Воном Праттом в 1977 году. Алгоритм стал революционным благодаря своей способности выполнять поиск за линейное время в худшем случае.
Алгоритм предназначен для поиска подстроки в строке. Он решает проблему наивного поиска, при котором возможны многократные сравнения одних и тех же символов, путем использования предварительно рассчитанной префикс-функции. Префикс-функция для строки длины
определяется как массив
, где
указывает длину наибольшего собственного префикса строки
, который одновременно является суффиксом этой строки.
Построение префикс-функции выполняется так:
Инициализация:
.
Для каждого символа
(начиная с
):
Таким образом, префикс-функция позволяет понять, сколько символов из начала строки совпадают с её концом.
Пример построения префикс-функции для строки »ababaca»:
(префикс «a» совпадает с суффиксом «a»)
(префикс «ab» совпадает с суффиксом «ab»)
(префикс «aba» совпадает с суффиксом «aba»)
(нет совпадений)
(префикс «a» совпадает с суффиксом «a»)
Процесс поиска
Процесс поиска строки в строке
заключается в следующем:
Инициализация:
индекс для
,
индекс для
.
Повторяем, пока
длина
:
Таким образом, алгоритм KMP использует префикс-функцию, чтобы избежать повторных сравнений.
Пример
Рассмотрим пример, где мы ищем подстроку »ababaca» в строке »bacbabababacaca»:
Находим префикс-функцию для »ababaca»:
Применяем алгоритм поиска:
Пример в коде
Реализуем алгоритм на Питоне:
def kmp_search(pattern, text):
def compute_prefix_function(pattern):
m = len(pattern)
pi = [0] * m
k = 0
for q in range(1, m):
while k > 0 and pattern[k] != pattern[q]:
k = pi[k - 1]
if pattern[k] == pattern[q]:
k += 1
pi[q] = k
return pi
n = len(text)
m = len(pattern)
pi = compute_prefix_function(pattern)
q = 0
for i in range(n):
while q > 0 and pattern[q] != text[i]:
q = pi[q - 1]
if pattern[q] == text[i]:
q += 1
if q == m:
print(f"Pattern occurs at index {i - m + 1}")
q = pi[q - 1]
# пример использования
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
kmp_search(pattern, text)
Функция compute_prefix_function(pattern)
функция вычисляет префикс-функцию для шаблона. Префикс-функция определяет для каждого индекса шаблона длину наибольшего собственного префикса, который также является суффиксом.
pi
— массив, содержащий значения префикс-функции.
k
— длина текущего наибольшего префикса, совпадающего с суффиксом.
Основная функция kmp_search(pattern, text)
:
n
— длина текста, m
— длина шаблона.
Вычисляем префикс-функцию для шаблона с помощью compute_prefix_function
.
q
— количество символов, совпадающих с началом шаблона.
Для каждого символа в тексте проверяем, совпадает ли он с текущим символом в шаблоне. Если да, увеличиваем q
. Если q
равно длине шаблона, значит найдено совпадение, и печатаем индекс начала совпадения в тексте. Затем сбрасываем q
на значение из префикс-функции, чтобы продолжить поиск.
Переходим к следующему алгоритму.
Алгоритм Boyer-Moore
Алгоритм Boyer-Moore был разработан Робертом Бойером и Джейом Муром также в 1977 году.
Алгоритм использует две ключевые эвристики для ускорения поиска: правило плохого символа и правило хорошего суффикса. Эти эвристики позволяют алгоритму пропускать большие части строки при сравнении.
Правило плохого символа
Правило плохого символа основано на том, что если в процессе сравнения подстроки с частью строки возникает несовпадение, алгоритм использует информацию о несовпадающем символе для того, чтобы пропустить несколько символов строки, а не проверять их снова.
Принцип работы:
Создаётся таблица плохих символов для шаблона
. Эта таблица содержит позиции каждого символа в шаблоне, с учётом его последнего появления.
Во время поиска, если символ в строке
не совпадает с символом в шаблоне P, шаблон смещается таким образом, чтобы несовпадающий символ в строке совпал с последним появлением этого символа в шаблоне.
Пример:
Пусть и
.
При первом несовпадении (например, на символе в строке и
в шаблоне, алгоритм смотрит в таблицу плохих символов и видит, что
отсутствует в шаблоне. Тогда шаблон смещается так, чтобы следующий символ строки совпал с последним символом шаблона.
Правило хорошего суффикса
Правило хорошего суффикса работает на основе совпадений в конце шаблона, называемых суффиксами. Когда происходит несовпадение, алгоритм использует информацию о совпадающих суффиксах для пропуска символов.
Принцип работы:
Создаётся таблица суффиксов для шаблона
. Эта таблица содержит информацию о позициях суффиксов в шаблоне, которые могут использоваться для смещения.
Если часть шаблона совпала с частью строки, но далее происходит несовпадение, алгоритм смещает шаблон так, чтобы следующий совпадающий суффикс выровнялся с соответствующей частью строки.
Пример:
Пусть и
.
Когда происходит несовпадение на символе в строке и
в шаблоне, алгоритм смотрит на таблицу суффиксов и определяет, что следующий возможный суффикс совпадает с позицией в строке, что позволяет сместить шаблон на несколько позиций вправо.
Пример использования
Рассмотрим строку T и шаблон P:
Шаг 1: Выравниваем шаблон с началом строки.
Шаг 2: Сравниваем символы с конца шаблона.
Шаг 3: При несовпадении применяем правило плохого символа или правило хорошего суффикса.
Шаг 4: Смещаем шаблон и повторяем процесс.
Пример:
Пусть и
.
Инициализация:
Поиск:
Сравниваем строку и шаблон.
При несовпадении находим подходящее смещение по таблицам.
Смещаем шаблон и продолжаем сравнение.
Алгоритм Boyer-Moore имеет среднюю сложность для практических случаев, где
— длина строки, а
— длина шаблона. Этот алгоритм очень хорош при работе с большими строками и сложными шаблонами.
Пример кода:
Реализуем аналогично предыдущему алгоритму на Питоне:
def boyer_moore_search(pattern, text):
def bad_character_table(pattern):
table = {}
m = len(pattern)
for i in range(m - 1):
table[pattern[i]] = i
return table
def good_suffix_table(pattern):
m = len(pattern)
table = [0] * m
last_prefix_position = m
for i in range(m - 1, -1, -1):
if is_prefix(pattern, i + 1):
last_prefix_position = i + 1
table[m - 1 - i] = last_prefix_position - i + m - 1
for i in range(m - 1):
slen = suffix_length(pattern, i)
table[slen] = m - 1 - i + slen
return table
def is_prefix(pattern, p):
m = len(pattern)
for i in range(p, m):
if pattern[i] != pattern[i - p]:
return False
return True
def suffix_length(pattern, p):
m = len(pattern)
length = 0
i = p
j = m - 1
while i >= 0 and pattern[i] == pattern[j]:
length += 1
i -= 1
j -= 1
return length
n = len(text)
m = len(pattern)
if m == 0:
return []
bad_char_table = bad_character_table(pattern)
good_suffix_table = good_suffix_table(pattern)
s = 0
while s <= n - m:
j = m - 1
while j >= 0 and pattern[j] == text[s + j]:
j -= 1
if j < 0:
print(f"Pattern occurs at index {s}")
s += good_suffix_table[0]
else:
bad_char_shift = j - bad_char_table.get(text[s + j], -1)
good_suffix_shift = good_suffix_table[j]
s += max(bad_char_shift, good_suffix_shift)
# пример
text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
boyer_moore_search(pattern, text)
Функция bad_character_table(pattern)
создаёт таблицу плохих символов для шаблона. Таблица содержит индексы последнего появления каждого символа в шаблоне, кроме последнего символа.
Функция good_suffix_table(pattern)
создаёт таблицу хороших суффиксов для шаблона. Таблица содержит смещения, которые определяются для каждого суффикса шаблона.
Вспомогательные функции is_prefix(pattern, p)
и suffix_length(pattern, p)
:
is_prefix
проверяет, является ли подстрока от позиции p
до конца шаблона префиксом всего шаблона.
suffix_length
определяет длину наибольшего суффикса шаблона, который заканчивается в позиции p
.
Основная функция boyer_moore_search(pattern, text)
вычисляет таблицы плохих символов и хороших суффиксов для шаблона. После выполняет поиск шаблона в строке, используя обе таблицы для эффективного пропуска символов при несовпадениях. А в конце выводит индексы вхождений шаблона в строке.
Как можно заметитиь, эти алгоритмы очень мощные и каждые предлагают уникальные подходы и преимущества.
KMP использует префикс-функцию для управления смещением при несовпадениях, обеспечивая линейную сложность в худшем случае.
А вот алгоритм Boyer-Moore использует две ключевые эвристики: правило плохого символа и правило хорошего суффикса, которые позволяют значительно ускорить процесс поиска за счёт пропуска множества символов.
Выбор между KMP и Boyer-Moore зависит от конкретного случая использования и требований к производительности.
Развивать алгоритмическое мышление и учиться увеличивать производительность программ можно на онлайн-курсе «Алгоритмы и структуры данных» в Отус.