• Author / Uploaded
• jhonis_56

Citation preview

APLICACIÓN DE AUTÓMATAS FINITOS

1. MARCO TEÓRICO Los algoritmos de búsqueda son los siguientes:

2. 3. 4. 5.

Algoritmo de búsqueda: Fuerza bruta Algoritmo de búsqueda: Knuth-Morris-Pratt Algoritmo de búsqueda: Boyer-Moore Algoritmo de búsqueda: Aho-Corasick

A continuación se presenta una breve explicación para cada algoritmo de búsqueda.

a. Fuerza Bruta El algoritmo de Fuerza Bruta consiste en comparar dos cadenas de caracteres. Este algoritmo compara de izquierda a derecha cada letra de la palabra digitada por el usuario con cada letra del nombre del archivo encontrado dentro de la ruta que especifica el usuario. El proceso que realiza este algoritmo de búsqueda es el siguiente: Toma el caracter con el que inicia el patrón.

Comienza a compararlo con cada uno de los carateres del texto, hasta que encuentre la primera coincidencia.

Se para en dicha posición y a partir de allí comienza a verificar si el patrón coincide con el resto del texto.

Si el patrón coincide se detiene la comparación y revisará el siguiente archivo en la ruta. Si por el contrario el patrón no es equivalente, volverá a comparar el caracter de la posición inicial del patrón con el resto de caracteres del texto hasta encontrar de nuevo una coincidencia.

De nuevo se para en dicha posición y a partir de allí comienza a verificar si el patrón coincide con el resto del texto.

Dado que el patrón coincide se detiene la comparación y comenzará a revisar el siguiente archivo en la ruta.

b. Knuth-Morris-Pratt El algoritmo originalmente fue elaborado por Donald Knuth and Vaughan Pratt y de modo independiente por James H. Morris in 1977, pero lo publicaron juntos los tres. El algoritmo KMP tiene por objeto buscar la existencia de palabra dentro de una cadena de texto. 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.

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. Supongamos una tabla ya pre-calculada, ambas cadenas comienzan a compararse usando un puntero de avance para la cadena a buscar (patrón), si ocurre un fallo en vez de volver a la posición siguiente a la primera coincidencia, salta el patrón y lo ubica alineando el carácter del texto con el carácter donde ocurrió el fallo y luego continua con el avance verificando las coincidencias. Este proceso se realiza hasta que el patrón coincida en su totalidad con el texto.1

c. Boyer-Moore El algoritmo de Boyer-Moore es considerado el algoritmo de procesamiento de cadenas 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».

1

Tomado de: http://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt

Este algoritmo consiste en alinear el patrón en una ventana de texto y comparar de derecha a izquierda los caracteres de la ventana con los correspondientes al patrón. Si ocurre una desigualdad se calcula un desplazamiento seguro, el cual permitirá desplazar la ventana hacia delante del texto sin riesgo de omitir alguna coincidencia. Si se alcanza el inicio de la ventana y no ocurre ninguna desigualdad, entonces se reporta una coincidencia y la ventana se desplaza.2

d. Algoritmo de búsqueda: Aho-Corasick El algoritmo de coincidencia de cadenas de texto Aho-Corasick, es un algoritmo de búsqueda inventado por Alfred V. Aho y Margaret J. Corasick. Es un tipo de algoritmo de búsqueda en diccionarios que localiza los elementos de un conjunto finito de cadenas (diccionario) dentro de un 2

Tomado de: http://www.dcc.uchile.cl/~gnavarro/ps/cic04.pdf

texto de entrada. Concuerda con cualquier patrón, por lo que la complejidad del algoritmo es lineal a la longitud de los patrones, más la longitud del texto buscado, más el numero coincidencias que proporcione la salida. Se debe tener en cuenta que debido a que todas las coincidencias se localizan, puede haber un numero de coincidencias cuadrático si coincide cada sub-cadena. El algoritmo construye una máquina de estados finitos que se asemeja a un “trie” con enlaces adicionales entre los distintos nodos internos. Estos enlaces internos permiten transiciones rápidas entre el patrón de coincidencias a otras bifurcaciones del “trie” que comparten un prefijo común. Esto permite al autómata la transición entre el patrón de coincidencias sin la necesidad de dar marcha atrás. Cuando el patrón de diccionario se conoce de antemano, la construcción del autómata se puede realizar una vez fuera de línea y el autómata compilado almacenado para su uso posterior. En este caso, su tiempo de ejecución es lineal en la longitud de la entrada más el número de entradas coincidentes. La siguiente es la estructura de datos de Aho-Corasick construida a partir del diccionario especificado, con cada fila de la tabla que representa un nodo en el “trie”, con la ruta de la columna que indica la secuencia (único) de los caracteres del nodo raíz. En cada paso, el nodo actual se extiende buscando su hijo, y si este no existe, busca el sufijo del hijo, y si eso no funciona, busca el sufijo del sufijo del hijo, finalmente termina en el nodo raíz visto anteriormente.3

3

Tomado de : http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm