Введение в алгоритмы BM

Функция «Найти» (Ctrl+F) различных текстовых редакторов в основном использует алгоритм Бойера-Мура.

Алгоритм Бойера-Мура не только эффективен, но и продуман до мелочей, и его легко понять. Этот алгоритм был изобретен в 1977 году профессорами Робертом С. Бойером и Дж. Строзером Муром из Техасского университета.

Ниже я представляю алгоритм BM, основанный на главе 2 «Точное сопоставление: классические методы на основе сравнения» книги «Алгоритмы строк, деревьев и последовательностей».

хороший суффикс

Если предположить, что x[i]=a и y[i+j] = b различны в процессе сопоставления, текущая информация о сопоставлении будет следующей:

x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u

x[i] != y[i+j]

На данный момент мы предполагаем, что можем найти крайнюю правую позицию u в x, мы можем напрямую сдвинуть x вправо на расстояние сдвига.

но если мы не находим u в x, то мы пытаемся найти самый длинный суффикс v в y[i+j+1 .. j+m-1], который также является префиксом x.

Обобщите две приведенные выше ситуации:

• ты можешь снова появиться в x полностью

• Суффикс u является префиксом x

плохой характер

Мы находим крайнюю правую позицию y[i+j]=b в x, и если она не найдена, выравниваем y[i+j+1] непосредственно слева:

Мы можем обнаружить, что в случае плохих символов сдвиг может быть отрицательным.

переехать

Мы можем вычислить сдвиг (хороший суффикс) и сдвиг (плохой символ) в соответствии с хорошим суффиксом и плохим символом выше, и сдвиг, который мы фактически перемещаем, равен max(shift (хороший суффикс), shift (плохой символ)).

Реализация алгоритма

Давайте посчитаем сдвиг (хороший суффикс) и сдвиг (плохой символ) отдельно.

Давайте сначала найдем сдвиг (плохой символ), конкретный алгоритм следующий:

Первое описание на приведенном выше рисунке состоит в том, что когда хвост не совпадает, мы находим позицию символа a в шаблоне, предполагая, что это i, тогда расстояние сдвига шаблона равно n-i

Во-вторых, сказать, что если несовпадение происходит в j-й позиции в шаблоне, то позиция символа a в шаблоне равна i, а сдвиг равен ji в это время, что означает, что если в это время мы можем возьмем только shift=1, давайте посчитаем

Давайте посмотрим, как вычисляется суффикс:

Глядя на рисунок выше, мы определяем L (i) как наибольшую позицию меньше n, удовлетворяющую P[i..n] является суффиксом P[1..L(i)].

Затем мы определяем L'(i), его смысл показан выше, мы определяем P[i-1] != P[L'(i)-n+i-1] на основе L(i).

Например:

Затем мы определяем самый длинный общий суффикс как P[1..j] и P[1..n].

Давайте посмотрим на определение P[1..j], предполагая, что существует i, удовлетворяющее условию L'(i)=j, то есть P[i..n] — тот же суффикс, а P[i- 1]!=P[j- n+i-1] также отличается, то есть в этот момент L'(i)=j, поэтому имеем следующий алгоритм:

В приведенном выше алгоритме мы предполагаем, что уже знаем Nj(P), а затем вычисляем L'(i) через Nj, так как же мы вычисляем Nj?

После вычисления Nj выполняется вычисление L':

Давайте рассмотрим другую ситуацию. Когда мы не можем найти суффикс, то есть L'(i)=0, мы можем согласиться на следующий лучший вариант и запросить префикс. См. рисунок ниже:

Мы определяем l '(i) как самый длинный суффикс p [i..n], а также префикс p [1..n], если такого префикса нет, то l' [i] = 0, то Значение - сказать, что в это время Shift = N, почему движение является крупнейшим? Поскольку мы впервые узнаем, если p [i..n] существует в шаблоне, потому что если мы хотим соответствовать, p [1..l '(i)] должен существовать в шаблоне, но, к сожалению, мы не нашли его, это Время, которое мы можем напрямую сместить I-1 первым, а затем медленно перемещайтесь вправо, пока L '(i). Процесс выглядит следующим образом:

Вот как вычислить l'(i).

Если предположить, что l'(i) существует, то есть l'(i) = j>0, то в данный момент Nj(P) = j, и j должно быть меньше или равно |P[i.. n]| = n - i + 1, с таким пониманием давайте посмотрим, как вычислить l'(i).

Предполагая, что N[j] == j, j i

код показывает, как показано ниже:

Теперь давайте посмотрим, как рассчитать расстояние смещения в соответствии с L'(i) и l'(i): когда P[i-1] != T[k], если L'(i) > 0, то Move n - L'(i), иначе переместить n - l'(i), здесь нужно обратить внимание на частный случай, то есть при i=n нужно переместить 1 бит.

код показывает, как показано ниже:

Хорошо, теперь все готово, мы запускаем весь процесс поиска, полный код поиска смотрите по адресу github.

Еще одну иллюстрацию полного процесса поиска можно найти в примерах поиска.

Поскольку поддержка Markdown в заголовке не очень хорошая, вы можете прочитать исходный текст: https://www.zybuluo.com/zhuanxu/note/1035645