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 se encuentran una o varias cadenas (también llamadas patrones) 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 de algoritmo de búsqueda de cadenas factible puede verse afectado por la codificación de la cadena. En particular, si se utiliza una codificación de ancho variable , entonces puede ser más lento encontrar el enésimo carácter, lo que quizás requiera 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 necesaria ]
El caso más básico de búsqueda de cuerdas involucra 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 apariciones de la aguja dentro del pajar. Por ejemplo, se podría buscar dentro de :
Algunos libros deben saborearse, otros deben tragarse y algunos pocos deben masticarse y digerirse.
Se podría solicitar la primera aparición de "to", que es la cuarta palabra; o todas las ocurrencias, 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, es posible que desee hacer coincidir la "aguja" sólo cuando consta de una (o más) palabras completas, tal vez definida como que no tiene otras letras inmediatamente adyacentes a cada lado. En ese caso, una búsqueda de "hew" o "low" debería fallar para la oración de ejemplo anterior, aunque esas cadenas literales aparezcan.
Otro ejemplo común es el de la "normalización". Para muchos propósitos, la búsqueda de una frase como "to be" debería tener éxito incluso en lugares donde hay algo más interpuesto entre "to" y "be":
Muchos sistemas de símbolos incluyen caracteres que son sinónimos (al menos para algunos propósitos):
Finalmente, para las cadenas que representan el lenguaje natural, se ven involucrados aspectos del propio lenguaje. Por ejemplo, es posible que deseemos encontrar todas las apariciones de una "palabra" a pesar de que tenga grafí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 capturar tanto la palabra inglesa americana "color" como su equivalente británico "color", en lugar de buscar dos cadenas literales diferentes, se podría utilizar una expresión regular como:
color
donde el "?" convencionalmente hace que el carácter anterior ("u") sea opcional.
Este artículo analiza principalmente 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 exacta máxima (MEM). [1] Dadas dos cadenas, las MEM son subcadenas comunes que no se pueden extender hacia la izquierda o hacia la derecha sin causar una falta de coincidencia. [2]
Una manera simple e ineficiente de ver dónde ocurre una cadena dentro de otra es verificar cada índice, uno por uno. Primero, vemos si hay una copia de la aguja comenzando 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, y así sucesivamente. En el caso normal, sólo 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 )
En este enfoque, se evita el retroceso mediante la construcción de un autómata finito determinista (DFA) que reconoce una cadena de búsqueda almacenada. Son costosos de construir (generalmente se crean usando la construcción powerset ) 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 .
Knuth-Morris-Pratt calcula un DFA que reconoce entradas con la cadena a buscar como sufijo, Boyer-Moore comienza a buscar desde el final de la aguja, por lo que generalmente puede avanzar una longitud completa de la aguja 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.
Los algoritmos de búsqueda más rápidos preprocesan el texto. Después de crear un índice de subcadena , por ejemplo un árbol de sufijos o una matriz de sufijos , las apariciones de un patrón se pueden encontrar rápidamente. Como ejemplo, se puede construir un árbol de sufijos en el tiempo, y todas las apariciones de un patrón se pueden encontrar en el 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.
Algunos métodos de búsqueda, por ejemplo la búsqueda de trigramas , tienen como objetivo encontrar una puntuación de "cercanía" entre la cadena de búsqueda y el texto en lugar de una "coincidencia/no coincidencia". A veces se les llama búsquedas "difusas" .
Los distintos algoritmos se pueden clasificar según la cantidad de patrones que utiliza cada uno.
En la siguiente compilación, m es la longitud del patrón, n la longitud del texto buscable y k = |Σ| es el tamaño del alfabeto.
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]
En la siguiente compilación, M es la longitud del patrón más largo, m su longitud total, n la longitud del texto buscable, o el número de apariciones.
Naturalmente, en este caso los patrones no se pueden enumerar de forma finita. Generalmente están representados por una gramática regular o una expresión regular .
Son posibles otros enfoques de clasificación. Uno de los más comunes utiliza el preprocesamiento como criterio principal.
Otro clasifica los algoritmos por su estrategia de coincidencia: [12]
{{citation}}: Enlace externo en |surname2=