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

Question

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

KMP

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

BM

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

я наткнулся на следующую Qu estion который вызвал этот вопрос (истина или ложь):

Алгоритм Кнута-Морриса-Пратта (KMP) является хорошим выбором, если мы хотим поиск по той же схеме неоднократно в разных текстах.

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

Answer 1

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

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

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

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