Hispanopedia Wiki
Articulo de referencia

Algoritmo de búsqueda de cadenas

Un algoritmo de búsqueda de cadenas , a veces llamado algoritmo de coincidencia de cadenas , es un algoritmo que busca en un texto fragmentos que coincidan con un patrón determi...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo de búsqueda de cadenas , a veces llamado algoritmo de coincidencia de cadenas , es un algoritmo que busca en un texto fragmentos que coincidan con un patrón determinado.

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 un 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 cadenas factibles puede verse afectado por la codificación de la cadena. En particular, si se utiliza una codificación de ancho variable , la búsqueda del carácter N puede ser más lenta, requiriendo quizás 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 esto puede generar coincidencias falsas a menos que la codificación esté diseñada específicamente para evitarlo.

Descripción general

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 " to" dentro de:

Algunos libros deben saborearse, otros tragarse y unos pocos masticarse y digerirse.

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 añadan diversas restricciones. Por ejemplo, se podría querer que la palabra "aguja" coincida únicamente con las palabras completas, definidas, por ejemplo, como aquellas que no tienen otras letras inmediatamente adyacentes a ambos lados. En ese caso, una búsqueda de "hew" o "low" no debería coincidir con la frase de ejemplo anterior, aunque esas cadenas literales aparezcan.

Otro ejemplo común tiene que ver con 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 que se interpone entre "to" y "be":

  • Más de un espacio
  • Otros caracteres de "espacio en blanco", como tabulaciones, espacios de no separación, saltos de línea, etc.
  • Con menos frecuencia, un guion o un guion suave.
  • En textos estructurados, etiquetas o incluso elementos 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 basados ​​en el alfabeto latino distinguen entre mayúsculas y minúsculas, pero para muchos fines se espera que la búsqueda de cadenas ignore esta distinción.
  • Muchos idiomas incluyen ligaduras , donde un carácter compuesto equivale a dos o más caracteres.
  • Muchos sistemas de escritura incluyen signos diacríticos como acentos o puntos vocálicos , cuyo uso puede variar o cuya importancia a la hora de realizar la correspondencia puede ser variable.
  • Las secuencias de ADN pueden incluir segmentos no codificantes que pueden ignorarse para ciertos fines, o polimorfismos que no producen ningún cambio en las proteínas codificadas, lo que puede no considerarse una diferencia real para otros fines.
  • Algunos idiomas tienen reglas que exigen el uso de un carácter o una forma de carácter diferente al principio, en medio o al final de las palabras.

Finalmente, para las cadenas que representan lenguaje natural, entran en juego aspectos del propio lenguaje. Por ejemplo, se podría desear encontrar todas las ocurrencias de una "palabra" a pesar de que tenga ortografías alternativas, prefijos o sufijos, etc.

Otro tipo de búsqueda más complejo es la búsqueda mediante expresiones regulares , donde el usuario construye un patrón de caracteres u otros símbolos, y cualquier coincidencia con dicho patrón debería satisfacer la búsqueda. Por ejemplo, para encontrar 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 usar una expresión regular como la siguiente:

color

donde el signo de interrogación convencionalmente hace que el carácter precedente ("u") sea opcional.

Este artículo trata principalmente sobre algoritmos para los tipos más sencillos de búsqueda de cadenas de texto.

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 discrepancia. [ 2 ]

Ejemplos de algoritmos de búsqueda

Una forma simple 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 comienza en el primer carácter del pajar; si no, buscamos 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 toma 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", toma O ( nm )

En este enfoque, se evita el retroceso mediante la construcción de un autómata finito determinista (AFD) que reconoce una cadena de búsqueda almacenada. Su construcción es costosa (generalmente se crean mediante la construcción de conjuntos potencia ), pero su uso es muy rápido. Por ejemplo, el AFD que se muestra a la derecha reconoce la palabra "MOMMY". Este enfoque se generaliza con frecuencia en la práctica para buscar expresiones regulares arbitrarias .

Esbozos

El algoritmo Knuth-Morris-Pratt calcula un autómata finito determinista (AFD) que reconoce entradas con la cadena a buscar como sufijo. El algoritmo Boyer-Moore comienza la búsqueda desde el final de la cadena, por lo que generalmente puede avanzar una longitud de cadena completa en cada paso. El algoritmo Baeza-Yates registra si los j caracteres anteriores eran 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.

Métodos de indexación

Los algoritmos de búsqueda más rápidos preprocesan el texto. Después de construir un índice de subcadenas , 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Θ(norte){\displaystyle \Theta (n)}tiempo y todoz{\displaystyle z}Las ocurrencias de un patrón se pueden encontrar enO(metro){\displaystyle O(m)}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, como la búsqueda de trigramas , buscan determinar el grado de similitud entre la cadena de búsqueda y el texto, en lugar de una simple coincidencia o no coincidencia. A veces se les denomina búsquedas "aproximadas" .

Clasificación de algoritmos de búsqueda

Clasificación según una serie de patrones

Los distintos algoritmos pueden clasificarse según 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 que se puede buscar 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 extender para manejar coincidencias de cadenas aproximadas y conjuntos de patrones (potencialmente infinitos) representados como lenguajes regulares .

El algoritmo de búsqueda de cadenas de Boyer-Moore ha sido el estándar de referencia para la literatura práctica sobre búsqueda de cadenas. [ 8 ]

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 que se puede buscar, o el número de ocurrencias.

Algoritmos que utilizan un número infinito de patrones

Naturalmente, en este caso los patrones no pueden enumerarse de forma finita. Suelen representarse mediante una gramática regular o una expresión regular .

Clasificación mediante el uso de programas de preprocesamiento

Existen otros enfoques de clasificación posibles. Uno de los más comunes utiliza el preprocesamiento como criterio principal.

Clasificación mediante estrategias de coincidencia

Otro clasifica los algoritmos según su estrategia de coincidencia: [ 12 ]

  • Primero, haga coincidir el prefijo (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
  • Primero, haga coincidir el sufijo (Boyer-Moore y variantes, Commentz-Walter).
  • Emparejar primero el mejor factor (BNDM, BOM, Set-BOM)
  • Otras estrategias (ingenua, Rabin-Karp, vectorizada)

Coincidencia de cadenas en tiempo real

En la comparación de cadenas en tiempo real, se requiere que el comparador genere una respuesta después de leer cada carácter del texto, indicando si se trata del último carácter de una coincidencia. La respuesta debe proporcionarse en un tiempo constante. Los requisitos de preprocesamiento varían: se puede permitir un preprocesamiento O( m ) después de leer el patrón (pero antes de leer el texto), o se puede plantear un requisito más estricto según el cual el comparador también debe hacer una pausa de como máximo un tiempo constante después de leer cualquier carácter del patrón (incluido el último). Para la versión más flexible, si no importa que el tiempo de preprocesamiento y los requisitos de memoria dependan del tamaño del alfabeto, la comparación mediante autómatas proporciona una solución en tiempo real. Zvi Galil desarrolló un método para convertir ciertos algoritmos en algoritmos en tiempo real y lo aplicó para producir una variante del comparador KMP que se ejecuta en tiempo real bajo el requisito estricto. [ 13 ]

Búsqueda de cadenas con "no importa"

En esta versión del problema de búsqueda de cadenas, hay un símbolo especial, ø (léase: no importa), que puede coincidir con cualquier otro símbolo (incluido otro ø). Los símbolos de "no importa" pueden aparecer tanto en el patrón como en el texto. En 2002, se desarrolló un algoritmo para este problema que se ejecuta enO(norteregistro⁡metro){\displaystyle O(n\log m)}Richard Cole y Ramesh Hariharan han dedicado tiempo a mejorar una solución de 1973 de Fischer y Paterson que tiene complejidad.O(norteregistro⁡metroregistro⁡k){\displaystyle O(n\log m\log k)}donde k es el tamaño del alfabeto. [ 14 ] Clifford y Clifford propusieron otro algoritmo, supuestamente más simple . [ 15 ]

Véase también

Referencias

  1. ↑ 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" . Genome Biology . 5 (2): R12. doi : 10.1186/gb-2004-5-2-r12 . ISSN 1465-6906 . PMC 395750. PMID 14759262 .   
  2. ↑ Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). "Un algoritmo práctico para encontrar coincidencias exactas máximas en grandes conjuntos de datos de secuencias utilizando matrices de sufijos dispersos" . Bioinformatics . 25 ( 13): 1609– 1616. doi : 10.1093/bioinformatics/btp275 . PMC 2732316. PMID 19389736 .  
  3. ↑ Crochemore, Maxime; Perrin, Dominique (1 de julio de 1991). "Coincidencia de cadenas bidireccional" ( PDF) . Journal of the ACM . 38 (3): 650– 674. doi : 10.1145/116825.116845 . S2CID 15055316. Archivado (PDF) del original el 24 de noviembre de 2021. Recuperado el 5 de abril de 2019 . 
  4. ↑ Navarro, Gonzalo; Raffinot, Mathieu (1998). "Un enfoque bit-paralelo para autómatas de sufijos: coincidencia rápida de cadenas extendidas" (PDF) . Combinatorial Pattern Matching . Lecture Notes in Computer Science. Vol. 1448. Springer Berlin Heidelberg. pp. 14–33 . doi : 10.1007/bfb0030778 . ISBN   978-3-540-64739-3. Archivado (PDF) del original el 05-01-2019 . Recuperado el 22-11-2019 .
  5. ↑ Fan, H.; Yao, N.; Ma, H. (diciembre de 2009). «Variantes rápidas del algoritmo de marcha hacia atrás con oráculo» (PDF) . Cuarta Conferencia Internacional de 2009 sobre Computación en Internet para la Ciencia y la Ingeniería . págs. 56–59 . doi : 10.1109/ICICSE.2009.53 . ISBN  978-1-4244-6754-9. S2CID 6073627 . Archivado del original el 10-05-2022 . Recuperado el 22-11-2019 . 
  6. ↑ "glibc/string/str-two-way.h" . Archivado del original el 20 de septiembre de 2020. Consultado el 22 de marzo de 2022 .
  7. ↑ "musl/src/string/memmem.c" . Archivado del original el 1 de octubre de 2020. Consultado el 23 de noviembre de 2019 .
  8. ↑ Hume; Sunday (1991). "Búsqueda rápida de cadenas". Software: Práctica y experiencia . 21 (11): 1221– 1248. doi : 10.1002/spe.4380211105 . S2CID 5902579 . 
  9. ↑ Commentz-Walter, Beate (1979). Un algoritmo de coincidencia de cadenas rápido en promedio (PDF) . Coloquio internacional sobre autómatas, lenguajes y programación . LNCS . Vol. 71. Graz, Austria: Springer. pp. 118–132 . doi : 10.1007/3-540-09510-1_10 . ISBN   3-540-09510-1Archivado del original (PDF) el 10 de octubre de 2017.
  10. ↑ 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/ Archivado el 4 de marzo de 2016 en Wayback Machine .
  11. ↑ Litwin, Witold; Mokadem, Riad; Rigaux, Philippe; Schwarz, Thomas (2007), Búsqueda rápida de cadenas basada en n-gramas sobre datos codificados mediante firmas algebraicas (PDF) , Conferencia internacional sobre bases de datos muy grandes
  12. ↑ Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences , Cambridge University Press, ISBN 978-0-521-03993-2
  13. ↑ Galil, Zvi (1981). "Comparación de cadenas en tiempo real". Journal of the ACM . 28 (1): 134– 149. doi : 10.1145/322234.322244 .
  14. ↑ Cole, Richard; Hariharan, Ramesh (2002). "Verificación de coincidencias candidatas en coincidencias dispersas y con comodines". Actas del trigésimo cuarto simposio anual de la ACM sobre Teoría de la Computación . págs. 592–601 . 
  15. ↑ Clifford, Peter; Clifford, Raphaël (enero de 2007). "Coincidencia simple determinista con comodines". Information Processing Letters . 101 (2): 53– 54. doi : 10.1016/j.ipl.2006.08.002 .

Lecturas adicionales

  • Gran lista de enlaces que coinciden con patrones. Última actualización: 27/12/2008 20:18:38
  • Lista extensa (y actualizada) de algoritmos de búsqueda de cadenas.
  • Lista de algoritmos de búsqueda de cadenas del NIST
  • 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 simples 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 aproximada de cadenas simples y múltiples mejorada. Archivado el 11/03/2017 en Wayback Machine.
  • 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.
  • Nathaniel K. Brown, et al.: "KeBaB: ruptura basada en k-meros para encontrar MEM largos", arXiv:2502.20338v3 (09 de junio de 2025).
Obtenido de " https://en.wikipedia.org/w/index.php?title=String-searching_algorithm&oldid=1355713810 "
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Diagrama de datos de cadena en computación. Muestra la palabra "ejemplo" con cada letra en un cuadro separado. La palabra "Cadena" está arriba y hace referencia a la oración completa. La etiqueta "Carácter" está debajo y apunta a un cuadro individual.Cadena (informática)En programación informática , una cadena es tradicionalmente una secuencia de caracteres , ya sea como una constante literal o como algún tipo de v...Array (data structure)In computer science , an array is a data structure consisting of a collection of elements ( values or variables ), of same memory size, each identi...{\displaystyle \{v_{1},v_{2},\ldots \}}Alfabeto (lenguajes formales)En la teoría del lenguaje formal , un alfabeto , a menudo llamado vocabulario en el contexto de símbolos terminales y no terminales , es un conjunt...{\estilo de visualización \estilo de visualización \{2,4,6,8,10\}}Conjunto finitoEn matemáticas , particularmente en teoría de conjuntos , un conjunto finito es un conjunto que tiene un número finito de elementos . De manera inf...iconoBioinformáticaBioinformática temprana: alineamiento computacional de secuencias determinadas experimentalmente de una clase de proteínas relacionadas; consulte §...