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?
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.
fonte
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
fonte