Comparação entre o algoritmo Aho-Corasick e o algoritmo Rabin-Karp

Estou trabalhando em algoritmos de pesquisa de string que suportam a pesquisa de vários padrões. Encontrei dois algoritmos que parecem os candidatos mais fortes em termos de tempo de execução, a saber, Aho-Corasick e Rabin-Karp . No entanto, não consegui encontrar nenhuma comparação abrangente entre os dois algoritmos. Qual algoritmo é mais eficiente? Além disso, qual é o mais adequado para computação paralela e pesquisa de múltiplos padrões? Finalmente, qual requer menos recursos de hardware?

Para o algoritmo AC, a fase de pesquisa leva tempo , enquanto é para RK. No entanto, o tempo de execução para o RK é que o torna semelhante ao AC. Minha conclusão preliminar é que o RK parece praticamente melhor, pois não precisa de tanta memória quanto o AC. Isso está correto? $O(n+m)$ $O(nm)$ $O(n+m)$

algorithms algorithm-analysis runtime-analysis strings Falcão
fonte

Todos os seus padrões têm o mesmo comprimento?

Hendrik Jan

@HendrikJan Não, diferentes padrões de comprimento

Falcão

Se os padrões são de tamanhos diferentes, parece difícil processá-los em paralelo usando RK? A página da wikipedia parece sugerir que esses padrões têm o mesmo comprimento, embora a atualização dos hashes possa ser feita para diferentes comprimentos.

Hendrik Jan

Você está interessado em algum tipo de estudo teórico ou experiência prática?

Raphael

@ Raphael Academicamente, costumávamos aplicar o estudo teórico antes de provar isso empiricamente. Postei a pergunta aqui porque não espero respostas de programação. Eu preciso de uma resposta algorítmica lógica

Falcão

Respostas:

A análise assintótica do tempo de execução provavelmente não é a melhor ferramenta para escolher entre esses dois algoritmos: a análise assintótica ignora fatores constantes e os fatores constantes serão críticos aqui. Os dois algoritmos têm basicamente o mesmo tempo de execução assintótico, portanto, a análise assintótica provavelmente não é muito útil para escolher entre eles.

Em vez disso, a escolha certa entre os dois algoritmos é através da análise experimental. Identifique uma carga de trabalho representativa e, em seguida, avalie o desempenho de ambos os algoritmos em sua carga de trabalho, nos tipos de máquinas que você pretende usar na prática.

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

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

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

DW
fonte

No entanto, não consegui encontrar nenhuma comparação abrangente entre os dois algoritmos.

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

mas, ao escrever sua consulta implícita para "comparação abrangente", alguns artigos foram escritos comparando experimentalmente / empiricamente esses dois e outros algoritmos com dados reais e incluem análise / comparação dos prós / contras / trocas dos diferentes algoritmos, por exemplo:

Metodologias de correspondência de seqüências de padrões múltiplos: uma análise comparativa / Khan, Pateriya
UM ESTUDO COMPARATIVO DE ALGORITMOS DE CORRESPONDÊNCIA DE SEQUÊNCIAS BIOLÓGICAS / Pandiselvam, Marimuthu, Lawrance

vzn
fonte