Algoritmos de cadenas de caracteres
Los algoritmos de cadenas de caracteres procesan secuencias de símbolos —texto, ADN u otros datos lineales— para encontrar patrones, indexar textos grandes para una búsqueda rápida y alinear secuencias por similitud.
Definition
Los algoritmos de cadenas de caracteres son procedimientos y estructuras de datos que operan sobre cadenas de caracteres —secuencias finitas de caracteres tomadas de un alfabeto— para resolver problemas como la localización de patrones, la indexación para una búsqueda rápida y la medición o alineación de la similitud entre secuencias.
Scope
Esta área abarca algoritmos y estructuras de datos especializados en cadenas de caracteres: coincidencia exacta y aproximada de patrones, estructuras de índice (tries, árboles y arreglos de sufijos) que preprocesan el texto para consultas repetidas, y métodos de alineación de secuencias para comparar cadenas de caracteres. Se conecta con la programación dinámica (alineación), las estructuras de datos (árboles y arreglos) y las aplicaciones en biología computacional, recuperación de texto y procesamiento del lenguaje natural.
Sub-topics
Core questions
- ¿Cómo se puede localizar un patrón en un texto más rápido que la comparación ingenua carácter por carácter?
- ¿Cómo se preprocesa un texto grande para que muchas consultas posteriores sean rápidas?
- ¿Cómo se define y calcula la similitud entre dos cadenas de caracteres?
- ¿Cómo afectan el tamaño del alfabeto y la longitud de la cadena de caracteres a la eficiencia de los algoritmos de cadenas de caracteres?
- ¿Cómo se extienden los métodos de coincidencia exacta a la coincidencia aproximada o de múltiples patrones?
Key concepts
- alfabeto y cadena de caracteres
- coincidencia exacta de patrones
- Knuth-Morris-Pratt y Boyer-Moore
- tries
- árboles de sufijos y arreglos de sufijos
- distancia de edición
- alineación de secuencias
- coincidencia aproximada
Key theories
- Coincidencia exacta de patrones en tiempo lineal
- Al preprocesar el patrón para explotar la información de las coincidencias parciales, algoritmos como Knuth-Morris-Pratt y Boyer-Moore encuentran todas las ocurrencias de un patrón en tiempo lineal con respecto a la longitud del texto, evitando el costo cuadrático de la coincidencia ingenua.
- Estructuras de índice para texto
- Los árboles de sufijos y los arreglos de sufijos preprocesan un texto para que las consultas de patrones arbitrarios, las repeticiones y las preguntas sobre la subcadena común más larga puedan responderse rápidamente, intercambiando el costo de construcción por una búsqueda repetida rápida.
Clinical relevance
Los algoritmos de cadenas de caracteres son fundamentales para la búsqueda de texto y la bioinformática: la coincidencia de patrones impulsa las utilidades de búsqueda, los editores de texto y la detección de intrusiones; las estructuras de sufijos indexan los motores de búsqueda y las bases de datos genómicas; y la alineación de secuencias es fundamental para comparar secuencias de ADN, ARN y proteínas en biología molecular.
History
La coincidencia eficiente de cadenas de caracteres surgió en la década de 1970 con los algoritmos de Knuth-Morris-Pratt (1977) y Boyer-Moore (1977). Los árboles de sufijos (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) y, posteriormente, los arreglos de sufijos (Manber y Myers, 1990) proporcionaron una indexación potente, y el campo se expandió rápidamente a través de la biología computacional, como se describe en el texto de Gusfield de 1997.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- ¿Por qué preprocesar el patrón o el texto en lugar de buscar directamente?
- La coincidencia ingenua puede tomar un tiempo proporcional al producto de las longitudes del patrón y del texto. El preprocesamiento del patrón (como en Knuth-Morris-Pratt) permite una búsqueda en tiempo lineal, y el preprocesamiento del texto en un índice (árbol o arreglo de sufijos) permite que muchas consultas posteriores se ejecuten mucho más rápido, lo que resulta rentable cuando se busca repetidamente en el mismo texto.
- ¿Cómo se utilizan los algoritmos de cadenas de caracteres en biología?
- El ADN, el ARN y las proteínas se representan naturalmente como cadenas de caracteres, por lo que la coincidencia de patrones localiza motivos, las estructuras de sufijos indexan los genomas para una búsqueda rápida, y los algoritmos de alineación de secuencias cuantifican la similitud entre secuencias para inferir relaciones evolutivas y funciones.