Análisis Suavizado del Algoritmo Boyer-Moore-Horspool

Abstract

El objetivo del presente trabajo de título es estudiar el algoritmo para búsqueda de patrones en texto debido a Boyer-Moore-Horspool (BMH) bajo un enfoque de texto sometido a una ligera perturbación independiente carácter a carácter, de manera de determinar la esperanza del desempeño del algoritmo sometido a dicha perturbación.

El algoritmo BMH es una simplificación de Horspool al algoritmo que había sido propuesto anteriormente por Boyer y Moore (BM). En el mismo trabajo original de Horspool, él hace notar que su versión, en cuanto a tiempo de ejecución y comparaciones entre texto y patrón, aunque más sencilla y con peor desempeño de peor caso, tiene un desempeño comparable y a veces incluso superior al del algoritmo BM. Si bien diversos trabajos han hecho un buen análisis del algoritmo BMH especialmente en el caso promedio, no es claro que un análisis promedio sea una buena respuesta a la pregunta de por qué un algoritmo funciona bien en la práctica aunque su desempeño de peor caso sea deficiente.

Basados en el enfoque de análisis suavizado propuesto originalmente por Spielman y Teng pero adaptado para problemas de naturaleza discreta y más específicamente para texto, proponemos una perturbación bajo la cual analizar el desempeño esperado del algoritmo BMH cuando la entrada es sometida a una perturbación lo suficientemente pequeña como para no eliminar la influencia que la entrada ejerce sobre el desempeño del algoritmo. Para ello, en primer lugar, diseñamos herramientas que permiten encontrar una familia de constantes, indexada por parámetros del algoritmo, que acotan el peor desempeño en cada caso. También diseñamos un procedimiento para calcular dichas constantes para patrones y alfabetos pequeños. Luego encontramos una familia de constantes análoga a la anterior para acotar el desempeño esperado, bajo perturbación de texto, del algoritmo, y demostramos resultados que aseguran que dicho desempeño perturbado, bajo condiciones razonables, es mejor que el desempeño de peor caso asintóticamente con el tamaño del texto.

Finalmente, mostramos alguna evidencia empírica que sugiere que dentro del espacio de entradas la mayoría lleva a un comportamiento sustancialmente mejor al del peor caso. Las herramientas desarrolladas durante el trabajo y el enfoque aplicado podrían, en un trabajo futuro, justificar la diferencia entre el desempeño teórico y el observado en la práctica para BMH.