Gramaticas de sufijo, parte 3: implementación en python

Sin más preámbulos, coloco el código Python que, dado una cadena S que se requiere transformar a T mediante una gramática de sufijo (conjunto de NR reglas), hace una búsqueda exhaustiva de todas las posibles maneras de transformar S a T:

#Definir estructura de datos (clase) para el arbol de busqueda
class Arbol:
    def __init__(self, nodo):
        self.nodo = nodo
        self.subarbol=[]
    def __str__(self):
        return str(self.nodo)
    def agregar_hijo(self,regla,hijo):
        self.subarbol.append(tuple([regla,hijo]))
    def contiene_nodo(self,nodo):
        """contiene el arbol al argumento como nodo?"""
        if self.nodo==nodo:
            return True
        else:
            if self.subarbol!=[]:
                cn=False
                for i in self.subarbol:
                    cn=cn or i[1].contiene_nodo(nodo)
                return cn
            else:
                return False           
    def aplicar_reglas(self,arbol):
        #primero aplica todas las reglas al nodo raiz
        for i in range(0,len(reglas)):
            su0=reglas[i][0]
            su1=reglas[i][1]
            no=self.nodo
            if no.endswith(su0):
                nuevo = no[:no.rfind(su0)]+su1
                if nuevo==T or not(arbol.contiene_nodo(nuevo)):
                    self.agregar_hijo(i,Arbol(nuevo))
        #luego se ramifica recursivamente para cada subarbol
        #(si hay subarboles hijos)
        if self.subarbol!=[]:
            for i in self.subarbol:
                i[1].aplicar_reglas(arbol)
    def recorrer_arbol(self,ruta):
        """recorre todo el arbol retornando las rutas que terminan en T"""
        global rutas
        if self.nodo==T:
            rutas.append(ruta)
        else:
            for i in self.subarbol:
                i[1].recorrer_arbol(ruta+[(i[0],i[1].nodo)])

def imprimir_rutas():
    if rutas==[]:
        print "No es posible transformar",S,"en",T,"mediante esta gramatica."
    else:
        for i in range(0,len(rutas)):
            print "Transformacion",i+1,":"
            print S,"\t-->",
            for j in rutas[i]:
                print j[1],"\tRegla",j[0]+1,": (",
                print reglas[j[0]][0],"-->",reglas[j[0]][1],")"
                if not(j==rutas[i][-1]):
                    print "\t-->",
               
#PROGRAMA PRINCIPAL
#Lee S, T y las reglas del archivo
archivo=open("suffix.in","r")
s=archivo.readline().split(" ")
S=s[0]
T=s[1]
NR=int(s[2])
reglas=[]
for i in range(0,NR):
    s=archivo.readline().strip().split(" ")
    reglas+=[tuple(s)]
archivo.close()
#Genera el arbol de busqueda
ab=Arbol(S)
ab.aplicar_reglas(ab)
#recorre el arbol de busqueda para generar las rutas que
#culminan en T
rutas=[]
ab.recorrer_arbol([])
imprimir_rutas()

Este script requiere de un archivo en donde se coloca la cadena inicial S, la cadena final T y el número de reglas (NR) en la primera línea, separados por espacio.  Las siguientes NR líneas del archivo contienen las reglas gramaticales.  Para probar el script, tome las siguientes líneas y cree con ellas un archivo llamado "suffix.in" en el mismo directorio que "suffix.py" (el script de arriba):

AA CB 6
C B
AB BA
AA CC
CC BB
C A
A B

Con esta data de entrada en el archivo "suffix.in", el programa generaría la siguiente salida:

Transformacion 1 :
AA     --> CC     Regla 3 : ( AA --> CC )
       --> CB     Regla 1 : ( C --> B )
Transformacion 2 :
AA     --> CC     Regla 3 : ( AA --> CC )
       --> CA     Regla 5 : ( C --> A )
       --> CB     Regla 6 : ( A --> B )

Gramaticas de sufijo, parte 2: la necesidad de arboles n-arios

Una forma de construir un algoritmo para buscar todas las formas posibles para transformar la cadena S a la cadena T sería esta: partiendo de la cadena inicial S verificamos cuales son las reglas aplicables.  Al aplicar dichas reglas a S obtenemos un conjunto de cadenas que "derivan" de ella.  A su vez, verificamos cuales son las reglas aplicables a cada una de las cadenas derivadas, las aplicamos y obtenemos otras cadenas , ...

Este proceso generaría una especie de árbol de búsqueda, donde un nodo representa una cadena, los arcos que salen de ese nodo representan la aplicación de determinada regla gramatical y estos arcos son aferentes a otros nodos, los cuales derivan del nodo padre mediante la aplicación de reglas.  Este árbol no sería del todo diferente al árbol de búsqueda que generan los programas de ajedrez cuando evalúan todas las posibles jugadas y respuestas del oponente en cada turno.  Para el ejemplo del post anterior, el árbol de búsqueda sería como este:
        
              AA
             /     \
            /       \
          AB     CC
           |         |
          BA     BB
           |
          BB

Se necesita etiquetar cada arco del árbol con el número de regla que produjo la transformación.  Observe que si hay muchas reglas, cada nodo podría tener muchos "hijos"- de ahí que necesitamos una estructura de datos parecida a un árbol n-ario, pero con los arcos etiquetados según la regla aplicada en cada transformación.  También hay que observar que en el proceso de verificar cuales reglas aplican a una cadena, pudiésemos obtener una cadena que ya ha sido producida y ya se encuentra en alguna parte del árbol.  Si agregamos nodos duplicados al árbol, el proceso de generar el árbol no terminaría nunca por la circularidad.  Por otro lado, cuando generamos un nodo igual a la cadena T, no se siguen generando más nodos hijos.  De hecho, aquellos nodos iguales a la cadena T son los únicos que pueden figurar repetidamente en el árbol y siempre se van a encontrar al final de alguna rama.  Si ninguna de las ramas del árbol termina en T, sabremos que no ha sido posible transformar S a T mediante la gramática dada.

Observese también que  una cadena (nodo) podría tener más de dos cadenas derivadas de ella, por lo cual no nos serviría un árbol binario como el que se describe en el capitulo 20 de "Pensar como programador".  Entonces, ¿como crear un árbol n-ario (n-ary tree) en python? Una busqueda por google me arrojo una página donde encontré esta definición de clase:


class Arbol:
    def __init__(self, nodo):
        self.nodo = nodo
        self.subarbol=[]
    def __str__(self):
        return str(self.nodo)
    def agregar_hijo(self,hijo):
        self.subarbol.append(hijo)

Para usar esta clase, creamos varias instancias de arboles, digamos a,b y c:

a=Arbol("arbol A")

b=Arbol("arbol B")

c=Arbol("arbol C")

luego, si por ejemplo queremos agregar los arboles b y c como hijos de a, haríamos lo siguiente:

a.agregar_hijo(b)

a.agregar_hijo(c)

Si queremos acceder a los hijos de a, navegariamos por la lista a.subarbol.  A su vez podemos agregarle nietos a a  (hijos de b o c) .  Este fue el punto de partida para desarrollar el programa que resuelve el problema de las gramaticas de sufijo.

continuara...

Gramáticas de sufijo

En la final del Mundial de Programación de la ACM (edición 2009), apareció un encantador problemita sobre gramáticas de sufijo, que es el problema K (suffix grammars) del problemario. 

Remontándonos a nuestras clases de lenguaje y castellano, un sufijo es una terminación de una palabra y la gramática es el conjunto de reglas que rigen la correctitud de las producción de secuencias de palabras.  En el contexto de la matemática y los lenguajes formales, estos dos conceptos tienen un significado parecido. En el problema en cuestión, una palabra es una secuencia (o cadena) de símbolos, los sufijos son las terminaciones de las palabras y la gramática va a ser el conjunto de reglas que nos van a permitir operar sobre los sufijos de una palabra y sustituirlo por otro sufijo.

Ejemplo:
Supóngase que tenemos una palabra inicial S="AA" que queremos transformar, mediante reglas gramaticales en una palabra T="BB", teniendo para ello las siguientes cuatro reglas:

Regla 1: "A" --> "B"
Regla 2: "AB" --> "BA"
Regla 3: "AA" --> "CC"
Regla 4: "CC" --> "BB"

Una manera de hacerlo sería, partiendo siempre de "AA", utilizar la regla 1 ("A" --> "B") y transformar "AA" en "AB". Luego aplicar la regla 2 para transformar el sufijo "AB" (o sea, toda la palabra) en "BA". Y por último, aplicando la regla 1 nuevamente, "BA" se transforma en "BB".

Otra manera (más directa) sería aplicar las reglas 3 y 4 sucesivamente, lo cual da la transformación en 2 pasos : "AA" --> "CC" --> "BB".

Se quiere desarrollar un programa en python que, dada una cadena inicial S, una cadena final T y un conjunto de reglas (la gramática), encuentre todas las transformaciones de S a T, mediante la aplicación de las reglas gramaticales, por supuesto.

continuará...