Boyer-Moore-Horspool

Un problema muy común es, dado un texto, encontrar la posición de una palabra dada en el texto. Existen varios algoritmos que resuelven este problema de una forma eficiente, aunque la eficiencia de cada algoritmo esta condicionada por varios factores del texto, como el tamaño del alfabeto, el largo del texto, y del patrón, etc. Uno de los algoritmos mas famosos para resolver este problema es el algoritmo de Boyer-Moore. Este algoritmo fue modificado después por Nigel Horspool, con el objetivo de crear un algoritmo que fuera rápido al buscar en textos de alfabetos naturales (lenguajes humanos) y a la vez sencillo de entender e implementar. El algoritmo fue publicado en 1980 con el nombre de Boyer-Moore-Horspool.

El algoritmo esta basado en dos ideas fundamentales:

1. Buscar de derecha a izquierda
2. Calcular los saltos que se pueden hacer para avanzar mas en la búsqueda

Buscar la aguja en el pajar

Tenemos el texto ‘TEXTOGENERADOALEATORIAMENTE’, y queremos encontrar la posicion de ‘EATOR’ dentro del texto. A continuacion, nos referiremos a ‘EATOR’ como el patron, y a ‘TEXTOGENERADOALEATORIAMENTE’ como el texto.

1. Alineamos el patrón con el texto

2. Comparamos de derecha a izquierda los caracteres del patrón con los del texto. En el patrón tenemos ‘R‘ y en el texto ‘O‘. En este caso, el algoritmo común movería a ciegas una posición a la derecha el patrón, en cambio, nuestro algoritmo trata de alinear el caracter del texto que esta alineado con el ultimo caracter del patron, con su posición mas a la derecha en el patrón.

3. De esta forma se alinean las dos O, y se vuelve a comparar comenzando por la derecha. Al comparar ‘R‘ con ‘G‘, el algoritmo trata de alinear ‘G‘ con su posición mas a la derecha en el patrón, pero dado que ‘G‘ no aparece en el patrón, podemos correctamente alinear el patrón hasta despues de la ‘G‘ en el texto, ya que el patron no puede aparecer antes de esa posicion, porque no contiene la ‘G‘.

4. Ahora al comparar ‘R‘ con ‘A‘, alineamos la ‘A‘ del texto con la del patrón, y se vuelve a comparar de derecha a izquierda

5. Sucede lo mismo que en el caso anterior, volvemos a alinear la ‘A‘ con su posición en el patrón

6. Idem

7. En este caso, el algoritmo continua comparando de derecha a izquierda hasta encontrar el patrón completo en el texto. Aquí tenemos una aparición.

8.En este punto el algoritmo puede terminar concluyendo que se encontró el texto en la posición dada, o continuar a buscar todas las posiciones donde aparece el patrón dentro del texto. En este caso, alinearíamos la ‘R‘ del texto a su próxima posición en el patrón, como no aparece mas, podemos mover el patrón pasada la ‘R‘ del texto.

9. En este punto, al comparar ‘N‘ con ‘R‘ notamos que ‘N‘ no aparece en el patrón, y al mover el patrón pasado ‘N‘, el algoritmo termina, ya que no hay suficientes caracteres en el texto para seguir comparando.

Precalcular la aguja

Para ejecutar el algoritmo, necesitamos definir la función R, que dado un caracter c del texto, R(c) nos indica la cantidad de posiciones que debemos mover el patrón para alinear la posición mas a la derecha de c en el patrón con la posición actual de c en el texto. Esta función se puede precalcular para cada uno de los caracteres del texto, y luego usarla en el algoritmo de forma constante.

Con esta función definida, el algoritmo alinea a cada paso el patrón con la posición actual en el texto. En caso de una coincidencia, se continua explorando el patrón tratando de encontrar mas coincidencias, en caso de encontrar dos caracteres diferentes, el algoritmo usa la función R(c) en el caracter del texto que esta siendo alineado con el ultimo caracter del patrón para calcular la nueva alineación del patrón. La implementacion quedaria asi

public int[] preBoyerMooreHorspool(char[] P, char[] T, int size)
{
    int pLength = P.length;
    int last = P.length - 1;

    // precalcular R
    int[] R = new int[size];
    for(int i = 0; i < size; i++) R[i] = pLength;
    for(int i = 0; i < last; i++) R[P[i]] = last - i;

    return R;
}

Esta función inicialmente asigna a cada letra del alfabeto (size es el tamaño del alfabeto) un salto del tamaño del patrón. Esto sucede en el caso en que la letra no aparece en el patrón. Luego, a las letras que están en el patrón (excepto la última) se le asigna un salto del tamaño de su posición más a la derecha.

El algoritmo luego va a usar la tabla para ir alineando el patrón con el texto

public int boyerMooreHorspool(String pattern, String text)
{
    char[] P = pattern.toCharArray();
    char[] T = text.toCharArray();
    int pLength = P.length;
    int offset = 0;
    int scan = 0;
    int last = P.length - 1;
    int maxoffset = T.length - P.length;

    // precalcular R
    int[] R = preBoyerMooreHorspool(P, T, 256);

    // aun hay suficientes caracteres para comparar
    while(offset <= maxoffset)
    {
        // comparar de derecha a izquierda
        for(scan = last; P[scan] == T[scan+offset]; scan--)
            if(scan == 0) return offset; // encontrado

        offset += R[T[offset + last]]; // alinear el patron
    }

    return -1; // no encontrado
}

En esta implementación se usa 256 para el tamaño del alfabeto. Esto se puede modificar para tamaños menores del texto, pero con la observación de que este algoritmo es particularmente eficiente para alfabetos grandes y patrones largos. Para alfabetos pequeños (como el de ADN o el binario) es mas eficiente usar la versión completa de Boyer-Moore.

Análisis

El algoritmo tiene un caso peor acotado por O(nm) donde n es el tamaño del texto y m del patrón. En la practica sin embargo – y especialmente con alfabetos de tamaño grande – este caso nunca ocurre. De hecho, el algoritmo se comporta en orden sublineal, ya que en la mayoría de las ocasiones los saltos que se producen en el algoritmo conllevan a que se produzcan pocas comparaciones. El análisis de este algoritmo es sumamente complejo, pero no es difícil notar que en el mejor caso, se realizan solamente O(n/m) comparaciones.

La siguiente gráfica muestra como se comporta el algoritmo comparado con otros algoritmos conocidos que resuelven el mismo problema:

Referencias

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/Matching-Boyer-Moore2.html

http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/horsen.htm

http://www-igm.univ-mlv.fr/~lecroq/string/node18.html

http://www.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf

Problemas

http://codeforces.com/problemset/problem/318/B

Codeforces 271D

codeforces.com/problemset/problem/271/D

Mi solución para este problema es usando trie. Al principio procesar la entrada en un arreglo para almacenar las letras que son buenas. A partir de ahí, enumerar cada substring y poner en un trie todos los que tengan no mas de k caracteres malos. Finalmente la solución es la cantidad de palabras insertadas en el trie.

Hay que tener en cuenta que si enumeramos los substrings en orden (todos los que comienzan en el primer caracter en orden ascendente por la cantidad de caracteres, luego todos los que comienzan en el segundo, etc), cada substring se obtiene agregando solo un caracter al final del anterior. Esto nos permite mantener la posicion en el trie, e insertar solo un caracter en vez de todo el substring, lo cual optimiza el algoritmo, ya que no tenemos que crear los substring, sino insertar solo un caracter en el trie. De forma similar, al encontrar mas de k caracteres malos, no tenemos que agregar mas caracteres a ese substring, sino movernos al próximo  Al insertar cada caracter en el trie, lo marcamos como terminal y si no estaba marcado anteriormente, incrementamos la cantidad de palabras en el trie.

Mi solucion en Codeforces codeforces.com/contest/271/submission/3110083

Referencias

Articulo sobre Trie

Trie – arbol de prefijos

El trie (también conocido como árbol de prefijos) es una estructura de datos muy útil para resolver problemas asociados con strings. El problema mas conocido es dado una colección de palabras (algo como un diccionario) y una palabra en particular, saber si la palabra se encuentra en la colección de palabras.

Una primera solución podría ser comparar la palabra buscada a cada palabra, pero esta solucion es O(n) ya que se necesitarían al menos n comparaciones donde n es  la cantidad de palabras en la colección. Cuando tenemos demasiadas palabras, esta solución es extremadamente lenta. Otra posible solución podría ser ordenar todas las palabras alfabéticamente  y luego usar búsqueda binaria para encontrar la palabra. Esta solución es mejor, pero tiene la desventaja de que cada vez que introducimos una nueva palabra hay que reordenar la colección completa, lo que es O(n log n).

El trie resuelve este problema eficientemente, ya que tanto agregar como buscar una palabra es O(|s|) donde |s| es la cantidad de caracteres de la palabra s. Esta estructura fue introducida por por Rene de la Briandais y Edward Fredking en 1959. El nombre proviene de la palabra RETRIEVAL, que significa recuperación. Internamente, funciona como un árbol ordenado, donde cada nodo representa un carácter de una palabra insertada en el trie, y los nodos hijos de este son caracteres que aparecen después de el en la palabra. La raíz del árbol es el caracter vacío, ya que se puede considerar que este aparece al principio de cualquier palabra.

El trie también es conocido como árbol de prefijos porque al insertar una palabra en el árbol  se busca primero el mayor prefijo de esa palabra que ya este presente en el árbol, y a partir de ahí se continua insertando hasta donde termine la palabra. La figura a continuación muestra un trie construido con las palabras algo, ala, abeja, y trie.

Trie construido con las palabras. Los nodos terminales están resaltados.

Construyendo el trie

Para construir el trie, necesitamos almacenar en cada nodo lo siguiente:

• Letra que representa
• Si es o no la ultima letra de alguna palabra
• Nodo padre
• Nodos hijos

Adicionalmente, cada nodo implementa un método para saber si un nodo dado es hijo de ese nodo, y para agregar un nuevo hijo. Usando estos métodos se encuentra el mayor prefijo que ya este en el árbol hasta llegar a un nodo hoja, y se comienza a insertar a partir de ahí.

class Node
{
    char content;
    boolean ends;
    Node parent;
    Node[] child = new Node[26];

    public Node(char c, Node pi)
    {
        parent = pi; content = c;
    }

    public Node getChild(char c) { return child[c-'a']; }

    public Node addChild(Node node) { child[node.content - 'a'] = node; }
}

En la linea 6 inicializamos el arreglo en 26 ya que ese es el tamaño del alfabeto ingles. Para un alfabeto mayor, hay que incrementar el tamaño del arreglo. El método getChild retornara el nodo hijo que contiene el caracter c, o null si no hay ninguno. Con esto podemos crear un trie cuya raíz sera el caracter vacío.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word) { }

    public boolean search(String word) { }
}

Insertar en el trie

El algoritmo para insertar una palabra en el trie es comenzar en la raíz  y moverse por el árbol buscando el caracter siguiente en la palabra. Mientras se encuentre el caracter, actualizamos la posición en el árbol  Cuando no se encuentre, insertamos a partir de esa posición  Al llegar al final de la palabra, marcamos la posición en que estamos como terminal.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub != null) current = sub;
            else
            {
                current.addChild(new Node(c, current));
                current = current.getChild(c);
            }
            if (i == word.length()-1) current.ends = true;
        }
    }

    public boolean search(String word) { }
}

Si insertáramos en el trie original la palabra abel, la secuencia de operaciones seria la siguiente:

1. Comenzamos en la raíz.
2. Buscamos el caracter ‘a’. Aparece, por tanto nos movemos en el árbol hasta la ‘a’.
3. Buscamos ‘b’. Aparece, nos movemos a ‘b’.
4. Buscamos ‘e’. Aparece, nos movemos a ‘e’.
5. Buscamos ‘l’. No aparece, insertamos ‘l’ como hijo de ‘e’. Nos movemos a ‘l’.
6. Fin de la palabra, marcamos ‘l’ como terminal.

La imagen a continuación muestra el trie después de insertar la palabra y la ruta recorrida para insertarla.

Despues de insertar la palabra. Los nodos sombreados representan el camino.

Buscar en el trie

Buscar en el trie es similar a la operación de insertar. Comenzamos en la raíz y vamos buscando cada caracter de la palabra y actualizando la posición en el árbol  Si en algún momento no encontramos un caracter, es porque la palabra no fue insertada. Similarmente, si el ultimo caracter no esta marcado como terminal, es porque esta palabra no aparece en el trie, sino aparece una palabra mayor que contiene a esta palabra como prefijo.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub != null) current = sub;
            else
            {
                current.addChild(new Node(c, current));
                current = current.getChild(c);
            }
            if (i == word.length()-1) current.ends = true;
        }
    }

    public boolean search(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub == null) return false;
        }
        return current.ends;
    }
}

El trie también puede ser usado para ordenar todas las palabras. Luego de insertarlas en el árbol  un recorrido en pre-orden muestra cada palabra en orden ascendente, y en post-orden, en orden descendente.

Felices códigos!

Referencias

es.wikipedia.org/wiki/Trie

community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

Problemas

codeforces.com/problemset/problem/271/D

www.spoj.com/problems/PRHYME/