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

Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.)

Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ -- образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором ${\hbox{\tt x[k]}}={\hbox{\tt s}}$ .Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить ${\hbox{\tt pos[s]}}={\hbox{\tt 0}}$ (мы увидим дальше, почему).

$\scriptstyle{\blacktriangleright}$ 10.5.1. Как заполнить массив pos?

Решение.

        положить все pos[s] равными 0
        for i:=1 to n do begin
          pos[x[i]]:=i;
        end;

В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале ${\hbox{\tt last}} = {\hbox{\tt n}}$ (длина образца), затем last постепенно увеличивается.

    last:=n;
    {все предыдущие положения образца уже проверены}
    while last <= m do begin {слово не кончилось}
    | if x[m] <> y[last] then begin {последние буквы разные}
    | | last := last + (n - pos[y[last]]);
    | | {n - pos[y[last]]  - это минимальный сдвиг образца,
    | |    при котором напротив y[last] встанет такая же
    | |    буква в образце. Если такой буквы нет вообще,
    | |    то сдвигаем на всю длину образца}
    | end else begin
    | | если нынешнее положение подходит, т.е. если
    | | x[1]..x[n] = y[last-n+1]..y[last],
    | | то сообщить о совпадении;
    | | last := last+1;
    | end;
    end;

Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы s.

Возможны разные модификации этого алгоритма. Например, можно строку $\begin{displaymath} {\hbox{\tt last:=last+1}}\end{displaymath}$ заменить на $\begin{displaymath} {\hbox{\tt last:=last+(n-u)}},\end{displaymath}$ где u -- координата второго справа вхождения буквы x[n] в образец. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 10.5.2. Как проще всего учесть это в программе?

Решение. При построении таблицы pos написать

        for i:=1 to n-1 do...

(далее как раньше), а в основной программе вместо $\begin{displaymath} {\hbox{\tt last:=last+1}}\end{displaymath}$ написать

        last:= last+n-pos[y[last]];`

Приведенная нами упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.

$\scriptstyle{\blacktriangleright}$ 10.5.3. Привести пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить.

Решение. Пусть образец имеет вид ${\hbox{\tt baaa}}\ldots{\hbox{\tt aa}}$ , а само слово состоит только из букв a. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. $\scriptstyle\blacktriangleleft$

Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит $C({\hbox{\tt m}}+{\hbox{\tt n}})$ в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z , а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в $C({\hbox{\tt m}}+{\hbox{\tt n}})$ действий.

pvv
1/8/1999