Как алгоритмы KMP и Boyer-Moore улучшают поисковые системы

Привет, Хабр!

Поисковые системы — без них не представить сегодняшний мир, они облегчают доступ к информации и улучшают пользовательский опыт. Однако, чтобы поисковая система работала эффективно, необходимы некоторые алгоритмы для обработки строк. Одни из них — Knuth-Morris-Pratt и Boyer-Moore.

Их мы и рассмотрим в сегодняшней статье, начнем с первого.

Алгоритм Knuth-Morris-Pratt (KMP)

Алгоритм Knuth-Morris-Pratt был разработан Дональдом Кнутом, Джеймсом Моррисом и Воном Праттом в 1977 году. Алгоритм стал революционным благодаря своей способности выполнять поиск за линейное время в худшем случае.

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

Построение префикс-функции выполняется так:

1. Инициализация: .

2. Для каждого символа (начиная с ):

   • Устанавливаем .

   • Пока и , уменьшаем до .

   • Если , то увеличивается на .

   • Устанавливаем .

Таким образом, префикс-функция позволяет понять, сколько символов из начала строки совпадают с её концом.

Пример построения префикс-функции для строки «ababaca«:

• 

• 

• (префикс «a» совпадает с суффиксом «a»)

• (префикс «ab» совпадает с суффиксом «ab»)

• (префикс «aba» совпадает с суффиксом «aba»)

• (нет совпадений)

• (префикс «a» совпадает с суффиксом «a»)

Процесс поиска

Процесс поиска строки в строке заключается в следующем:

1. Инициализация: индекс для , индекс для .

2. Повторяем, пока длина :

   • Если , увеличиваем и .

   • Если , значит, найдено совпадение:

     • Позиция совпадения:.

     • Сбрасываем на для продолжения поиска.

   • Если :

     • Если j \neq 0, устанавливаем.

     • Иначе, увеличиваем .

Таким образом, алгоритм KMP использует префикс-функцию, чтобы избежать повторных сравнений.

Пример

Рассмотрим пример, где мы ищем подстроку «ababaca» в строке «bacbabababacaca«:

1. Находим префикс-функцию для «ababaca«:

2. Применяем алгоритм поиска:

   • 

   • 

   • 

   • 

   • 

   • 

   • 

   • 

   • 

   • 

   • 

   • : найдено совпадение на позиции

Пример в коде

Реализуем алгоритм на Питоне:

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 году.

Алгоритм использует две ключевые эвристики для ускорения поиска: правило плохого символа и правило хорошего суффикса. Эти эвристики позволяют алгоритму пропускать большие части строки при сравнении.

Правило плохого символа

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

Принцип работы:

1. Создаётся таблица плохих символов для шаблона . Эта таблица содержит позиции каждого символа в шаблоне, с учётом его последнего появления.

2. Во время поиска, если символ в строке не совпадает с символом в шаблоне P, шаблон смещается таким образом, чтобы несовпадающий символ в строке совпал с последним появлением этого символа в шаблоне.

Пример:

Пусть и .

При первом несовпадении (например, на символе в строке и в шаблоне, алгоритм смотрит в таблицу плохих символов и видит, что отсутствует в шаблоне. Тогда шаблон смещается так, чтобы следующий символ строки совпал с последним символом шаблона.

Правило хорошего суффикса

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

Принцип работы:

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

2. Если часть шаблона совпала с частью строки, но далее происходит несовпадение, алгоритм смещает шаблон так, чтобы следующий совпадающий суффикс выровнялся с соответствующей частью строки.

Пример:

Пусть и .

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

Пример использования

Рассмотрим строку T и шаблон P:

• Шаг 1: Выравниваем шаблон с началом строки.

• Шаг 2: Сравниваем символы с конца шаблона.

• Шаг 3: При несовпадении применяем правило плохого символа или правило хорошего суффикса.

• Шаг 4: Смещаем шаблон и повторяем процесс.

Пример:

Пусть и .

1. Инициализация:

   • Таблица плохих символов: ‘

   • Таблица суффиксов:

2. Поиск:

   • Сравниваем строку и шаблон.

   • При несовпадении находим подходящее смещение по таблицам.

   • Смещаем шаблон и продолжаем сравнение.

Алгоритм 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 зависит от конкретного случая использования и требований к производительности.

Развивать алгоритмическое мышление и учиться увеличивать производительность программ можно на онлайн-курсе «Алгоритмы и структуры данных» в Отус.