Когда вы будете использовать KMP через BOYER-MOORE

В настоящее время я изучаю алгоритмы сопоставления образов и сталкиваюсь с этими двумя алгоритмами. У меня есть следующие общие идеи:

КМР

Сравнивает текст слева направо
Использование массива сбоев для интеллектуального переключения
принимает O (m), где m - длина шаблона, для вычисления массива отказов
принимает O (m), пространство
принимает O (n), время поиска строки

ВМ

Сравнивает шаблон с последним символом
Использует неудачные прыжки персонажа и прыжки хорошего суффикса
принимает O (m + размер алфавита) для вычисления таблиц
принимает O (m + размер алфавита), пробел
принимает O (n), но обычно лучше искать

Я наткнулся на следующий вопрос, который вызвал этот вопрос (True или False):

Алгоритм Knuth-Morris-Pratt (KMP) - хороший выбор, если мы хотим повторите поиск одного и того же шаблона во многих разных текстах.

Итак, я верю, что ответ верен только потому, что предполагается, что каждый раз, когда вы запускаете алгоритм на другом тексте, предварительная обработка - это только O (n), где для BM это O (n + размер алфавита). Тем не менее, я не уверен, принимаю ли я правильное предположение, что каждый раз, когда алгоритм повторно запускается, новая таблица пересчитывается. Потому что текст всегда попадает в алфавит на английском языке. Мне нужно было бы только вычислить таблицу один раз и просто повторно использовать таблицу. Итак, в конце концов, будет ли ответ на этот вопрос зависеть от того, что все алгоритмы выполняются по тексту, который содержится в одном и том же алфавите, или есть какой-то другой фактор, который может повлиять на него?

Ответ 1

Теоретически оба алгоритма будут иметь "сходную" производительность; KMP будет делать около 2n сравнений на этапе поиска, а Boyer-Moore сделает примерно 3n сравнений на этапе поиска в худшем случае. В любом случае вам не нужно повторять предварительную обработку, когда вы получаете новый текст.

Но реальный ответ заключается в том, что вы не должны использовать его на практике.

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

Однако идеи Boyer-Moore и KMP лежат в основе самых быстрых алгоритмов сопоставления строк. Что-то вроде идеи "отказа функции KMP" используется каждым практически эффективным алгоритмом соответствия строк, который я знаю; оказывается, что вы можете вычислить субоптимальную "функцию отказа" для шаблона "на лету", который по-прежнему дает вам линейное соответствие времени, но при этом требуется только дополнительное дополнительное пространство. Бойер-Мур быстрее, чем линейный, в "среднем случае", соответствующем фиксированной схеме против случайного шума, и это проявляется во многих практических ситуациях.