Algoritmo de búsqueda de cadenas Boyer-Moore

Elalgoritmo de búsqueda de cadenas Boyer-Moorees un particularmente eficientealgoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica.​ Fue desarrollado porBob BoyeryJ Strother Mooreen 1977. Elalgoritmopreprocesalacadenaobjetivo (clave)queestá siendo buscada, pero noenla cadena en que se busca (no como algunos algoritmos que procesan la cadena en que se busca y pueden entoncesamortizarel coste del preprocesamiento mediante búsqueda repetida). Eltiempo de ejecucióndel algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos. Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida.
A la gente frecuentemente le sorprende el algoritmo de Boyer-Moore, cuando lo conoce, porque en su verificación intenta comprobar si hay una coincidencia en una posición particular marchando hacia atrás. Comienza una búsqueda al principio de un texto para la palabra
"ANPANMAN", por ejemplo, comprueba que la posición octava del texto en proceso contenga una "N". Si encuentra la "N", se mueve a la séptima posición para ver si contiene la última "A" de la palabra, y así sucesivamente hasta que comprueba la primera posición del texto para una "A".
La razón por la que Boyer-Moore elige este enfoque está más clara cuando consideramos que pasa si la verficación falla-por ejemplo, si en lugar de una "N" en la octava posición, encontramos una "X". La "X" no aparece en "ANPANMAN", y esto significa que no hay coincidencia para la cadena buscada en el inicio del texto-o en las siguientes siete posiciones, puesto que todas fallarían también con la "X". Después de comprobar los ocho caracteres de la palabra "ANPANMAN" para tan sólo un carácter "X", seremos capaces de saltar hacia delante y comenzar buscando una coincidencia en el final en la 16.ª posición del texto.
Esto explica por qué el rendimiento del caso promedio del algoritmo, para un texto de longitudn{\displaystyle n}y patrón fijo de longitudm{\displaystyle m}, esn/m{\displaystyle n/m}: en el mejor caso, solo uno enm{\displaystyle m}caracteres necesita ser comprobado. Esto también explica el resultado algo contra-intuitivo de que cuanto más largo es el patrón que estamos buscando, el algoritmo suele ser más rápido para encontrarlo.
El algoritmo precalcula dos tablas para procesar la información que obtiene en cada verificación fallada: una tabla calcula cuantas posiciones hay por delante en la siguiente búsqueda basada en el valor del carácter que no coincide; la otra hace un cálculo similar basado en cuantos caracteres coincidieron satisfactoriamente antes del intento de coincidencia fallado. (Puesto que estas dos tablas devuelven resultados indicando cuán lejos "saltar" hacia delante, son llamada en ocasiones "tablas de salto", que no deberían ser confundidas con el significado más común detabla de saltosen ciencia de la computación.) El algoritmo se desplazará con el valor más grande de los dos valores de salto cuando no ocurra una coincidencia.
Rellénese la primera tabla como sigue. Para cadaimenor que la longitud de la cadena de búsqueda, constrúyase el patrón consistente en los últimosicaracteres de la cadena precedida por un carácterno-coincidente, alinéense a la derecha el patrón y la cadena,y anótese el menor número de caracteres para que el patrón tenga que desplazarse a la izquierda para una coincidencia.Por ejemplo, para la búsqueda de la cadena ANPANMAN, la tabla sería como sigue:(NMAN significa una subcadena en ANPANMAN consistente en un carácter que no es 'N' más los caracteres 'MAN'.)
La cantidad de desplazamiento calculada por la primera tabla es a veces llamada "desplazamiento desufijobueno"​ o "regla de sufijo bueno (fuerte)". El algoritmo original Boyer-Moore publicado​ usa una más simple, más débil, versión de la regla de sufijo bueno en que cada entrada en tabla de arriba no requiere unano-coincidencia para el carácter de más a la izquierda. Esto es a veces llamado "regla del sufijo bueno débil" y no es suficiente para conseguir que Boyer-Moore funcione en tiempo lineal en el peor caso.
La segunda tabla es fácil de calcular: iniciése en el último carácter de la cadena vista y muévase hacia el primer carácter. Cada vez que usted se mueve a la izquierda, si el carácter sobre el que está no está ya en la tabla, añádalo; su valor de desplazamiento es la distancia desde el carácter más a la derecha. Todos los otros caracteres reciben un valor igual a la longitud de la cadena de búsqueda.
Ejemplo: Para la cadena ANPANMAN, la segunda tabla sería como se muestra (por claridad, las entradas son mostradas en el orden que serían añadidas a la tabla):(La N que se supuestamente sería cero está basada en la segunda N desde la derecha porque solo anotamos el cálculo para las primerasm−1{\displaystyle m-1}letras)
La cantidad de desplazamiento calculada por la segunda tabla es a veces llamada "desplazamiento de carácter malo".​
El caso peor para encontrar todas las coincidencias en un texto necesita aproximadamente3n{\displaystyle 3n}comparaciones, de aquí que la complejidad seaO(n){\displaystyle O(n)}, a pesar de que el texto contenga una coincidencia o no.​ Esta prueba llevó algunos años para desarrollarse. En el año en que se ideó el algoritmo, 1977, se mostró que el número máximo de comparaciones no era más de6n{\displaystyle 6n}; en 1980 se demostró que no era más de4n{\displaystyle 4n}, hasta el resultado de Cole en Sep 1991.
ElAlgoritmo Boyer-Moore Turbotoma una cantidad constante adicional de espacio para completar una búsqueda en2n{\displaystyle 2n}comparaciones (en contra de3n{\displaystyle 3n}para Boyer-Moore), donden{\displaystyle n}es el número de caracteres en el texto para ser buscado.​
Elalgoritmo Boyer-Moore-Horspooles una simplificación del algoritmo que omite la "tabla primera". El algoritmo Boyer-Moore-Horspool requiere (en el peor caso)mn{\displaystyle mn}comparaciones, mientras que el algoritmo Boyer-Moore requiere (en el peor caso) tan solo3n{\displaystyle 3n}comparaciones.