Algoritmo Boyer-Moore


Características

  • La comparación ahora se realiza de derecha a izquierda.
  • Si hay una discrepancia en el último carácter del patrón y el carácter del texto no aparece en todo el patrón, entonces éste se puede deslizar m posiciones sin realizar niguna comparación extra.
  • No es necesario comparar los primeros m-1 caracteres del texto, lo cual indica que podría realizarse una búsqueda en el texto con menos de n comparaciones.
  • Si el carácter discrepante del texto se encuentra dentro del patrón, éste podría desplazarse en un número menor de espacios.
  • Este tipo de algoritmos se basan en el hechote que en cada ventana se pueden hacer “backwards”
  • El tiempo promedio para este algoritmo es de O(n log(m/n))
  • El peor caso genera un tiempo de O(mn).

Lógica

  • Ante una discrepancia de un carácter, el carácter del texto se compara con el patrón de búsqueda para determinar el salto hacia la derecha.
  • Si el carácter no existe en el patrón de búsqueda se salta la cadena completa.
  • Si la discrepancia se produce tras varias coincidencias, se salta en función de la repetición de patrones en la secuencia de búsqueda, y se alinea de nuevo usando ese valor.
  • Se toma como salto el mayor de los dos valores.

Ejemplo





Variante del Algoritmo Boyer-Moore


Algoritmo Boyer-Moore-Horspool



Comments