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

Question

У меня проблемы с пониманием алгоритма поиска строки Бойера Мура.

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

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

Будь добр, если кто-нибудь поможет мне понять это, это будет очень полезно.

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

Заранее спасибо.

Answer 1

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

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

Например:

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

В статье BM содержатся следующие наблюдения:

(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 =                             ^

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

Answer 2

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

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

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

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

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

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

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

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