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

Я сталкиваюсь с проблемами в понимании алгоритма поиска строки Бойера Мура.

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

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

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

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

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

Источник

6 ответов

Решение

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

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

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

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

Как только я начинаю сопоставление с начала подстроки, когда я нахожу несоответствие, я не могу просто начать с нуля. Я мог бы быть частично через матч, начинающийся в другой точке. Например, если я пытаюсь соответствовать anand в ananand успешно совпадают, ananпоймите, что следующее a это не d, но я только что подобрал anи поэтому я должен вернуться к попытке сопоставить мой третий символ в моей подстроке. Эта информация: "Если мне не удастся сопоставить символы х, я могу быть у 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
Источник

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

Скажем наш образец 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 пока мы не преуспеем или не достигнем несоответствия. (3а) если происходит несоответствие k персонажи с самого начала p и несовпадающий персонаж не находится в pтогда мы можем продвинуться (по крайней мере) k персонажи.

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

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

Тем не менее, мы можем сделать лучше, чем это. (3б), так как мы знаем, что на старом 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 =                             ^

и бинго! Были сделаны.

Источник

А как насчет веб-сайта соавтора этого алгоритма - это помогает?
http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html

ура!

Источник

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

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

Источник

Я нашел эту ссылку, это объясняет алгоритм самым простым способом. Надеюсь это поможет. http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore

Источник

Еще одно подробное объяснение... http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides03.pdf

Источник
Другие вопросы по тегам