badcasedaily1 19 июл в 16:36

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

Простой

6 мин

1.4K

Блог компании OTUSPython*Программирование*Алгоритмы*Поисковая оптимизация*

Обзор

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

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

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

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

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

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

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

Инициализация: $\pi[0] = 0$ .
Для каждого символа (начиная с ):
- Устанавливаем $k = \pi[i-1]$ .
- Пока и $P[k] \neq P[i]$ , уменьшаем до $\pi[k-1]$ .
- Если , то увеличивается на .
- Устанавливаем $\pi[i] = k$ .

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

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

$P[0] = a : \pi[0] = 0$
$P[1] = b : \pi[1] = 0$
$P[2] = a : \pi[2] = 1$ (префикс "a" совпадает с суффиксом "a")
$P[3] = b : \pi[3] = 2$ (префикс "ab" совпадает с суффиксом "ab")
$P[4] = a : \pi[4] = 3$ (префикс "aba" совпадает с суффиксом "aba")
$P[5] = c : \pi[5] = 0$ (нет совпадений)
$P[6] = a : \pi[6] = 1$ (префикс "a" совпадает с суффиксом "a")

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

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

Инициализация: индекс для , индекс для .
Повторяем, пока длина :
- Если , увеличиваем и .
- Если , значит, найдено совпадение:
  - Позиция совпадения:.
  - Сбрасываем на $\pi[j-1]$ для продолжения поиска.
- Если $P[j] \neq T[i]$ :
  - Если j \neq 0, устанавливаем $j = \pi[j-1]$ .
  - Иначе, увеличиваем .

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

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

Теги:

Хабы:

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

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

Пример

Пример в коде

Алгоритм Boyer-Moore

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

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

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

Публикации

Информация