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

Поисковые системы - без них не представить сегодняшний мир, они облегчают доступ к информации и улучшают пользовательский опыт. Однако, чтобы поисковая система работала эффективно, необходимы некоторые алгоритмы для обработки строк. Одни из них - 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 зависит от конкретного случая использования и требований к производительности.

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