Сравнение алгоритма Ахо-Корасика и алгоритма Рабина-Карпа

Я работаю над алгоритмами поиска строк, которые поддерживают поиск по нескольким шаблонам. Я нашел два алгоритма, которые кажутся наиболее сильными кандидатами с точки зрения времени выполнения, а именно: Aho-Corasick и Rabin-Karp . Однако я не смог найти исчерпывающего сравнения между этими двумя алгоритмами. Какой алгоритм более эффективен? Кроме того, какой из них больше подходит для параллельных вычислений и поиска по нескольким шаблонам? Наконец, какой из них требует меньше аппаратных ресурсов?

Для алгоритма переменного тока фаза поиска занимает времени, в то время как для RK это . Тем не менее, время работы для RK составляет что делает его похожим на AC. Мой предварительный вывод заключается в том, что РК кажется практически лучше, поскольку ему не нужно столько памяти, сколько АС. Это правильно? $O(n+m)$ $O(nm)$ $O(n+m)$

algorithms algorithm-analysis runtime-analysis strings ястреб
источник

Все ли ваши рисунки одинаковой длины?

Хендрик Ян

@HendrikJan Нет, модели разной длины

Ястреб

Если шаблоны имеют разную длину, кажется, трудно обрабатывать их параллельно, используя RK? Страница википедии, кажется, предполагает, что эти шаблоны имеют одинаковую длину, хотя обновление хешей может быть сделано для различной длины.

Хендрик Ян

Вас интересует какое-то теоретическое обучение или практический опыт?

Рафаэль

@Raphael Академически, мы использовали теоретические исследования, прежде чем доказывать это эмпирически. Я разместил вопрос здесь, потому что я не жду ответов по программированию. Мне нужен логичный алгоритмический ответ

Ястреб

Ответы:

Асимптотический анализ времени выполнения вряд ли будет лучшим инструментом для выбора между этими двумя алгоритмами: асимптотический анализ игнорирует постоянные факторы, и постоянные факторы здесь будут иметь решающее значение. Оба алгоритма имеют в основном одинаковое время асимптотики, поэтому асимптотический анализ, вероятно, не очень помогает выбирать между ними.

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

$O(nm)$ $O(n+m)$

$O(n+m)$ $c\cdot(n+m)$ $c$ $O(n+m)$

$O(n+m)$ $O(nm)$

DW
источник

Однако я не смог найти исчерпывающего сравнения между этими двумя алгоритмами.

$O(n + m)$ $O(n m)$

но в отношении вашего неявного запроса на «всестороннее сравнение» некоторые статьи были написаны экспериментально / эмпирически, сравнивая эти два и другие алгоритмы с реальными данными и включающие анализ / сравнение плюсов / минусов / компромиссов различных алгоритмов, например:

Методологии сопоставления множественных шаблонных строк: сравнительный анализ / Хан, Патерия
СРАВНИТЕЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ БРИОЛОГИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СООТВЕТСТВИЯ СТРОКАМ / Пандисельвам, Маримуту, Лавранс

ВЗН
источник