3.1- Algoritmo De Búsqueda De Cadenas Boyer-Moore

Algoritmo de búsqueda de cadenas Boyer-Moore

El algoritmo de búsqueda de cadenas Boyer-Moore es un particularmente eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas práctica.1 Fue desarrollado por Bob Boyer y J Strother Moore en 1977. El algoritmo preprocesa la cadena objetivo (clave) que está siendo buscada, pero no en la cadena en que se busca (no como algunos algoritmos que procesan la cadena en que se busca y pueden entonces amortizar el coste del preprocesamiento mediante búsqueda repetida). El tiempo de ejecución del 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.Cómo funciona el algoritmo

La X en la posición 8 excluye todas la 8 posibles posiciones de comienzo mostradas.

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".

- - - - - - - X - - - - - - -

A N P A N M A N - - - - - - -

- A N P A N M A N - - - - - -

- - A N P A N M A N - - - - -

- - - A N P A N M A N - - - -

- - - - A N P A N M A N - - -

- - - - - A N P A N M A N - -

- - - - - - A N P A N M A N -

- - - - - - - A N P A N M A N

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.

BOYE