Algoritmo de Boyer-Moore, búsquedea de patrones
Por Luis Javier López Arredondo, 17/09/2006
El algoritmo de Boyer-Moore, considerado el algoritmo más eficiente en la búsqueda de patrones en cadena de caracteres, se basa en desplazar la ventana de comparación lo máximo posible.
El algoritmo se desplaza dentro de la cadena de búsqueda de izquierda a derecha, y dentro del patrón de derecha a izquierda. La mayor eficiencia se consigue minimizando el número de comparaciones entre caracteres, desplazando lo máximo posible la venta de comparación, a costa de una computación previa.
y: cadena dónde se busca.
x: patrón de búsqueda.
| y | = n, longitud de y.
| x | = m, longitud de x.
j: posición en y desde dónde se prueba la coincidencia.
i: posición en x de comparación, dónde se produce una no coincidencia , y[j+i] <> x[i], y[j+i] = b, x[i] = a.
u: coincidencia en la comparación, sufijo de x, u = y[j+i+..j+m] = x[i+1..m-1].
v: prefijo de x.
s: salto del patrón para la siguiente comparación.
Al producirse una ocurrencia del patrón, o un error en la comparación de un carácter, se calcula el desplazamiento máximo del patrón a lo largo de la cadena de búsqueda.
Partimos de una situación en que no hay coincidencia, existe diferencia entre y[j+i] y x[i], pero las posiciones de x siguientes a i sí coinciden con sus asociadas en y, u = y[j+i+..j+m] = x[i+1..m-1]; hacer notar que u es sufijo de x.
El desplazamiento de x a lo largo de y se limita a causa del carácter en y que produjo la no coincidencia, y[i+j] (1), y los caracteres de x posteriores a i (2), sufijo de x que tenía coincidencia parcial con y.
(1) Teniendo en cuenta el carácter que produjo la no coincidencia en y, y[i+j] = b, el desplazamiento máximo, s, será la distancia entre la aparición más a la derecha de b en x[0..m-2] y la longitud de x, m. La nueva j sería j’=j+s, lo que se consigue es alinear las dos coincidencias de b en x e y, desde dónde es posible que se produzca una coincidencia del patrón. Se considera el intervalo 0..m-2, porque si se da el caso de que b es igual al último carácter de x, el desplazamiento sería 0, y podría provocar un bucle infinito debido a que el patrón no varía su posición.
(2) Teniendo en cuenta los caracteres posteriores a i en x (u, sufijo de x), que coinciden de forma parcial con y, hay que alinear u lo más a la derecha posible de x, sin que esté precedido por x[i] = a (2.a); al no estar u ya precedido por x[i] = a <> x[i-s] = c, en la nueva posición de x respecto de y, sabemos que existe la coincidencia u precedida por c, es posible que se produzca una ocurrencia en y. Si no se encuentra la situación anterior, se tratará de alinear el mayor sufijo posible de x con un prefijo v también de x (2.b); como u coincide parcialmente en y, al buscar el prefijo v de x que también es sufijo de x, v también está en y. Si no se producen ninguno de los dos casos anteriores, el patrón se podrá desplazar toda su longitud.
El desplazamiento de x a lo largo de y será el máximo desplazamiento entre los dos anteriores, (1) y (2).
Código
- StringMatchingBM.java: Implementación en Java del algoritmo de Boyer-Moore.
- StringMatchingBF.java: Implementación en Java del algoritmo de fuerza bruta.
- StringMatchingTest.java: Clase en Java empleada para realizar las pruebas de rendimiento.
100 tests --> BM: 70 millis (18462 comparisons) 100 tests --> BF: 50 millis (73898 comparisons) 1000 tests --> BM: 310 millis (187974 comparisons) 1000 tests --> BF: 341 millis (777391 comparisons) 10000 tests --> BM: 2424 millis (1877086 comparisons) 10000 tests --> BF: 2872 millis (8021317 comparisons) 100000 tests --> BM: 22760 millis (18809679 comparisons) 100000 tests --> BF: 34268 millis (79647647 comparisons)
Referencias:
- "Moore home page".
- "Exact String Mathing Algoritims", por Christian Charras y Thierry Lecroq, recopilación de muchos algoritmos de búsqueda de subcadenas de caracteres.
- "Animation of the Boyer/Moore Algorithm", por Dieter Bühler.
- "Boyer-Moore Illustrated v2.0", animación applet.
