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