En informática , los algoritmos de búsqueda de cadenas , a veces llamados algoritmos de coincidencia de cadenas , son una clase importante de algoritmos de cadenas que intentan encontrar un lugar donde una o varias cadenas (también llamadas patrones) se encuentran dentro de una cadena o texto más grande.
Un ejemplo básico de búsqueda de cadenas es cuando el patrón y el texto buscado son matrices de elementos de un alfabeto ( conjunto finito ) Σ. Σ puede ser un alfabeto de lenguaje humano, por ejemplo, las letras de la A a la Z y otras aplicaciones pueden usar un alfabeto binario (Σ = {0,1}) o un alfabeto de ADN (Σ = {A, C, G, T}) en bioinformática .
En la práctica, el método del algoritmo de búsqueda de cadenas factible puede verse afectado por la codificación de cadenas. En particular, si una codificación de anchura variable está en uso, entonces puede ser más lenta para encontrar el N º carácter, tal vez requieran un tiempo proporcional a N . Esto puede ralentizar significativamente algunos algoritmos de búsqueda. Una de las muchas soluciones posibles es buscar la secuencia de unidades de código, pero hacerlo puede producir coincidencias falsas a menos que la codificación esté diseñada específicamente para evitarlo. [ cita requerida ]
Descripción general
El caso más básico de búsqueda de cuerdas implica una cuerda (a menudo muy larga), a veces llamada pajar , y una cuerda (a menudo muy corta), a veces llamada aguja . El objetivo es encontrar una o más ocurrencias de la aguja dentro del pajar. Por ejemplo, se podría buscar a dentro:
Algunos libros deben probarse, otros para tragar y algunos pocos para masticar y digerir.
Se podría solicitar la primera aparición de "to", que es la cuarta palabra; o todas las apariciones, de las cuales hay 3; o la última, que es la quinta palabra desde el final.
Sin embargo, es muy común que se agreguen varias restricciones. Por ejemplo, uno podría querer hacer coincidir la "aguja" solo cuando consta de una (o más) palabras completas, tal vez definido como no tener otras letras inmediatamente adyacentes en ninguno de los lados. En ese caso, una búsqueda de "hew" o "low" debería fallar para la oración de ejemplo anterior, aunque esas cadenas literales se produzcan.
Otro ejemplo común es el de la "normalización". Para muchos propósitos, la búsqueda de una frase como "ser" debería tener éxito incluso en lugares donde hay algo más entre el "para" y el "ser":
- Más de un espacio
- Otros caracteres de "espacios en blanco" como tabulaciones, espacios sin interrupción, saltos de línea, etc.
- Con menos frecuencia, un guión o un guión suave
- En textos estructurados, etiquetas o incluso cosas arbitrariamente grandes pero "entre paréntesis", como notas al pie, números de lista u otros marcadores, imágenes incrustadas, etc.
Muchos sistemas de símbolos incluyen caracteres que son sinónimos (al menos para algunos propósitos):
- Los alfabetos latinos distinguen las minúsculas de las mayúsculas, pero para muchos propósitos se espera que la búsqueda de cadenas ignore la distinción.
- Muchos idiomas incluyen ligaduras , donde un carácter compuesto es equivalente a otros dos o más caracteres.
- Muchos sistemas de escritura involucran marcas diacríticas como acentos o puntos vocales , que pueden variar en su uso o tener una importancia variable en la coincidencia.
- Las secuencias de ADN pueden involucrar segmentos no codificantes que pueden ignorarse para algunos propósitos, o polimorfismos que no conducen a cambios en las proteínas codificadas, que pueden no contar como una verdadera diferencia para otros propósitos.
- Algunos idiomas tienen reglas en las que se debe usar un carácter o forma de carácter diferente al principio, al medio o al final de las palabras.
Finalmente, para las cadenas que representan el lenguaje natural, se involucran aspectos del propio lenguaje. Por ejemplo, uno podría desear encontrar todas las apariciones de una "palabra" a pesar de que tenga ortografías, prefijos o sufijos alternativos, etc.
Otro tipo de búsqueda más complejo es la búsqueda de expresiones regulares , donde el usuario construye un patrón de caracteres u otros símbolos, y cualquier coincidencia con el patrón debe cumplir con la búsqueda. Por ejemplo, para captar tanto la palabra "color" en inglés estadounidense como el equivalente británico "color", en lugar de buscar dos cadenas literales diferentes, se puede usar una expresión regular como:
color
donde el "?" convencionalmente hace que el carácter anterior ("u") sea opcional.
Este artículo analiza principalmente los algoritmos para los tipos más simples de búsqueda de cadenas.
Un problema similar introducido en el campo de la bioinformática y la genómica es la coincidencia máxima exacta (MEM). [1] Dadas dos cadenas, los MEM son subcadenas comunes que no pueden extenderse hacia la izquierda o hacia la derecha sin causar una falta de coincidencia. [2]
Ejemplos de algoritmos de búsqueda
Búsqueda de cadenas ingenua
Una forma simple e ineficiente de ver dónde ocurre una cadena dentro de otra es verificar cada lugar en el que podría estar, uno por uno, para ver si está allí. Entonces, primero vemos si hay una copia de la aguja en el primer carácter del pajar; si no, miramos para ver si hay una copia de la aguja comenzando en el segundo carácter del pajar; si no, miramos empezando por el tercer carácter, y así sucesivamente. En el caso normal, solo tenemos que mirar uno o dos caracteres para cada posición incorrecta para ver que es una posición incorrecta, por lo que en el caso promedio, esto toma O ( n + m ) pasos, donde n es la longitud de el pajar y m es la longitud de la aguja; pero en el peor de los casos, buscando una cadena como "aaaab" en una cadena como "aaaaaaaaab", se necesita O ( nm )
Búsqueda basada en autómatas de estado finito
En este enfoque, evitamos retroceder al construir un autómata finito determinista (DFA) que reconoce la cadena de búsqueda almacenada. Estos son costosos de construir, generalmente se crean usando la construcción del conjunto de energía, pero son muy rápidos de usar. Por ejemplo, el DFA que se muestra a la derecha reconoce la palabra "MAMÁ". Este enfoque se generaliza con frecuencia en la práctica para buscar expresiones regulares arbitrarias .
Talones
Knuth-Morris-Pratt calcula un DFA que reconoce las entradas con la cadena a buscar como sufijo, Boyer-Moore comienza a buscar desde el final de la aguja, por lo que normalmente puede avanzar una longitud de aguja completa en cada paso. Baeza – Yates realiza un seguimiento de si los caracteres j anteriores eran un prefijo de la cadena de búsqueda y, por lo tanto, se adapta a la búsqueda de cadenas difusas . El algoritmo bitap es una aplicación del enfoque de Baeza-Yates.
Métodos de índice
Los algoritmos de búsqueda más rápidos preprocesan el texto. Después de construir un índice de subcadena , por ejemplo, un árbol de sufijos o una matriz de sufijos , las ocurrencias de un patrón se pueden encontrar rápidamente. Como ejemplo, se puede construir un árbol de sufijos en tiempo, y todo las ocurrencias de un patrón se pueden encontrar en tiempo bajo el supuesto de que el alfabeto tiene un tamaño constante y todos los nodos internos del árbol de sufijos saben qué hojas hay debajo de ellos. Esto último se puede lograr ejecutando un algoritmo DFS desde la raíz del árbol de sufijos.
Otras variantes
Algunos métodos de búsqueda, por ejemplo , la búsqueda de trigramas , están destinados a encontrar una puntuación de "cercanía" entre la cadena de búsqueda y el texto en lugar de una "coincidencia / no coincidencia". En ocasiones, se denominan búsquedas "aproximadas" .
Clasificación de algoritmos de búsqueda
Clasificación por varios patrones
Los distintos algoritmos pueden clasificarse por el número de patrones que utiliza cada uno.
Algoritmos de patrón único
En la siguiente compilación, m es la longitud del patrón, n la longitud del texto de búsqueda, k = | Σ | es el tamaño del alfabeto y f es una constante introducida por las operaciones SIMD .
Algoritmo | Tiempo de preprocesamiento | Hora de coincidencia [1] | Espacio |
---|---|---|---|
Algoritmo ingenuo de búsqueda de cadenas | ninguno | Θ (mn) | ninguno |
Algoritmo optimizado de búsqueda de cadenas ingenuo (libc ++ y libstdc ++ string :: find) [3] [4] | ninguno | Θ (mn / f) | ninguno |
Algoritmo de Rabin-Karp | Θ (m) | promedio Θ (n + m), peor Θ ((n − m) m) | O (1) |
Algoritmo de Knuth-Morris-Pratt | Θ (m) | Θ (n) | Θ (m) |
Algoritmo de búsqueda de cadenas de Boyer-Moore | Θ (m + k) | mejor Ω (n / m), peor O (mn) | Θ (k) |
Algoritmo Bitap ( shift-or , shift-and , Baeza – Yates – Gonnet ; difuso; agrep) | Θ (m + k) | O (mn) | |
Algoritmo bidireccional de coincidencia de cadenas (glibc memmem / strstr) [5] | Θ (m) | O (n + m) | O (1) |
BNDM (Coincidencia DAWG no determinista hacia atrás) (fuzzy + regex; nrgrep) [6] | O (m) | En) | |
BOM (Coincidencia de Oracle hacia atrás) [7] | O (m) | O (mn) | |
Índice FM | En) | O (m) | En) |
- 1. ^ Los tiempos asintóticos se expresan mediante notación O, Ω y Θ .
El algoritmo de búsqueda de cadenas de Boyer-Moore ha sido el punto de referencia estándar para la literatura práctica de búsqueda de cadenas. [8]
Algoritmos que utilizan un conjunto finito de patrones
- Algoritmo de coincidencia de cadenas Aho-Corasick (extensión de Knuth-Morris-Pratt)
- Algoritmo Commentz-Walter (extensión de Boyer-Moore)
- Set-BOM (extensión de Backward Oracle Matching)
- Algoritmo de búsqueda de cadenas de Rabin-Karp
Algoritmos que utilizan un número infinito de patrones.
Naturalmente, los patrones no se pueden enumerar de manera finita en este caso. Suelen estar representados por una gramática regular o una expresión regular .
Clasificación por el uso de programas de preprocesamiento
Son posibles otros enfoques de clasificación. Uno de los usos más habituales es el preprocesamiento como criterio principal.
Texto no preprocesado | Texto preprocesado | |
---|---|---|
Patrones no preprocesados | Algoritmos elementales | Métodos de índice |
Patrones preprocesados | Motores de búsqueda construidos | Métodos de firma: [10] |
Clasificación por estrategias de emparejamiento
Otro clasifica los algoritmos por su estrategia de coincidencia: [11]
- Haga coincidir el prefijo primero (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)
- Haga coincidir el sufijo primero (Boyer-Moore y variantes, Commentz-Walter)
- Haga coincidir el mejor factor primero (BNDM, BOM, Set-BOM)
- Otra estrategia (Naïve, Rabin-Karp)
Ver también
- Alineación de secuencia
- Coincidencia de gráficos
- La coincidencia de patrones
- Coincidencia de patrones comprimidos
- Coincidencia de comodines
- Búsqueda de texto completo
Referencias
- ^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). "Software versátil y abierto para comparar genomas grandes" . Biología del genoma . 5 (2): R12. doi : 10.1186 / gb-2004-5-2-r12 . ISSN 1465-6906 . PMC 395750 . PMID 14759262 .
- ^ Khan, Zia; Bloom, Joshua S .; Kruglyak, Leonid; Singh, Mona (1 de julio de 2009). "Un algoritmo práctico para encontrar coincidencias máximas exactas en grandes conjuntos de datos de secuencia utilizando matrices de sufijos dispersos" . Bioinformática . 25 (13): 1609-1616. doi : 10.1093 / bioinformatics / btp275 . PMC 2732316 . PMID 19389736 .
- ^ Kumar, Aditya. "libc ++: Mejora el algoritmo string :: find" . Cite journal requiere
|journal=
( ayuda ) - ^ Kumar, Aditya. "libstdc ++: Mejora el algoritmo string :: find" . Cite journal requiere
|journal=
( ayuda ) - ^ Crochemore, Maxime; Perrin, Dominique (1 de julio de 1991). "Coincidencia de cadenas bidireccional" (PDF) . Revista de la ACM . 38 (3): 650–674. doi : 10.1145 / 116825.116845 . S2CID 15055316 .
- ^ Navarro, Gonzalo; Raffinot, Mathieu (1998). "Un enfoque de bits paralelos a los autómatas de sufijos: coincidencia rápida de cadenas extendidas" (PDF) . Coincidencia de patrones combinatorios . Apuntes de conferencias en informática. Springer Berlín Heidelberg. 1448 : 14–33. doi : 10.1007 / bfb0030778 . ISBN 978-3-540-64739-3.
- ^ Fan, H .; Yao, N .; Ma, H. (diciembre de 2009). "Variantes rápidas del algoritmo Backward-Oracle-Marching" (PDF) . 2009 Cuarta Conferencia Internacional sobre Computación de Internet para Ciencias e Ingeniería : 56–59. doi : 10.1109 / ICICSE.2009.53 . ISBN 978-1-4244-6754-9. S2CID 6073627 .
- ^ Hume; Domingo (1991). "Búsqueda rápida de cadenas" . Software: práctica y experiencia . 21 (11): 1221-1248. doi : 10.1002 / spe.4380211105 . S2CID 5902579 .
- ^ Melichar, Borivoj, Jan Holub y J. Polcar. Algoritmos de búsqueda de texto. Volumen I: Coincidencia de cadenas hacia adelante. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ .
- ^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Búsqueda rápida de cadenas basada en nGram sobre datos codificados con firmas algebraicas , 33a Conferencia internacional sobre bases de datos muy grandes (VLDB)
- ^ Gonzalo Navarro; Mathieu Raffinot (2008), Cadenas de coincidencia de patrones flexibles: algoritmos prácticos de búsqueda en línea para textos y secuencias biológicas , ISBN 978-0-521-03993-2
- RS Boyer y JS Moore, un algoritmo de búsqueda rápida de cadenas , Carom. ACM 20, (10), 262-272 (1977).
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , tercera edición. MIT Press y McGraw-Hill, 2009. ISBN 0-262-03293-7 . Capítulo 32: Correspondencia de cadenas, págs. 985-1013.
enlaces externos
- Enorme lista de enlaces de coincidencia de patrones Última actualización: 27/12/2008 20:18:38
- Lista grande (mantenida) de algoritmos de coincidencia de cadenas
- Lista NIST de algoritmos de coincidencia de cadenas
- StringSearch - algoritmos de coincidencia de patrones de alto rendimiento en Java - Implementaciones de muchos algoritmos de coincidencia de cadenas en Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
- StringsAndChars : implementaciones de muchos algoritmos de coincidencia de cadenas (para patrones únicos y múltiples) en Java
- Algoritmos de correspondencia exacta de cadenas : animación en Java, descripción detallada e implementación en C de muchos algoritmos.
- (PDF) Coincidencia aproximada de cadenas única y múltiple mejorada
- Kalign2: alineación múltiple de alto rendimiento de secuencias de proteínas y nucleótidos que permite características externas
- NyoTengu - algoritmo de coincidencia de patrones de alto rendimiento en C - Implementaciones de algoritmos de coincidencia de cadenas vectoriales y escalares en C