Set Horspool

Definición

El algoritmo de Set Horspool es una variante del algoritmo de búsqueda de patrones Horspool, que se utiliza para encontrar una cadena de texto (patrón) dentro de un texto más grande. Este algoritmo es una mejora del algoritmo de Boyer-Moore y se basa en la idea de que, en lugar de comparar el patrón completo en cada posición del texto, se utiliza una tabla de desplazamientos para saltarse posiciones de manera eficiente.

Utiliza un conjunto de desplazamientos (o shifts) precomputados para optimizar la búsqueda del patrón en el texto. En vez de comparar el patrón entero con la porción del texto, compara el último carácter del patrón con el texto y, dependiendo del carácter, decide cuánto saltar para la siguiente comparación, haciendo uso de una tabla de desplazamientos basada en el conjunto de caracteres del patrón.

Su manera de funcionar le permite recorrer eficientemente cadenas de texto, permitiendo una complejidad temporal de peor caso de \(O(mn)\), donde \(m\) es el largo del patrón que se está buscando y \(n\) es el largo del texto.

La complejidad espacial es de \(O(\sigma)\), donde \(\sigma\) es el tamaño del alfabeto, este se refiere a la cantidad de caracteres distintos en el texto.

Ejemplo de Uso

En la siguiente imagen se puede ver la representación de cómo funciona el algoritmo bajo el texto "AMO LAS CASAS", y la cadena de texto "CASAS". Para esto primero se tiene que completar la tabla de malas combinaciones o "Bad match table", la que sirve para medir cuantos caracteres se debería mover el algoritmo para avanzar eficientemente sobre el texto.

Por lo tanto se recibe por entrada el patrón "CASAS", y se calcula con la fórmula indicada, viendo cuando fue la última vez que el carácter apareció en el patrón para evitar repeticiones innecesarias. Para el caso en que el algoritmo no encuentre algún caracter del patrón en el texto, el algoritmo se moverá el largo del patrón, en este caso 5 casiilas, hasta el próximo caracter en el texto. Esto se simboliza con el cáracter '*' en la tabla, indicando que se tiene que mover 5 casillas para cualquier caracter que no este contenido en el patrón.

En la primera iteración se saltan 5 casillas porque el caracter 'L' no está contenido en el patrón 'CASAS', en la segunda iteración el caracter vacío o de espacio tampoco se encuentra en el patrón, además de que el orden de los caracteres n combina con el patrón. Finalmente, para la última iteración se encuentra el patrón exitosamente.

Implementación

Se encontró la siguiente implementación del algoritmo escrita por el profesor de Hope University Charles Cusack\(^3\). En esta implementación se tiene que este algoritmo busca un patrón P de longitud m dentro de un texto T de longitud n. Primero, construye una tabla de desplazamientos S, que tiene un tamaño de 256 (para cubrir todos los caracteres posibles de 1 byte). Inicialmente, todos los valores de la tabla S se configuran con el valor m, indicando que el patrón se debe mover completamente al siguiente carácter del texto si no se encuentra una coincidencia. Luego, la tabla se ajusta para almacenar los desplazamientos específicos de los caracteres del patrón.

Si un carácter del patrón no coincide con el texto, se utiliza esta tabla para determinar cuántos caracteres puede saltar el patrón para continuar la búsqueda, lo que reduce el número de comparaciones. El algoritmo compara el patrón con el texto desde el final del patrón hacia el principio, lo que permite que, en caso de una coincidencia fallida, el patrón se desplace una cantidad específica de posiciones sin tener que comparar carácter por carácter. Si se encuentra una coincidencia completa, se imprime la posición en la que empieza la coincidencia. Este enfoque mejora la eficiencia en comparación con la búsqueda ingenua, ya que evita comparaciones redundantes.

void horspoolSearch(char P[], int m, char T[], int n) {
    int S[256];
    for (int i = 0; i < 256; i++)
        S[i] = m;

    for (int j = 0; j < m - 1; j++)
        S[(unsigned char)P[j]] = m - 1 - j;

    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && P[j] == T[i + j])
            j--;

        if (j < 0)
            std::cout << i << std::endl;

        char next = T[i + m - 1];
        i += S[(unsigned char)next];
    }
}

Referencias

1. Navarro G, Raffinot M. Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press; 2002.

2. Kytöjoki, J., Salmela, L., & Tarhio, J. (2003). Tuning string matching for huge pattern sets. In R. Baeza-Yates, E. Chavez, & M. Crochemore (Eds.), Combinatorial Pattern Matching, 14th Annual Symposium, June 25-27, 2003, Morelia, Mexico (pp. 211-224). Springer.

3. C, Cusack. Horspool’s Algorithm Tutorial & Demo. (s. f.). https://cusack.hope.edu/Algorithms/Content/Algorithms/Space-Time%20Tradeoff/Horspool.html?path=Problems/Other/String%20Matching

4. SetHorspool. (s. f.). https://docs.seqan.de/seqan1/1.2/SPEC_Set_Horspool.html