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.

Arquitectura del algoritmo de búsqueda de cadenas

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