В чем основные отличия между поисковым алгоритмом Knuth-Morris-Pratt и алгоритмом поиска Boyer-Moore?
Я знаю, что KMP выполняет поиск Y в X, пытаясь определить шаблон в Y и сохраняет шаблон в векторе. Я также знаю, что BM работает лучше для небольших слов, таких как DNA (ACTG).
Каковы основные отличия в том, как они работают? Какой из них быстрее? Какой из них менее компьютерный? В каких случаях?
Веб-страница Moore UTexas проходит по обеим алгоритмам поэтапно (он также предоставляет различные технические источники):
По словам самого человека,
Классический алгоритм Бойера-Мура страдает от того, что он имеет тенденцию не работать так эффективно на небольших алфавитах, как ДНК. Пропустить расстояние имеет тенденцию прекращать расти с длиной образца, поскольку подстроки повторяются часто. Вспоминая больше того, что уже были сопоставлены, можно получить больше пропусков через текст. Один может даже устроить "идеальную память" и, таким образом, взглянуть на каждого персонажа в один раз, тогда как алгоритм Бойера-Мура, хотя и линейный, может несколько раз проверяйте символ из текста. Эта идея вспомнив, что в литературе больше других исследовали другие. Это страдает необходимостью для очень больших таблиц или состояний машин.
Однако были некоторые модификации BM, которые сделали поиск в маленьком алфавите жизнеспособным.
В грубом объяснении
Подход Boyer-Moore состоит в том, чтобы попытаться сопоставить последний символ шаблона вместо первого с предположением, что если в конце не совпадают, не нужно пытаться совпадение в начале, Это позволяет "большие прыжки", поэтому BM работает лучше, когда шаблон и текст, который вы ищете, напоминают "естественный текст" (т.е. Английский)
Knuth-Morris-Pratt выполняет поиск вхождения "слова" W в основной "текстовой строке" S, используя наблюдение, что, когда происходит несоответствие, само слово содержит достаточную информацию для определения где может начаться следующий матч, минуя повторное рассмотрение ранее совпадающих символов. (Источник: Wiki)
Это означает, что KMP лучше подходит для небольших наборов, таких как DNA (ACTG)
Техника Бойера-Мура соответствует символам справа налево, хорошо работает на длинных узорах. knuth moris pratt соответствует персонажам слева направо, быстро работает на коротких рисунках.