Coincidencia de cadenas

La coincidencia de cadenas encuentra todas las ocurrencias de un patrón dentro de un texto; los algoritmos clásicos preprocesan el patrón para omitir comparaciones redundantes y lograr un tiempo de búsqueda lineal o sublineal.

Definition

La coincidencia de cadenas es el problema de encontrar todas las posiciones en un texto donde ocurre una cadena de patrón dada; un algoritmo de coincidencia exacta de cadenas reporta cada desplazamiento en el que el patrón se alinea idénticamente con una subcadena del texto.

Scope

Este tema cubre algoritmos de coincidencia exacta de patrón único —el método ingenuo, Knuth-Morris-Pratt, Boyer-Moore y el Rabin-Karp basado en hashing— junto con el preprocesamiento (funciones de fallo, tablas de desplazamiento, hashes rodantes) que los hace eficientes, y la extensión a la coincidencia de múltiples patrones a través del autómata de Aho-Corasick. La coincidencia aproximada y la búsqueda basada en índices se cubren en temas relacionados.

Core questions

• ¿Por qué la coincidencia ingenua toma un tiempo proporcional al producto de las longitudes del patrón y del texto?
• ¿Cómo evita el preprocesamiento del patrón reexaminar los caracteres del texto?
• ¿Cómo funcionan la función de fallo de Knuth-Morris-Pratt y las reglas de desplazamiento de Boyer-Moore?
• ¿Cómo utiliza Rabin-Karp el hashing para probar alineaciones rápidamente?
• ¿Cómo se extiende la coincidencia a muchos patrones simultáneamente?

Key concepts

• coincidencia ingenua
• algoritmo de Knuth-Morris-Pratt
• función de fallo
• algoritmo de Boyer-Moore
• reglas de carácter incorrecto y sufijo bueno
• algoritmo de Rabin-Karp
• hash rodante
• autómata de Aho-Corasick

Key theories

Función de fallo de Knuth-Morris-Pratt

Al precalcular, para cada prefijo del patrón, el prefijo propio más largo que también es un sufijo, el algoritmo de Knuth-Morris-Pratt desplaza el patrón de forma inteligente después de una falta de coincidencia y nunca reexamina los caracteres del texto, lo que permite una coincidencia en tiempo lineal.

Escaneo de derecha a izquierda de Boyer-Moore

Boyer-Moore compara el patrón desde su último carácter hacia atrás y utiliza reglas de carácter incorrecto y sufijo bueno para omitir grandes porciones del texto, logrando un rendimiento sublineal en el caso promedio en entradas típicas.

Clinical relevance

La coincidencia de cadenas es la base de herramientas e infraestructuras cotidianas: búsqueda en editores de texto y utilidades de línea de comandos, filtrado de contenido y escaneo de firmas de detección de intrusiones, detección de plagio y la localización de motivos en secuencias biológicas. La coincidencia de múltiples patrones escala esto a diccionarios de muchos patrones a la vez.

History

El algoritmo de Knuth-Morris-Pratt (publicado en 1977, desarrollado anteriormente) proporcionó el primer emparejador exacto de tiempo lineal ampliamente conocido, y Boyer y Moore (1977) introdujeron la coincidencia sublineal en el caso promedio el mismo año. El enfoque de hashing de Rabin y Karp y el autómata de múltiples patrones de Aho-Corasick (1975) ampliaron aún más el campo.

Key figures

• Donald Knuth
• James H. Morris
• Vaughan Pratt
• Robert Boyer
• J Strother Moore
• Michael Rabin
• Richard Karp

Seminal works

• knuth1977
• boyer1977
• cormen2009

Frequently asked questions

¿Qué algoritmo de coincidencia exacta de cadenas es el más rápido?

Depende de la entrada. Knuth-Morris-Pratt garantiza un tiempo lineal en el peor de los casos; Boyer-Moore suele ser el más rápido en la práctica en texto natural porque omite caracteres y se ejecuta de forma sublineal en promedio; Rabin-Karp destaca cuando se buscan muchos patrones o se realizan comparaciones de huellas dactilares. No hay un único ganador universal.

¿Cómo evita Rabin-Karp comparar cada carácter en cada posición?

Calcula el hash del patrón y de cada ventana de texto de la misma longitud utilizando un hash rodante que se actualiza en tiempo constante a medida que la ventana se desliza. Solo cuando los hashes coinciden, verifica los caracteres reales, por lo que la mayoría de las posiciones que no coinciden se rechazan mediante una única comparación económica.