Comparación entre el algoritmo Aho-Corasick y el algoritmo Rabin-Karp

11

Estoy trabajando en algoritmos de búsqueda de cadenas que admiten la búsqueda de patrones múltiples. Encontré dos algoritmos que parecen ser los candidatos más fuertes en términos de tiempo de ejecución, a saber, Aho-Corasick y Rabin-Karp . Sin embargo, no pude encontrar ninguna comparación exhaustiva entre los dos algoritmos. ¿Qué algoritmo es más eficiente? Además, ¿cuál es más adecuado para la computación paralela y la búsqueda de patrones múltiples? Finalmente, ¿cuál requiere menos recursos de hardware?

Para el algoritmo de CA, la fase de búsqueda toma tiempo , mientras que es para RK. Sin embargo, el tiempo de ejecución para RK es lo que lo hace similar a AC. Mi conclusión tentativa es que RK parece prácticamente mejor ya que no necesita tanta memoria como AC. ¿Es eso correcto?O ( n m ) O ( n + m )O(n+m)O(nm)O(n+m)

algorithms algorithm-analysis runtime-analysis strings Halcón
fuente
¿Todos sus patrones tienen la misma longitud?
Hendrik Jan
@HendrikJan No, diferentes patrones de longitud
Hawk
Si los patrones son de diferente longitud, ¿parece difícil procesarlos en paralelo usando RK? La página de wikipedia parece sugerir que estos patrones son de igual longitud, aunque la actualización de los hash se puede hacer para diferentes longitudes.
Hendrik Jan
¿Estás interesado en algún tipo de estudio teórico o experiencia práctica?
Raphael
@Raphael Academicamente, solíamos aplicar el estudio teórico primero antes de demostrarlo empíricamente. Publiqué la pregunta aquí porque no espero respuestas de programación. Necesito una respuesta algorítmica lógica
Hawk

Respuestas:

4

No es probable que el análisis de tiempo de ejecución asintótico sea la mejor herramienta para elegir entre estos dos algoritmos: el análisis asintótico ignora factores constantes, y los factores constantes serán críticos aquí. Los dos algoritmos tienen básicamente el mismo tiempo de ejecución asintótico, por lo que el análisis asintótico probablemente no sea muy útil para elegir entre ellos.

En cambio, la forma correcta de elegir entre los dos algoritmos es a través del análisis experimental. Identifique una carga de trabajo representativa y luego compare el rendimiento de ambos algoritmos en su carga de trabajo, en los tipos de máquinas que piensa usar en la práctica.

Por cierto, parece que podría tener una ligera confusión sobre el tiempo de funcionamiento asintótico de Rabin-Karp. Por un lado, dice que Rabin-Karp tiene tiempo de ejecución, pero luego, en la siguiente oración, dice que Rabin-Karp tiene tiempo de ejecución. Quizás esté confundido por la diferencia entre el tiempo de ejecución esperado (caso promedio) y el peor de los casos.O ( n + m )O(nm)O(n+m)

Dado que Rabin-Karp es aleatorio, el tiempo de ejecución esperado (caso promedio) es la métrica adecuada para predecir el rendimiento en la práctica en el mundo real. En particular, aquí el promedio se toma sobre la elección aleatoria de la función hash. Específicamente, no es un promedio tomado de la elección de cadenas. Incluso para la peor cadena y patrón posibles, el tiempo de ejecución promedio seguirá siendo . Con una función hash adecuada, la probabilidad de que el tiempo de ejecución sea mayor que es exponencialmente pequeña en . Para decirlo de otra manera (y ser un poco informal), solo hay una posibilidad exponencialmente pequeña de que Rabin-Karp tarde más quec ⋅ ( n + m ) c O ( n + m )O(n+m)c⋅(n+m)cO(n+m)hora. Ya tenemos que aceptar posibilidades exponencialmente pequeñas de que sucedan cosas malas; por ejemplo, hay una pequeña pero no nula posibilidad de que un rayo cósmico provoque un cambio de bits en su memoria que haga que el programa se repita para siempre. Entonces, preocuparse por esta posibilidad exponencialmente pequeña no tiene sentido.

Desde el punto de vista de la ingeniería, el tiempo de ejecución de Rabin-Karp es [o bien podría serlo]. Ignora el material ; eso no es realmente relevante para la práctica.O ( n m )O(n+m)O(nm)

DW
fuente
1

Sin embargo, no pude encontrar ninguna comparación exhaustiva entre los dos algoritmos.

Una pregunta como esta sobre el rendimiento relativo de dos algoritmos generalmente depende del caso promedio versus el peor de los casos, que depende de los datos reales. la respuesta teórica es que el algoritmo Aho-Corasick superará a Rabin-Karp en el caso de límite de datos grandes / asintóticamente, pero donde se alcanza ese límite es la implementación y la dependencia de los datos y la compensación entre búsquedas / tiempos de ejecución.O ( n m )O(n+m)O(nm)

pero en su consulta implícita de "comparación exhaustiva", algunos documentos se han escrito experimentalmente / empíricamente comparando estos dos y otros algoritmos en datos reales e incluyen análisis / comparación de los pros / contras / compensaciones de los diferentes algoritmos, por ejemplo:

vzn
fuente