Víctor Briones: [TEORÍA DE LA INFORMACIÓN] String Matching

Para esta entrada se encargó analizar los algoritmos de "String matching" vistos en clase, estos son el algorimo de Boyer-Moore y el algoritmo de Knuth-Morris-Pratt, yo no alcancé a implementar el algoritmo Boyer-Moore por lo que utilicé en su lugar el algoritmo de fuerza bruta (comparar caracter por carácter) para comparar con el de Knuth-Morris-Pratt.

Boyer-Moore:

Éste algoritmo es un 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. El algoritmo preprocesa la cadena objetivo que está siendo buscada, pero no en la cadena en que se busca.

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.

Su principal característica es que su búsqueda la realiza de derecha a izquierda, de esta manera se sabe que si no coincide la última letra, entonces no hay por que comparar el resto, lo que ahorra tiempo.

Antes de iniciar con la búsqueda, se preprocesa una tabla llamada "bad character" que contiene las posiciones que hay que saltar para determinado caracter.

El tiempo promedio para este algoritmo es de O(n log(m/n)), pero en el peor caso genera un tiempo de O(mn).

Lógica:

Al no haber coincidencia, 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 tras varias coincidencias no se acertó, 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:

Knuth-Morris-Pratt:

KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena 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í , 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.

Con KPM se pre-calcula una tabla donde se localizan las posibles coincidencias de patrón. Una vez calculadas, se procede a tomar la primera celda de la tabla. Si el caracter coincide se procede con el siguiente, si no, el algoritmo se corta y busca la siguiente posible posición.

Debido a que el algoritmo consta de 2 partes donde se analiza una cadena en cada parte, la complejidad resultante es O(m) y O(n), cuya suma resulta ser O(m+n).

Mi código es el siguiente:

Al correrlo me da como resultado lo siguiente:

La imagen muestra que son 1000 caracteres los que se generan aleatoriamente, despues se muestra la tabla de posibles coincidencias, al final muestra el total de caracteres y el tiempo de ejecución ademas de la unica coincidencia en la posición 717.

Analicé esto con gnuplot, haciendo correr el programa varias veces e imprimiendo los resultados en un archivo.

El resultado es:

Vemos por el eje Y que casi alcanzaba los 0.0004 segundos de ejecución por texto.

Por ultimo tambien decidí realizar un analisis del algoritmo fuerza bruta que compara caracter por caracter. La complejidad del algoritmo es O(m) ya que solo opera en una sola corrida.

El código es el siguiente:
Utilicé el mismo scripto para correrlo varias veces e imprimirlo a un archivo de texto, el resultado es el siguiente:

Se puede ver que para este, el máximo tiempo estuvo cerca de 0.0018 segundos. A diferencia del anterior, se puedenotar que crece más rapido.

La comparativa entre las 2: