1 """ Este codigo es desarrollado por Angelica Maria Juez Suarez y Diego
   2 Andres Sanabria Martin y es software libre bajo los terminos de la licencia
   3 GPL, este programa de acuerdo a un alfabeto calcula el codigo de 
   4 huffman."""
   5 
   6 """Clase que contiene el peso, el simbolo y la hoja del codigo
   7 y se encarga de almacenar el alfabeto que nos dieron."""
   8 class alfabeto:
   9     simbolo=None
  10     peso=None
  11     hoja=None
  12     def __init__(self,simbolo,peso,hoja):
  13         self.simbolo=simbolo
  14         self.peso=float(peso)
  15         self.hoja=hoja
  16 # Clase que contiene el arbol en el cual quedan los simbolos de acuerdo a
  17 # su peso
  18 class arbol:
  19     der=None
  20     izq=None
  21     padre=None
  22     def __init__(self,der,izq,padre):
  23         self.der=der
  24         self.izq=izq
  25         self.padre=padre
  26 #Clase que realiza el codigo de huffman
  27 class Huffman:
  28     Bosque={}
  29     Alfabeto=[]
  30     Arbol=[]
  31     Codigo={}
  32     def __init__(self):
  33         self.Alfabeto.append(None)
  34         self.Arbol.append(None)
  35     # esta funcion lee el alfabeto
  36     def leerAlfabeto(self):
  37         cond=True
  38         opc="si"
  39         cont=1
  40         while cond:
  41             x=raw_input("Digite el simbolo:peso\t")
  42             self.Alfabeto.append(alfabeto(x.split(":")[0],x.split(":")[1],cont))
  43             opc=x=raw_input("Desea ingresar otro simbolo? si, no\n")
  44             if opc=="no":
  45                 cond=False
  46             cont=cont+1
  47     def inicio(self):
  48         for b in range(1,len(self.Alfabeto)):
  49             self.Arbol.append(arbol(None,None,None))
  50         for i in range(1,len(self.Alfabeto)):
  51             #self.Bosque[self.Alfabeto[i].peso]=self.Alfabeto[i].hoja
  52             self.Bosque[self.Alfabeto[i].hoja]=self.Alfabeto[i].peso
  53     def algoritmo(self):
  54         #self.leerAlfabeto()
  55         #self.inicio()
  56         # La variable peso almacena una lista con los pesos del alfabeto
  57         peso=[None]
  58         # La variable cont lleva la posicion en la que se guarda el nuevo bosque
  59         cont=len(self.Bosque)+1
  60         # Mientras aun halla datos en la lista de los pesos
  61         while len(peso)!=0:
  62             #peso=self.Bosque.keys()
  63             # Saca la lista de los valores (pesos) que hay en el bosque
  64             peso=self.Bosque.values()
  65             # Ordena la lista de los pesos
  66             peso.sort()
  67             # El menor
  68             izq=peso.pop(0)
  69             # el segundo menor
  70             der=peso.pop(0)
  71             #self.Bosque[izq+der]=cont
  72             self.Bosque[cont]=izq+der
  73             # El siguiente segmento de codigo se encarga de hallar los indices en los
  74             # cuales se van a guardar en el arbol, esto se debe a la sintaxis del lenguaje pero
  75             # no al algoritmo de huffman
  76 
  77             tmpKeys=self.Bosque.keys()
  78             tmpValues=self.Bosque.values()
  79             indtmp=tmpValues.index(izq)
  80             indizq=tmpKeys[indtmp]
  81             tmpValues.pop(indtmp)
  82             tmpKeys.pop(indtmp)
  83             indtmp=tmpValues.index(der)
  84             indder=tmpKeys[indtmp]
  85 
  86 
  87             self.Arbol.append(arbol(indder,indizq,None))
  88             self.Arbol[indizq].padre=cont
  89             self.Arbol[indder].padre=cont
  90             self.Bosque.pop(indizq)
  91             self.Bosque.pop(indder)
  92             cont=cont+1
  93             print self.Bosque
  94         self.codificar(cont-1,"")
  95         #print self.Codigo
  96     def codificar(self,ind,cod):
  97         print ind
  98         print cod
  99         if len(self.Alfabeto)-1<ind:
 100             self.codificar(self.Arbol[ind].der,cod+"1")
 101             self.codificar(self.Arbol[ind].izq,cod+"0")
 102         else:
 103             self.Codigo[self.Alfabeto[ind].simbolo]=cod