Los métodos más comunes de búsqueda por palabra son:
- Knuth Morris Pratt
- Boyer Moore
Boyer Moore
Boyer moore consiste en realizar un escaneo de derecha a izquiera, moverse en dirección hacia la izquierda hasta que se produsca un error, si el primer elemento a comparar es errónea se realiza un salto respecto a su tabla de salto, de lo contrario al pasar el primer elemento de izquierda a derecha, esta se cambia y se continua de derecha a izquierda empezando con el último elemento del patrón, éste algoritmo es considerado como uno de los más eficaces para búsquedas de palabras
+08.54.31.png)
+08.54.31.png)
[http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore]
Knuth Morris Pratt
Este algoritmo trata de localizar la posición de comienzo de un string dentro de otra. Obteniendo antes una tabla de fallos que sirve para hacer saltos entre el string cuando se encuentra un fallo. A continuación se explica la forma en la que se trabaja con éste método
+08.22.16.png)
+08.22.23.png)
Este algoritmo trata de localizar la posición de comienzo de un string dentro de otra. Obteniendo antes una tabla de fallos que sirve para hacer saltos entre el string cuando se encuentra un fallo. A continuación se explica la forma en la que se trabaja con éste método
"Supongamos una tabla 'F' ya precalculada, y supongamos que la cadena a buscar esté contenida en el array 'P()', y la cadena donde buscamos esté contenida en un array 'T()'. Entonces ambas cadenas comienzan a compararse usando un puntero de avance para la cadena a buscar, si ocurre un fallo en vez de volver a la posición siguiente a la primera coincidencia, se salta hacia donde sobre la tabla, indica el puntero actual de avance de la tabla. El array 'T' utiliza un puntero de avance absoluto que considera donde se compara el primer carácter de ambas cadenas, y utiliza como un puntero relativo (sumado al absoluto) el que utiliza para su recorrido el array 'P'."Para poder realizar éste método se baso en el psudocódigo que proporciona wikipedia, en la cual, lo contiene lo anterior mencionado.
+08.22.16.png)
[http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm]
+08.22.23.png)
[http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm]
Código
Para tener la simulación al principio lo que se hizo fueron unas pruebas donde se tenían el texto y el paterno que había preestablecido, pero para tener diferentes resultados se hizo una función donde que se generaba palabras aleatorias dependiendo de un tamaño dado del paterno y del texto. Para así correrlo en un bash donde se metería en un bucle para generar diferentes resultados.
Para tener la simulación al principio lo que se hizo fueron unas pruebas donde se tenían el texto y el paterno que había preestablecido, pero para tener diferentes resultados se hizo una función donde que se generaba palabras aleatorias dependiendo de un tamaño dado del paterno y del texto. Para así correrlo en un bash donde se metería en un bucle para generar diferentes resultados.
Bash
Resultados:
Una vez generados los archivos lo que se hizo fue plotearlo con gnuplot obteniendo los siguientes resultados:
Donde podemos comentar que con el metodo de naive su tiempo va creciendo al depender de las cantidades de palabras que contenga el texto y el paterno a diferencia con el método Knuth Morris Pratt que se va comportando igual y resaltando que la cantidad de éxitos es mayor cuando el paterno su tamaño es pequeño.
Referencias:
Pues, faltó la implementación de BM. Por ende el programa te da 3 pts de 5 máximo. En el reporte hay unos detalles de redacción y no mencionas la complejidad en términos de espacio; van 4 pts de 5 máx.
ResponderEliminar