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 un 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 , puede resultar más lento encontrar el carácter N , y tal vez se necesite 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 en su lugar, pero hacerlo puede producir coincidencias falsas a menos que la codificación esté diseñada específicamente para evitarlo. [ cita requerida ]
El caso más básico de búsqueda de cadenas implica una cadena (a menudo muy larga), a veces llamada pajar , y una cadena (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 to dentro de:
Algunos libros son para saborearlos, otros para tragarlos y algunos para masticarlos y digerirlos.
Se podría solicitar la primera ocurrencia 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, se podría querer encontrar la palabra "needle" solo cuando esté compuesta por una (o más) palabras completas, tal vez definidas como aquellas que no tienen otras letras inmediatamente adyacentes a ninguno de los lados. En ese caso, una búsqueda de "hew" o "low" debería fallar para la oración del ejemplo anterior, aunque esas cadenas literales sí aparezcan.
Otro ejemplo común es el de la "normalización". Para muchos propósitos, una búsqueda de una frase como "ser" debería tener éxito incluso en lugares donde hay algo más entre "ser" y "ser":
Muchos sistemas de símbolos incluyen caracteres que son sinónimos (al menos para algunos propósitos):
Por último, en el caso de cadenas que representan lenguaje natural, intervienen aspectos del lenguaje en sí. Por ejemplo, se podría desear encontrar todas las apariciones de una "palabra" a pesar de que tenga otras formas de escribirla, prefijos o sufijos, etc.
Otro tipo de búsqueda más complejo es la búsqueda mediante expresiones regulares , en la que el usuario construye un patrón de caracteres u otros símbolos y cualquier coincidencia con el patrón debe satisfacer la búsqueda. Por ejemplo, para capturar tanto la palabra en inglés americano "color" como su equivalente británico "colour", 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 precedente ("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 el de la correspondencia 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 un desajuste. [2]
Una forma sencilla e ineficiente de ver dónde aparece una cadena dentro de otra es comprobar en cada índice, uno por uno. Primero, vemos si hay una copia de la aguja que comience en el primer carácter del pajar; si no, miramos para ver si hay una copia de la aguja que comience en el segundo carácter del pajar, 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 lleva O ( n + m ) pasos, donde n es la longitud del pajar y m es la longitud de la aguja; pero en el peor de los casos, buscar una cadena como "aaaab" en una cadena como "aaaaaaaaab", lleva 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. Estos son costosos de construir (normalmente se crean mediante la construcción de conjuntos potenciados ), pero son muy rápidos de usar. Por ejemplo, el DFA que se muestra a la derecha reconoce la palabra "MOMMY". Este enfoque se suele generalizar en la práctica para buscar expresiones regulares arbitrarias .
Knuth–Morris–Pratt calcula un DFA que reconoce las entradas con la cadena que se va a buscar como sufijo; Boyer–Moore comienza la búsqueda desde el extremo de la aguja, por lo que normalmente puede saltar hacia adelante una longitud de aguja completa en cada paso. Baeza–Yates realiza un seguimiento de si los caracteres j anteriores fueron un prefijo de la cadena de búsqueda y, por lo tanto, es adaptable 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 construir un índice de subcadena , por ejemplo, un árbol de sufijos o una matriz de sufijos , se pueden encontrar rápidamente las ocurrencias de un patrón. Por ejemplo, se puede construir un árbol de sufijos a tiempo y se pueden encontrar todas las ocurrencias de un patrón a tiempo bajo el supuesto de que el alfabeto tiene un tamaño constante y todos los nodos internos en el árbol de sufijos saben qué hojas están 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, como por ejemplo la búsqueda de trigramas , tienen como objetivo encontrar un índice de "proximidad" entre la cadena de búsqueda y el texto, en lugar de una "coincidencia/no coincidencia". A veces se las denomina búsquedas "difusas" .
Los distintos algoritmos se pueden clasificar según el número 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 ocurrencias.
Naturalmente, en este caso los patrones no se pueden enumerar de forma finita. Se representan normalmente mediante una gramática regular o una expresión regular .
Existen otros métodos de clasificación posibles. Uno de los más comunes utiliza el preprocesamiento como criterio principal.
Otro clasifica los algoritmos por su estrategia de emparejamiento: [12]
{{citation}}: Enlace externo en |surname2=