Понимание и пример алгоритма Бойера Мура?

Я столкнулся с проблемами в понимании алгоритма поиска Boyer Moore String.

Я следую следующему документу. Ссылка

Я не могу разобраться в том, что такое истинный смысл delta1 и delta2 здесь, и как они применяют это для поиска строкового алгоритма поиска. Язык выглядел немного расплывчатым.

Просьба, если кто-нибудь из нас может помочь мне в понимании этого, было бы очень полезно.

Или, если вы знаете какую-либо другую ссылку или документ, который легко понять, пожалуйста, поделитесь.

Спасибо заранее.

Ответы

Ответ 1

Сначала совет, сделайте глубокий вдох. Вы явно подчеркнуты, и когда вы подчеркиваете, первое, что происходит, это то, что большие куски вашего мозга закрыты. Это усложняет понимание, что увеличивает стресс, и у вас есть проблема.

5-минутный тайм-аут для улучшения вашего свободного пространства может показаться невозможным, но может быть неожиданно полезным.

Теперь, когда сказано, алгоритм основан на простом принципе. Предположим, что я пытаюсь совместить подстроку длиной m. Сначала я посмотрю на символ с индексом m. Если этот символ не в моей строке, я знаю, что подстрока, которую я хочу, не может начинаться с символов в индексе 1, 2, ... , m.

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

Как только я начну сопоставлять с начала подстроки, когда я нахожу несоответствие, я не могу просто начать с нуля. Я мог бы частично пройти матч, начиная с другой точки. Например, если я пытаюсь сопоставить anand в ananand с успехом, anan, поймите, что следующий a не является d, но я только что сопоставил an, и поэтому я должен вернуться к попытке сопоставить мой третий символ в моей подстроке. Это: "Если я не сработал после сопоставления символов x, я мог бы быть на символе y'th символа соответствия" информация хранится во второй таблице.

Обратите внимание, что когда я не могу соответствовать второй таблице, знает, как далеко в матче я могу основываться на том, что я только что сопоставил. Первая таблица знает, как далеко назад я мог бы основываться на характере, который я только что видел, который мне не удалось сопоставить. Вы хотите использовать более пессимистичные данные этих двух частей информации.

С учетом этого алгоритм работает следующим образом:

start at beginning of string
start at beginning of match
while not at the end of the string:
    if match_position is 0:
        Jump ahead m characters
        Look at character, jump back based on table 1
        If match the first character:
            advance match position
        advance string position
    else if I match:
        if I reached the end of the match:
           FOUND MATCH - return
        else:
           advance string position and match position.
    else:
        pos1 = table1[ character I failed to match ]
        pos2 = table2[ how far into the match I am ]
        if pos1 < pos2:
            jump back pos1 in string
            set match position at beginning
        else:
            set match position to pos2
FAILED TO MATCH

Ответ 2

Понимание Boyer-Moore заключается в том, что если вы начнете поиск шаблона в строке, начинающейся с последнего символа в шаблоне, вы можете пересканировать свой поиск несколькими символами, когда вы нажмете несоответствие.

Скажем, наш шаблон p представляет собой последовательность символов p1, p2,..., pn и мы ищем строку s, в настоящее время с p выровненную так, чтобы pn находится в индексе i в s.

например:.

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i =       ^

В документе B-M сделаны следующие замечания:

(1), если мы попытаемся сопоставить символ, который не находится в p, тогда мы можем перейти вперед n символов:

'F' не находится в p, поэтому мы продвигаем символы n:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =        AT THAT
i =              ^

(2), если мы попытаемся сопоставить символ, последняя позиция которого находится k с конца p, тогда мы можем перейти вперед k символов:

'последняя позиция в p равна 4 с конца, поэтому мы продвигаем 4 символа:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =            AT THAT
i =                  ^

Теперь мы отскакиваем назад от i до тех пор, пока мы не добьемся успеха или не попали в несоответствие. (3a), если в рассогласовании встречаются символы k с начала p, а несоответствующий символ не находится в p, тогда мы можем продвигать (по крайней мере) k символы.

'L' не находится в p, а несоответствие произошло против p6, поэтому мы можем продвинуть (по крайней мере) 6 символов:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                  AT THAT
i =                        ^

Однако мы действительно можем сделать лучше, чем это. (3b), поскольку мы знаем, что при старом i мы уже сопоставляли некоторые символы (в этом случае 1). Если совпадающие символы не совпадают с началом p, тогда мы можем немного перепрыгнуть вперед (это дополнительное расстояние называется "delta2" в документе):

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                   AT THAT
i =                         ^

В этот момент наблюдение (2) применяется снова, давая

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                       AT THAT
i =                             ^

и бинго! Мы закончили.

Ответ 4

Это объяснение H.W. Lang действительно ясно, что он объясняет B & M в каждом конкретном случае с подробными описаниями. Только после прочтения этого я понял алгоритм B & M.

http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm