Algoritmos de búsqueda de subcadenas

A este tipo de algoritmos también se les llama Algoritmos de patrones en un texto, algoritmos de emparejamiento de secuencias, algoritmos de casamiento de secuencias o simplemente por su nombre en inglés string matching. Este tipo de algoritmos persiguen encontrar subcadena/s con alguna propiedad en una cadena de caracteres.

Terminología

Normalmente se denomina patrón/es a la/ subcadena/s buscada/s y texto a la cadena en la que se realiza la búsqueda. Se suelen emplear las letras m y n para referirnos a la longitud de un patrón y a la longitud del texto respectivamente. Podemos asumir que n>m

Clasificación

Este tipo de algoritmos se pueden clasificar según el número de subcadenas que se intentan buscar en simples, se busca sólo una subcadena, y múltiples, se buscan varias subcadenas.^[1]​^[2]​

Algoritmos de búsqueda simple de subcadenas

También llamados por su denominación en inglés Single string Matching. En este tipo de algoritmos sólo se busca una subcadena a la que llamamos patrón, es decir el objetivo es encontrar todas las ocurrencias del patrón p dentro del texto. Este tipo de algoritmos se suelen agrupar en alguno de los siguientes tipos^[1]​

1. Fuerza bruta. La idea es ir deslizando el patrón sobre el texto de izquierda a derecha, comparándolo con las subcadenas del mismo tamaño que empiezan en cada carácter del texto.
2. Leer todos los caracteres del texto uno a uno modificando en cada paso algunas variables que permitan identificar posibles ocurrencias. A este tipo pertenecen los algoritmos de Knuth-Morris-Pratt,^[3]​ Shift-Or^[4]​ o búsqueda simple con autómata determinista.
3. Buscar el patrón en una ventana que se desliza a lo largo del texto. Para cada posición de esta ventana buscamos de derecha a izquierda un sufijo de la ventana que corresponda a un sufijo del patrón. A este tipo pertenecen los algoritmos de Boyer-Moore,^[5]​ Boyer-Moore-Horspool^[6]​ y Sunday Quick Search.^[7]​ Este tipo de algoritmos no suelen funcionar bien cuando el tamaño del patrón es pequeño y hay una probabilidad alta de encontrarlo en el texto.
4. La búsqueda se realiza de derecha a izquierda dentro de una ventana, pero en este esquema se busca el sufijo más largo en la ventana que es subcadena del patrón. Ejemplos de este tipo de algoritmos son BDM,^[8]​ BNDM^[9]​ y BOM.^[10]​ Este tipo de algoritmos para patrones pequeños no suelen funcionar bien.
5. Esquemas basados en funciones hash. Ejemplo de este tipo de algoritmos es el de Karp-Rabin.^[11]​

Algoritmos de búsqueda múltiple de subcadenas

También llamados por su denominación en inglés Multiple String Matching. Ahora no tenemos un solo patrón p a buscar sino que contamos con un conjunto P={p1,..., pl} de patrones. La solución que se suele adoptar es la extensión de los esquemas anteriores para el caso múltiple. Por tanto tenemos los siguientes subtipos:

1. Fuerza bruta
2. Extensión del tipo 2 de algoritmos de búsqueda simple de subcadenas. De este tipo de algoritmos son los de Aho-Corasick,^[12]​ Multiple Shift-And y búsqueda múltiple con autómata determinista.
3. Extensión del tipo 3 de algoritmos de búsqueda simple de subcadenas. De este tipo son los algoritmos de Commentz-Walter,^[13]​ Set Horspool, Wu-Manber.^[14]​
4. Extensión del tipo 4 de algoritmos de búsqueda simple de subcadenas. De este tipo son los algoritmos SBOM, Multiple BNDM,^[15]​ DAWG-MATCH.^[16]​
5. Extensión del tipo 5 de algoritmos de búsqueda simple de subcadenas

Referencias

1. Román Roset Mayals,Diseño de una aplicación bioinformática para el estudio de repeticiones de patrones en cadenas de DNA. Memoria 2003
2. Sergio Talens-Oliag Análisis de algoritmos de búsqueda de un solo patrón. Proyecto Fin de Carrera 1997. U Politécnica de Valencia
3. D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J.Comput, 6(2):323–350, 1977
4. R. Baeza-Yates and G. Gonnet. A new approach to text searching. Comm. ACM, 35(10):74–82, 1992
5. R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. ACM, 20(10):762–772, 1977
6. R. Horspool. Practical fast searching in strings. Softw. Pract. Exp.,10(6):501–506, 1980
7. Daniel M. Sunday. A Very Fast Substring Search Algorithm. Comunications of the ACM 33 (8),132–142 (Agosto de 1990)
8. A. Czumaj, M. Crochemore, L. Gasieniec, S. Jarominek, W. Plandowski, T. Lecroq, and W. Rytter. Speeding up two string-matching algorithms. Algorithmica, 12:247–267, 1994.
9. G. Navarro and M. Raffinot. A bit-parallel approach to suffix automata:Fast extended string matching. In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, number 1448 in Lecture Notes in Computer Science, pages 14–33. Springer-Verlag, Berlin, 1998
10. Cyril Allauzen, Maxime Crochemore, and Mathieu Raffinot. Factor oracle:A new structure for pattern matching. In Conference on Current Trends in Theory and Practice of Informatics, pages 295–310, 1999.
11. Karp, R. M. y Rabin, M. O.. Efficient Randomized Pattern Matching Algorithms. IBM J. Res.Develop.31 (2), 249–260 (1987)
12. A. V. Aho and M. Corasick. Efficient string matching: An aid to bibliographic search. Comm. ACM, 18(6):333–340, 1975
13. B. Commentz-Walter. A string matching algorithm fast on the average. In 6th, number 71 in Lecture Notes in Computer Science, pages 118–132. H.A.Maurer, 1979
14. S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR-94-17, Chung-Cheng University, 1994
15. M. Crochemore and W.Rytter. Text Algorithms. Oxford University Press,1994.
16. Maxime Crochemore, Artur Czumaj, Leszek Gasieniec, Thierry Lecroq,Wojciech Plandowski, and Wojciech Rytter. Fast practical multi-pattern matching. Information Processing Letters, 71(3-4):107–113, 1999.

•   Datos: Q374040
•   Multimedia: String-searching algorithm