Алгоритм Бойера-Мура

Модуль "Поиск" • урок 4 из 7 • ~11 минут

Как работает алгоритм Бойера-Мура

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

Если во время сравнения обнаружено несовпадение, алгоритм обращается к заранее построенной таблице "последних вхождений" символов в образец (эвристика "плохого символа"). Если символ из текста, на котором произошла ошибка, вообще не встречается в нашем образце - значит, нет смысла сдвигать образец на 1 или 2 позиции, он все равно "напорется" на этот плохой символ. Алгоритм совершает огромный скачок, сдвигая все окно поиска сразу за плохой символ.

На сквозном примере модуля это видно сразу. Ищем образец ABABAC в тексте ABABADABABAC: последний символ окна - D, а в образце есть только A, B и C. Сравнение срывается на первом же шаге, и окно перелетает через всю длину образца.

Реализация на языках C и C++ (Бойер-Мур-Хорспул)

Существует несколько вариаций алгоритма. Оригинальный Бойер-Мур использует две эвристики - плохой символ и хороший суффикс, - но и в учебниках, и на практике чаще разбирают упрощенную версию: только правило плохого символа, без правила хорошего суффикса. Ее же называют модификацией Бойера-Мура-Хорспула (BMH). Она проще в написании и на обычных текстах часто работает даже быстрее полной.

Сдвиг в упрощенной версии всегда берется по одному и тому же символу текста - тому, что стоит напротив последней позиции образца, независимо от того, на каком символе сорвалось сравнение. Таблица для этого нужна ровно одна: для каждой буквы алфавита в ней лежит расстояние от ее самого правого вхождения в образец до конца образца, а для буквы, которой в образце нет, - вся длина M.

Второе правило, хорошего суффикса, работает почти как КМП, только с конца: если хвост совпал, а дальше сорвалось, образец сдвигают до следующего такого же хвоста внутри себя. Комбинированная стратегия считает оба сдвига и берет больший - оба правила гарантируют, что меньший сдвиг вхождение не пропустит. Сами Бойер и Мур предлагали пойти дальше и объединить свою стратегию с КМП, но Н. Вирт заметил на это, что усложнение построения таблиц и самого поиска вряд ли окупится выигрышем. На практике так и вышло: закрепилась упрощенная версия.

#include <stdio.h>
#include <string.h>

#define ALPHABET_SIZE 256

// Функция поиска (Бойер-Мур-Хорспул)
void searchBMH(const char *txt, const char *pat) {
    int m = strlen(pat);
    int n = strlen(txt);
    int badChar[ALPHABET_SIZE]; // Таблица сдвигов

    // 1. Инициализация таблицы сдвигов максимальной длиной
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        badChar[i] = m;
    }
    
    // 2. Запись реальных сдвигов (кроме последней буквы)
    // Мы считаем расстояние от символа до конца образца
    for (int i = 0; i < m - 1; i++) {
        badChar[(unsigned char)pat[i]] = m - 1 - i;
    }

    // 3. Поиск по тексту
    int shift = 0; // Смещение окна относительно начала текста
    while (shift <= (n - m)) {
        int j = m - 1;
        
        // Проверяем совпадение СПРАВА НАЛЕВО
        while (j >= 0 && pat[j] == txt[shift + j]) {
            j--;
        }

        if (j < 0) {
            printf("Совпадение на индексе: %d\n", shift);
            // Если нужно искать дальше, сдвигаем окно
            shift += m; 
        } else {
            // Эвристика плохого символа: прыгаем по таблице!
            // Смотрим на последний символ текущего окна в тексте
            shift += badChar[(unsigned char)txt[shift + m - 1]]; 
        }
    }
}

Приведенный выше код на C собирается и компилятором C++ без единой правки - это проверено сборкой в режиме C++17. Но если вы пишете на C++, привычнее другая запись: std::string и std::array вместо указателей и ручного выделения памяти. Отсутствие вхождения обозначается привычным для C++ значением std::string::npos.

#include <array>
#include <string>

// Упрощенный Бойер-Мур: только правило плохой литеры
std::size_t searchBMH(const std::string& txt, const std::string& pat) {
    const std::size_t m = pat.size();
    const std::size_t n = txt.size();
    if (m == 0 || m > n) return std::string::npos;

    std::array<std::size_t, 256> shift;
    shift.fill(m);                        // чужой буквы нет в образце: прыжок на всю длину
    for (std::size_t i = 0; i + 1 < m; ++i)
        shift[static_cast<unsigned char>(pat[i])] = m - 1 - i;

    std::size_t pos = 0;
    while (pos + m <= n) {
        std::size_t j = m;
        while (j > 0 && pat[j - 1] == txt[pos + j - 1]) --j;   // сравнение справа налево
        if (j == 0) return pos;
        // сдвиг по символу текста напротив последней позиции образца
        pos += shift[static_cast<unsigned char>(txt[pos + m - 1])];
    }
    return std::string::npos;             // не найдено
}

Алгоритм воскресного дня: другая точка опоры

В 1990 году Д. Санди предложил еще одно упрощение той же идеи; в англоязычных источниках оно известно как Quick Search. Отличие от Хорспула ровно одно - по какому символу текста считается сдвиг.

Хорспул берет символ напротив последней позиции образца, то есть последний символ текущего окна. Санди берет символ, стоящий сразу за окном. Рассуждение простое: сдвиг, который еще может привести к совпадению, не превосходит длины образца, а значит этот символ после сдвига обязательно окажется под образцом. Если его в образце нет вовсе, то и перешагнуть можно вместе с ним - на M + 1 позицию.

Из-за этого меняется и таблица: она строится по всем символам образца, включая последний, а величина сдвига равна расстоянию от самого правого вхождения буквы до позиции сразу за образцом. Для ABABAC обе таблицы выглядят так:

Прыжки у Санди в среднем на единицу длиннее, и на обычных текстах это заметно. Но выигрыш не гарантирован, и сквозной пример модуля - как раз тот случай, когда лучше оказывается Хорспул. При поиске ABABAC в ABABADABABAC напротив конца первого окна стоит D, которой в образце нет, и окно сразу перелетает через шесть позиций; Санди же смотрит на символ за окном, а там A, и сдвигает всего на две. В итоге Хорспул проходит два окна и 7 сравнений символов, Санди - четыре окна и 18 сравнений.

Точка опоры у этих правил разная, поэтому и проигрывают они на разных данных. На практике их нередко объединяют - и именно такое сочетание работает внутри Python, о чем речь ниже.