Tpicos IBsqueda de cadenasSemana 7Seguridad y encriptacin

Objetivos GeneralesEntender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo nfasis en los algoritmos de internet, seguridad y redes.

Objetivo EspecficoImplementar algoritmos para seguridad y encriptacin.

Objetivo InstruccionalImplementar algoritmos para el procesamiento y reconocimiento de patrones en secuencia de cadenas.

A menudo sucede que los datos a procesar no se descomponen lgicamente en registros independientes que representen pequeas partes identificables. Este tipo de datos se caracteriza fcilmente por el hecho de que se pueden escribir en forma de cadenas: series lineales de caracteres.

Las cadenas son el centro de los sistemas de tratamiento de texto, que proporcionan una gran variedad de posibilidades para la manipulacin de textos. Tales sistemas procesan cadenas alfanumricas, que pueden definirse como serie de letras, nmeros y caracteres especiales. Otro tipo de cadena es la cadena binaria, que es una simple serie de valores 0 y 1. Los dos tipos de cadena son equivalentes.

Una operacin fundamental sobre las cadenas es el reconocimiento de patrones: dada una cadena alfanumrica de longitud N y un patrn de longitud M, encontrar una ocurrencia del patrn dentro del texto.

El reconocimiento de patrones se puede caracterizar como un problema de bsqueda en el que el patrn seria la clave.El objetivo de bsqueda en cadenas es hallar la localizacin de un patrn de texto especfico dentro de un texto largo (ejm., una oracin, un prrafo, un libro, etc.). En el cual los requisitos son velocidad y eficiencia.

Se alinea la primera posicin del patrn con la primera posicin del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrn, esto es, se encontr una ocurrencia del patrn en el texto, o hasta que se encuentre una discrepancia.

Si se detiene la bsqueda por una discrepancia, se desliza el patrn en una posicin hacia la derecha y se intenta calzar el patrn nuevamente.

Suponga que se est comparando el patrn y el texto en una posicin dada, cuando se encuentra una discrepanciaSea X la parte del patrn que coincide con el texto, e Y la correspondiente parte del texto, y suponga que el largo de X es j. El algoritmo de fuerza bruta mueve el patrn una posicin hacia la derecha, sin embargo, esto puede o no puede ser lo correcto en el sentido que los primeros j-1 caracteres de X pueden o no pueden coincidir con los ltimos j-1 caracteres de Y.

La observacin clave que realiza el algoritmo Knuth-Morris-Pratt (KMP) es que X es igual a Y, por lo que la pregunta planteada en el prrafo anterior puede ser respondida mirando solamente el patrn de bsqueda, lo cual permite precalcular la respuesta y almacenarla en una tabla.

Por lo tanto, si deslizar el patrn en una posicin no funciona, se puede intentar deslizarlo en 2, 3, ..., hasta j posiciones.

Por ejemplo:

Cuando se esta buscando X=10100111 en Y=1010100111, se comienza por detectar la discordancia en el quinto carcter, pero se debe retroceder al tercero para continuar la bsqueda, puesto que de lo contrario se perdera la concordancia.

Maquina de estados finitos:

Para determinar el desplazamiento (posiciones de reinicializacin) en caso de no existir concordancia. Cada desplazamiento hacia atrs corresponde a desplazar una posicin hacia la derecha del patrn con respecto a la cadena evaluada, y se reinicia el proceso de reconocimiento.

Rabin-KarpEl mtodo se basa en calcular la funcin de dispersin para la posicin i del texto conociendo su valor para la posicin i-1.

Se supone que se transforman los M caracteres en nmeros agrupndolos en una palabra que podra tratarse como un numero entero. Esto equivale a escribir los caracteres como nmeros en un sistema de base d, donde d es el numero de caracteres posibles.

Rabin-KarpCalcula un valor hash para el patrn, y para cada subsecuencia de M-caracteres de texto.

Si los valores hash son diferentes, se calcula un valor para la siguiente secuencia.

Si los valores hash son iguales se usa una comparacin de Fuerza Bruta.

Valor Hash de AAAAA es 37Valor Hash deAAAAH es 100Rabin-Karp1) AAAAAAAAAAAAAAAAAAAHAAAAH371002) AAAAAAAAAAAAAAAAAAAHAAAAH371003) AAAAAAAAAAAAAAAAAAAHAAAAH37100..N) AAAAAAAAAAAAAAAAAAAHAAAAH100=100

TRABAJO

Investigar algoritmo de Boyer-Moore para la bsqueda de cadenas

Tpicos IBsqueda de cadenasSemana 7Seguridad y encriptacin