c++ - sunday - ¿Cuál es un mejor algoritmo de búsqueda de cadenas? ¿Boyer-Moore o Boyer Moore Horspool?

boyer moore sunday

Question

El algoritmo de Boyer Moore tiene un tiempo de preproceso de Θ (m + | Σ |) y un tiempo de coincidencia de Ω (n / m), O (n). Entiendo que Boyer Moore Horspool es un avance de Simplified Boyer Moore en sí, sin embargo, su complejidad promedio es O (N) y el peor caso O (MN) según este artículo de Wikipedia . Entonces, en el peor de los casos, debería ser más lento que el algoritmo de Boyer Moore. Pero esta encuesta clásica de la Universidad de Chile muestra que el Horspool Boyer-Moore supera a Boyer Moore casi todo el tiempo. ¡Estoy confundido! ¿Cuál debería usar (tanto para patrones pequeños como grandes) para la búsqueda de cadenas y qué algoritmo tiene una mayor importancia en el mundo práctico (solo soy un estudiante de informática)?

Answer 1

La palabra clave es "casi". El peor de los casos puede ser por un número de casos que va desapareciendo. El comportamiento promedio en la vida real y el comportamiento asintótico también están bastante débilmente relacionados. El mejor comportamiento de casos de Boyer-Moore-Horspool es el mismo que el de Boyer-Moore. El peor caso para Boyer-Moore-Horspool es bastante peor que para Boyer-Moore. Para un uso típico, Boyer-Moore-Horspool tiende a ser casi lo mismo que Boyer-Moore, pero con un poco más (menos) gastos generales y de inicialización.

¿Cuál usar? Depende de tus objetivos y de lo que esperas en cuanto a la forma de buscar patrones y texto. Ninguno de los dos es particularmente difícil de implementar, entonces ¿por qué no hacer ambos y comparar los resultados usted mismo? (¿Ves lo que sucede cuando admites que eres un estudiante? ¡Obtienes una tarea! :))