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 uno o varios las 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 A a 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 factible de búsqueda de cadenas puede verse afectado por la codificación de cadenas. En particular, si se usa una codificación de ancho variable, entonces puede ser más lento encontrar el carácter N, 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.

Resumen

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 ocurrencias de la aguja dentro del pajar. Por ejemplo, se podría buscar a dentro de:

Algunos libros deben ser probados, otros para ser tragados, y algunos para ser masticados y digeridos.

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.

Muy comúnmente, sin embargo, se agregan varias restricciones. Por ejemplo, uno podría querer hacer coincidir la "aguja" solo donde consiste en una (o más) palabras completas, tal vez definidas como no que tienen otras letras inmediatamente adyacentes a cada lado. En ese caso, una búsqueda de "hew" o "bajo" debería fallar para la oración de ejemplo anterior, aunque esas cadenas literales sí ocurran.

Otro ejemplo común implica la "normalización". Para muchos propósitos, una búsqueda de una frase como "to be" debería tener éxito incluso en lugares donde hay algo más interviniendo entre el "to" y el "ser":

• Más de un espacio
• Otros caracteres "espaciales blancos" como pestañas, espacios no rompedores, rompe líneas, etc.
• Menos comúnmente, un hifeno o blando hifeno
• En textos estructurados, etiquetas o incluso cosas arbitrariamente grandes pero "parentéticas" como notas de 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 de base latina distinguen la minúscula de la maleta superior, pero para muchos fines se espera que la búsqueda de cuerdas ignore la distinción.
• Muchos idiomas incluyen ligaduras, donde un personaje compuesto es equivalente a dos o más caracteres.
• Muchos sistemas de escritura implican marcas diacríticas tales como acentos o puntos de vocal, que pueden variar en su uso, o ser de diversa importancia en juego.
• Las secuencias de ADN pueden implicar segmentos de no codificación que pueden ser ignorados para algunos propósitos, o polimorfismos que conducen a ningún cambio en las proteínas codificadas, que pueden no contar como una verdadera diferencia para algunos otros propósitos.
• Algunos idiomas tienen reglas donde un carácter diferente o forma de carácter debe ser utilizado al principio, al medio o al final de las palabras.

Finalmente, para cadenas que representan lenguaje natural, se involucran aspectos del lenguaje mismo. Por ejemplo, uno podría desear encontrar todas las apariciones de una "palabra" a pesar de tener ortografías alternativas, prefijos o sufijos, etc.

Otro tipo de búsqueda más complejo es la búsqueda de expresiones regulares, en la que el usuario construye un patrón de caracteres u otros símbolos, y cualquier coincidencia con el patrón debería cumplir con la búsqueda. Por ejemplo, para captar tanto la palabra en inglés americano "color" y el equivalente británico "color", en lugar de buscar dos cadenas literales diferentes, se podría usar una expresión regular como:

¿Colou? r

¿dónde está 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 exacta máxima (MEM). Dadas dos cadenas, los MEM son subcadenas comunes que no se pueden extender hacia la izquierda o hacia la derecha sin causar una falta de coincidencia.

Ejemplos de algoritmos de búsqueda

Búsqueda de cadena ingenua

Una forma simple e ineficiente de ver dónde se encuentra una cadena dentro de otra es verificar cada índice, uno por uno. Primero, vemos si hay una copia de la aguja que comienza en el primer carácter del pajar; si no, miramos para ver si hay una copia de la aguja que comienza en el segundo carácter del pajar, y así sucesivamente. En el caso normal, solo tenemos que mirar uno o dos caracteres por cada posición incorrecta para ver que es una posición incorrecta, por lo que en el caso promedio, esto requiere 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 "aaaaaaaaaab", toma O(nm)

Búsqueda basada en autómatas de estado finito

En este enfoque, se evita el retroceso mediante la construcción de un autómata finito determinista (DFA) que reconoce la cadena de búsqueda almacenada. Estos son costosos de construir, generalmente se crean utilizando 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.

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 generalmente puede avanzar la longitud de una 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 de Baeza–Yates' Acercarse.

Métodos de indexación

Los algoritmos de búsqueda más rápidos preprocesan el texto. Después de construir un índice de subestring, por ejemplo un árbol de sufijo o matriz de sufijo, las ocurrencias de un patrón se pueden encontrar rápidamente. Como ejemplo, un árbol de sufijo puede ser construido en .. ()n){displaystyle Theta (n)} tiempo, y todo z{displaystyle z} ocurrencias de un patrón se puede encontrar en O()m){displaystyle O(m)} tiempo bajo la suposición de que el alfabeto tiene un tamaño constante y todos los nodos interiores en el árbol de sufijo saben qué hojas están debajo de ellos. Este último se puede lograr ejecutando un algoritmo DFS de la raíz del árbol de sufijo.

Otras variantes

Algunos métodos de búsqueda, por ejemplo, la búsqueda de trigramas, están destinados a encontrar una "cercanía" puntuación entre la cadena de búsqueda y el texto en lugar de una "coincidencia/no coincidencia". Estos a veces se denominan "difusos" búsquedas.

Clasificación de algoritmos de búsqueda

Clasificación por varios patrones

Los diversos algoritmos se pueden clasificar 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 buscable y k = |Σ | es el tamaño del alfabeto.

1.^ Los tiempos asintomáticos se expresan usando O, Ω, y Ø notación.

2.^ Usado para implementar el memmem y funciones de búsqueda strstr en las bibliotecas estándar glibc y musl C.

3.^ Se puede ampliar para manejar conjuntos de cuerdas aproximadas y (potencialmente infinitos) de patrones representados como idiomas regulares.

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.

Algoritmos que utilizan un conjunto finito de patrones

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.

Algoritmos que utilizan un número infinito de patrones

Naturalmente, los patrones no se pueden enumerar de forma finita en este caso. Normalmente se representan mediante una gramática regular o una expresión regular.

Clasificación por el uso de programas de preprocesamiento

Otros enfoques de clasificación son posibles. Uno de los usos más comunes es el preprocesamiento como criterio principal.

Clasificación por estrategias de coincidencia

Otro clasifica los algoritmos por su estrategia de coincidencia:

• Coincide primero con el prefijo (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
• Coincide con el sufijo primero (Boyer-Moore y variantes, Commentz-Walter)
• Coloque el mejor factor primero (BNDM, BOM, Set-BOM)
• Otra estrategia (Naïve, Rabin-Karp)