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

11

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 é O ( n m ) para RK. No entanto, o tempo de execução para o RK é O ( n + m ), o 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)

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:

4

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(n+m)cO(n+m)

O(n+m)O(nm)

DW
fonte
1

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

O(n+m)O(nm)

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:

vzn
fonte