Boyer-Moore-Sunday (BMS)
El algoritmo BMH desliza el patrón basado en el símbolo del texto que corresponde a la posición del último carácter del patrón. Este siempre se desliza al menos una posición si se encuentra una discrepancia con el texto.
Es fácil ver que si se utiliza el carácter una posición más adelante en el texto como entrada de la función siguiente el algoritmo también funciona, pero en este caso es necesario considerar el patrón completo al momento de calcular los valores de la función siguiente. Esta variante del algoritmo es conocida como Boyer-Moore-Sunday (BMS).
Algoritmo de fuerza bruta
Descripcion:
• No requiere ninguna fase de pre proceso previo, ni un espacio extra constante además del espacio asignado al patrón y al texto.
• Para la búsqueda:
• Consiste en la comparación de todas las posiciones del texto entre 0 y el n-m, si una ocurrencia del patrón corresponde o no.
• Si encuentra una no ocurrencia, o una ocurrencia total del patrón, salta un carácter hacia la derecha.
Características:
• Es el algoritmo más simple posible.
• Consiste en probar todas las posibles posiciones del patrón en el texto.
• Requiere espacio constante.
• Realiza siempre saltos de un carácter.
• Compara de izquierda a derecha.
• Realiza la búsqueda del patrón en un tiempo O(m*n).
• Realiza 2n comparaciones previstas de los caracteres del texto.
Boyer-Moore-Horspool (BMH)
El algoritmo de búsqueda es el siguiente:
Compara el patrón con el texto de derecha a izquierda, y se detiene cuando se encuentra una discrepancia con el texto. Cuando esto sucede, se desliza el patrón de manera que la letra del texto que estaba alineada con bm, denominada c, ahora se alinie con algún bj, con j<m, si dicho calce es posible, o con b0, un carácter ficticio a la izquierda de b1, en caso contrario (este es el mejor caso del algoritmo).
Para determinar el desplazamiento del patrón se define la función siguiente como:
• 0 si c no pertenece a los primeros m-1 caracteres del patrón (¿Por qué no se considera el carácter bm?).
• j si c pertenece al patrón, donde j<m corresponde al mayor índice tal que bj==c.
Esta función sólo depende del patrón y se puede precalcular antes de realizar la búsqueda.
Se puede demostrar que el tiempo promedio que toma el algoritmo BMH es:
donde c es el tamaño del alfabeto (c<<n). Para un alfabeto razonablemente grande, el algoritmo es
El método descrito es la base del algoritmo Boyer-Moore, del cual se estudiarán dos variantes: Horspool y Sunday.
:
Características
Algoritmos de Cadenas
La búsqueda de patrones en un texto es un problema muy importante en la práctica. Sus aplicaciones en computación son variadas, como por ejemplo la búsqueda de una palabra en un archivo de texto o problemas relacionados con biología computacional, en donde se requiere buscar patrones dentro de una secuencia de ADN, la cual puede ser modelada como una secuencia de caracteres (el problema es más complejo que lo descrito, puesto que se requiere buscar patrones en donde ocurren alteraciones con cierta probabilidad, esto es, la búsqueda no es exacta).
By: Marisa Ruiz Velasco
Francisco Javier De La Paz Nava
Juan Carlos Valadez
• 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).
El algoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada con la cadena a localizar se pre-calcula una tabla de saltos (conocida como tabla de fallos) que después al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo.
Descripcion:
El algoritmo KMP es un algoritmo de búsqueda de sub-cadenas simple y por lo tanto su objetivo es buscar la existencia de una sub-cadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se pre-calcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.
A este tipo de algoritmos también se les llama:
• Algoritmos de patrones en un texto
• Algoritmos de emparejamiento de secuencias
• Algoritmos de casamiento de secuencias
• String matching.
• Realiza las comparaciones de izquierda a derecha;
• Procesamiento previo de fase en el espacio O (m) y la complejidad del tiempo;
• Fase de búsqueda en tiempo O (n + m) complejidad del tiempo (independiente del tamaño del alfabeto);
• Retardo delimitado por log (m) donde es el coeficiente de oro ( ).
Características:
Algoritmo de Knuth-Morris-Pratt.
El algoritmo de Boyer-Moore es considerado el algoritmo de procesamiento de cadenas (string-matching) más eficiente en las aplicaciones usuales. Una versión simplificada de él o el algoritmo completo es frecuentemente implementada en los editores de texto para los comandos de «búsqueda» y «Reemplazar».
Algoritmo de Boyer-Moore.