string - morris - ¿Cuál es la teoría detrás del algoritmo de coincidencia de patrones KMP?
knuth morris pratt geeksforgeeks (2)
¿Cuál es la base teórica del algoritmo de coincidencia de patrones KMP?
Entiendo el algoritmo en sí, pero no entiendo cómo Knuth, Morris y Pratt inventaron este algoritmo.
¿Hubo alguna prueba matemática?
¿Puedes dar un enlace por favor?
El algoritmo de coincidencia KMP se basa en autómatas finitos y funciona mediante la construcción implícita de la tabla de transición para un autómata que coincide con la cadena. Usando un preprocesamiento de tiempo lineal muy inteligente de la cadena para buscar, se puede construir un autómata coincidente, y luego se puede simular el autómata en la cadena para buscar en tiempo lineal. El resultado neto es un algoritmo de tiempo lineal para la coincidencia de cadenas.
El autómata que se construye funciona al tener un estado para cada cantidad de la cadena que se ha emparejado hasta ahora. De forma predeterminada, las transiciones son tales que, al hacer coincidir el siguiente carácter, se avanza al siguiente estado en la máquina y se leen las transiciones de carácter no válido al principio. Sin embargo, ciertas partes de la cadena para buscar pueden compartir alguna estructura superpuesta, por lo que se agregan algunas nuevas transiciones que llevan al autómata a un estado anterior (pero no al primero) cuando se lee un carácter.
Este algoritmo es generalizado por el algoritmo Aho-Corasick, que construye un autómata más complejo para buscar múltiples cadenas a la vez.
Tengo una implementación de este algoritmo en mi sitio personal que contiene una extensa discusión de los detalles reales de cómo funciona el algoritmo, incluida una prueba de corrección, una intuición más formal detrás del algoritmo y una explicación de cómo derivar el algoritmo desde los primeros principios. Me tomó un tiempo armarlo, pero espero que sea un buen recurso para aprender más sobre el algoritmo.
¡Espero que esto ayude!
Morris descubrió el algoritmo a partir de los primeros principios, pero Knuth aprendió de forma independiente sobre un teorema debido a Stephen A. Cook que los autómatas de empuje bidireccionales deterministas podrían simularse en tiempo lineal y extrajeron una versión anterior de "KMP" especializando la simulación a un cadena de autómata a juego. Pratt contribuyó con una mejora de la eficiencia. Ver el recuento de Knuth .