Desconcatenación mediante matrices evolutivas

notas

Fernando Galindo Soria

Julio del 2012

 

Uno de los problemas clásicos de la lingüística y en general del reconocimiento de patrones es el de encontrar los componentes de un objeto (palabras de una oración), y aunque existen múltiples métodos tiende a ser ineficientes, en ese documento planteo un método basado en la combinación de 2 herramientas desarrolladas a mediados de los 80, la primera se basa en la búsqueda de cadenas que se repiten dentro de grandes cadenas y la segunda es el uso de matrices evolutivas.

 

La búsqueda de cadenas en el primer caso consiste en tomar una cadena grande, por ejemplo

 

mgasdfgasdhjkasmhjdefg

 

y buscar dentro de ella cadenas que se repiten.

 

Por facilidad a la cadena la veremos como una oración de algún lenguaje y la representaremos mediante la regla de reescritura

 

S -> mgasdfgasdhjkasmhjdefg

 

Donde S se conoce como Axioma y representa al sistema u objeto que se esta analizando y la flecha -> indica que S se puede rescribir o sustituir por la cadena

 

 

Existen muchos métodos para realizar estas búsquedas pero los mas generales parten de buscar las cadenas mas grandes posibles y dentro de ellas seguir buscando las subcadenas mas grandes posibles que se repiten, y por el otro extremos se tiene los métodos que buscan las cadenas mas pequeñas posibles y luego las combinan para obtener cadenas cada vez mas grandes.

 

En este documento, y con el fin de poder mostrar la aplicación con las matrices evolutivas, mostraremos uno de los métodos que se han desarrollado para encontrar cadenas buscando primero las subcadenas mas pequeñas.

 

Entonces dada la cadena

 

S -> mgasdfgasdhjkasmhjdefg

 

Empezamos de izquierda a derecha y buscamos la cadena mas pequeña que aparece al menos dos veces,  encontrando que as se repite varias veces:

 

S -> mgasdfgasdhjkasmhjdefg

 

Inventamos un nuevo símbolo A y dondequiera que aparece as lo sustituimos por A, quedando

 

S -> mgAdfgAdhjkAmhjdefg

A -> as

 

Siguiendo el proceso encontramos que Ad se repite, por lo que lo sustituimos por B, quedando:

 

S -> mgBfgBhjkAmhjdefg

B -> Ad

A -> as

 

Y asi se sigue mientras sigan encontrándose cadenas repetidas, sustituyendo en este caso fg por C y hj por D, quedando al final la siguiente representación gramatical:

 

S -> mgBCBDkAmDdeC

B -> Ad

A -> as

C -> fg

D -> hj

 

Donde S, A, B, C, D se conocen como elementos no terminales y representan a las cadenas que se repiten.

 

El ejercicio continua para encontrar cadenas mas representativas, para lo cual excepto en el axioma las demás regla se expanden, por ejemplo en este caso en la regla

 

B -> Ad

 

Se puede sustituir A por as (porque se tiene la regla A -> as), quedando

 

B -> asd

 

Con lo que queda:

 

S -> mgBCBDkAmDdeC

B -> asd

A -> as

C -> fg

D -> hj

 

 

El problema con este método es que puede requerir una gran cantidad de comparaciones (en el peor de los casos del orden n2  por lo que si el objeto tiene por ejemplo 100 elementos se pueden requerir de orden de diez mil comparaciones, pero si se tienen 1000 elementos se requiere del orden de 1 millón de comparaciones)

 

Aquí es donde intervienen las matrices evolutivas

 

Se tiene originalmente una matriz M con tantas entradas como elementos básicos se manejen (por ejemplo en texto en código ASCII se manejan 256 elementos, por lo que la matriz seria de 256 por 256) llena de ceros

 

Se va leyendo la secuencia de elementos (caracteres) de la cadena a analizar

Por ejemplo si se tiene la cadena

 

mgasdfgasdhjkasmhjdefg

 

Como los dos primeros elementos son m y g se suma 1 a la entrada que corresponde a la intercepción del renglón m y la columna g, para indicar que existe una secuencia m y g

M(m, g)++;

 

Lo mismo se hace con la intercepción del segundo y tercer elemento g y a

 

M(g, a)++;

 

Y así para todos los elementos de la cadena

 

Al final queda una matriz donde las entradas con valor 0 indican que esas letras no aparecen juntas en las cadenas, las entradas con 1 indican que esos elementos solo aparecen una vez juntos en la cadena y las entradas con un valor de 2 o mas indican que existen al menos dos repeticiones  y esas son las combinaciones que se tiene que sustituir por los elementos no terminales.

 

Se introducen tantos renglones y columnas como elementos no terminales se crearon en este ciclo, y se repite el proceso mientras se tengan cadenas repetidas.