Algoritmo de búsqueda de cadenas

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 búsqueda de un algoritmo de cadena 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":

• Más de un espacio
• Otros caracteres de "espacio en blanco", como tabulaciones, espacios indivisibles, saltos de línea, etc.
• Con menos frecuencia, un guion o guión suave.
• En textos estructurados, etiquetas o incluso elementos arbitrariamente grandes pero "entre paréntesis", como notas a pie de página, 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 basados ​​en el latín distinguen entre minúsculas y 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 dos o más caracteres.
• Muchos sistemas de escritura implican marcas diacríticas , como acentos o puntos vocálicos , que pueden variar en su uso o tener distinta importancia en la coincidencia.
• Las secuencias de ADN pueden incluir segmentos no codificantes que pueden ignorarse para algunos propósitos, o polimorfismos que no producen cambios en las proteínas codificadas, lo que puede no considerarse una verdadera diferencia para algunos otros propósitos.
• Algunos idiomas tienen reglas donde se debe utilizar un carácter o una forma de carácter diferente al principio, en el medio o al final de las palabras.

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 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. ${\displaystyle \Theta (n)}$${\displaystyle z}$${\displaystyle O(m)}$

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.

1. ^ Los tiempos asintóticos se expresan utilizando la notación O, Ω y Θ .

2. ^ Se utiliza para implementar las funciones de búsqueda memmem y strstr en las bibliotecas estándar de C glibc ^[6] y musl ^[7] .

3. ^ Se puede ampliar para manejar coincidencias aproximadas de cadenas y conjuntos (potencialmente infinitos) de patrones representados como lenguajes regulares . ^{[ cita requerida ]}

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]

• Coincida primero con el prefijo (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
• Coincida primero con el sufijo (Boyer–Moore y variantes, Commentz-Walter)
• Haga coincidir primero el mejor factor (BNDM, BOM, Set-BOM)
• Otra estrategia (ingenua, Rabin–Karp, vectorizada)

• Alineación de secuencias
• Correspondencia de gráficos
• Coincidencia de patrones
• Coincidencia de patrones comprimidos
• Comodines coincidentes
• Búsqueda de texto completo

• RS Boyer y JS Moore, Un algoritmo rápido de búsqueda 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: Coincidencia de cadenas, págs. 985–1013. 

• Lista enorme 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 del 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 individuales y múltiples) en Java
• Algoritmos de coincidencia exacta de cadenas: animación en Java, descripción detallada e implementación en C de muchos algoritmos.
• (PDF) Coincidencia de cadenas aproximadas simples y múltiples mejorada Archivado el 11 de marzo de 2017 en Wayback Machine
• Kalign2: alineamiento 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 escalares y vectoriales en C