algorithm - rabin - como funciona el algoritmo kmp
¿Cuáles son las principales diferencias entre los algoritmos de búsqueda de Knuth-Morris-Pratt y Boyer-Moore? (3)
¿Cuáles son las principales diferencias entre el algoritmo de búsqueda Knuth-Morris-Pratt y el algoritmo de búsqueda Boyer-Moore ?
Sé que KMP busca Y en X, tratando de definir un patrón en Y, y guarda el patrón en un vector. También sé que BM funciona mejor para palabras pequeñas, como ADN (ACTG).
¿Cuáles son las principales diferencias en cómo funcionan? ¿Cuál es más rápido? ¿Cuál es menos codicioso de la computadora? En que casos?
En una explicación aproximada
El enfoque de Boyer-Moore es tratar de hacer coincidir el último carácter del patrón en lugar del primero con la suposición de que si no hay coincidencia al final no es necesario tratar de hacer coincidir al principio. Esto permite "grandes saltos", por lo tanto BM funciona mejor cuando el patrón y el texto que está buscando se parecen al "texto natural" (es decir, inglés)
Knuth-Morris-Pratt busca ocurrencias de una "palabra" W dentro de una "cadena de texto" S principal empleando la observación de que cuando se produce un desajuste, la palabra en sí misma incorpora información suficiente para determinar dónde podría comenzar la siguiente coincidencia, evitando así el re -examen de personajes previamente coincidentes. (Fuente: Wiki )
Esto significa que KMP es más adecuado para juegos pequeños como ADN (ACTG)
La técnica Boyer-Moore combina los personajes de derecha a izquierda, funciona bien en patrones largos. knuth moris pratt coincide con los personajes de izquierda a derecha, trabaja rápido en patrones cortos.
La página web de UTexas de Moore recorre ambos algoritmos paso a paso (también proporciona varias fuentes técnicas):
De acuerdo con el hombre mismo,
El algoritmo clásico de Boyer-Moore adolece del fenómeno de que tiende a no funcionar tan eficientemente en alfabetos pequeños como el ADN. La distancia de omisión tiende a dejar de crecer con la longitud del patrón porque las subcadenas vuelven a producirse con frecuencia. Al recordar más de lo que ya se ha emparejado, uno puede obtener saltos más grandes a través del texto. Incluso se puede organizar `` la memoria perfecta '''' y así observar a cada personaje al menos una vez, mientras que el algoritmo de Boyer-Moore, aunque es lineal, puede inspeccionar un personaje del texto varias veces. Esta idea de recordar más ha sido explorada en la literatura por otros. Sufre de la necesidad de tablas muy grandes o máquinas de estado.
Sin embargo, ha habido algunas modificaciones de BM que han viabilizado la búsqueda de pequeños alfabetos.