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