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

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

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

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

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

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

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

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

Инициализация: $\pi[0] = 0$ .
Для каждого символа (начиная с ):

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

Пример построения префикс-функции для строки »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»)

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

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

Инициализация: индекс для , индекс для .
Повторяем, пока длина :

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

Пример:

Пусть P = и T = .

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

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

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

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

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

Пример:

Пусть P = и T = .

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

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

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

Шаг 1: Выравниваем шаблон с началом строки.
Шаг 2: Сравниваем символы с конца шаблона.
Шаг 3: При несовпадении применяем правило плохого символа или правило хорошего суффикса.
Шаг 4: Смещаем шаблон и повторяем процесс.

Пример:

Пусть P = и T = .

Инициализация:
Поиск:
- Сравниваем строку и шаблон.
- При несовпадении находим подходящее смещение по таблицам.
- Смещаем шаблон и продолжаем сравнение.

Алгоритм Boyer-Moore имеет среднюю сложность O(n/m) для практических случаев, где — длина строки, а — длина шаблона. Этот алгоритм очень хорош при работе с большими строками и сложными шаблонами.

Пример кода:

Реализуем аналогично предыдущему алгоритму на Питоне:

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

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