algorithm - ¿Cuándo utilizarías KMP sobre BOYER-MOORE?
pattern-matching knuth-morris-pratt (1)
Actualmente estoy aprendiendo sobre los algoritmos de coincidencia de patrones y he encontrado estos dos algoritmos. Tengo las siguientes ideas generales:
KMP
- Compara el texto de izquierda a derecha
- Utiliza una matriz de fallos para cambiar inteligentemente
- toma O (m), donde m es la longitud del patrón, para calcular la matriz de falla
- toma O (m), espacio
- toma O (n), tiempo para buscar una cadena
BM
- Compara el patrón del último personaje
- Utiliza saltos de personajes malos y saltos de sufijos buenos.
- toma O (m + tamaño del alfabeto) para calcular tablas
- toma O (m + tamaño del alfabeto), espacio
- Toma O (n), pero generalmente es mejor buscar
Encontré la siguiente pregunta que provocó esta pregunta (Verdadero o Falso):
El algoritmo Knuth-Morris-Pratt (KMP) es una buena opción si queremos buscar el mismo patrón repetidamente en muchos textos diferentes.
Entonces, creo que la respuesta es verdadera solo porque se supone que cada vez que se ejecuta el algoritmo en un texto diferente, el preprocesamiento es solo O (n) donde para BM es O (n + tamaño del alfabeto). Sin embargo, no estoy seguro de si estoy asumiendo correctamente que cada vez que se vuelve a ejecutar el algoritmo, se vuelve a calcular una nueva tabla. Porque digamos que el texto siempre cae en el abecedario del inglés. Solo necesitaría calcular la tabla una vez y simplemente reutilizar la tabla. Entonces, al final del día, ¿la respuesta a esta pregunta dependerá del hecho de que todos los algoritmos se ejecutan en un texto que está contenido en el mismo alfabeto o hay algún otro factor que pueda afectarlo?
En teoría, ambos algoritmos tendrán un rendimiento "similar"; KMP hará aproximadamente 2n comparaciones en la fase de búsqueda y Boyer-Moore hará aproximadamente 3n comparaciones en la fase de búsqueda en el peor de los casos . En ningún caso, debe repetir el preprocesamiento cuando obtenga un nuevo texto.
Pero la respuesta real es que no debe usar ninguno de ellos en la práctica.
El almacenamiento auxiliar lineal que necesitan ambos algoritmos conduce a un rendimiento considerablemente más áspero en las arquitecturas modernas debido a todos los accesos de memoria adicionales.
Sin embargo, las ideas detrás de Boyer-Moore y KMP respaldan la mayoría de los algoritmos de emparejamiento de cadenas rápidos. Algo así como la idea de "función de falla" de KMP es usado por cada algoritmo de emparejamiento de cadenas prácticamente efectivo que conozco; Resulta que puede calcular una "función de falla" subóptima para un patrón sobre la marcha que aún le da una coincidencia de tiempo lineal mientras que solo necesita espacio adicional constante. Boyer-Moore es más rápido que lineal en el "caso promedio" de comparar un patrón fijo con un ruido aleatorio, y esto se confirma en muchas situaciones prácticas.