1
2 class ShannonFano:
3 """
4 Autor: Diego Andrés Sanabria (diegueus9)
5 Funcionalidad: Implementación del algoritmo de Shannon-Fanon
6 Licencia: GPL v2.0
7 Fecha: 27 de mayo de 2006
8 """
9 def __init__(self):
10 self.codigo=None
11 self.frase=""
12 def dividir(self,alf):
13 uno=0
14 dos=0
15 total=0
16 ind=None
17 dif=0
18 if len(alf)>1:
19 for i in range(0,len(alf)):
20 total=total+alf[i][0]
21 total=float(float(total)/float(2))
22 for cont in range(0,len(alf)-1):
23 uno=0
24 dos=0
25 for cont2 in range(0,cont+1):
26 uno=uno+alf[cont2][0]
27 if ind==None or abs(total-uno)<dif:
28 ind=cont2
29 dif=abs(total-uno)
30 return ind
31 def algoritmo(self, alf, first_time=True):
32 alf.sort()
33 self.codigo=None
34 alf0=[]
35 alf1=[]
36 if len(alf)>2:
37 ind=self.dividir(alf)
38 if ind!=None:
39 alf0=alf[0:ind+1]
40 alf1=alf[ind+1:]
41 if first_time:
42 for i in range(len(alf0)):
43 alf0[i][2]="s"
44 for j in range(len(alf1)):
45 alf1[j][2]="f"
46 else:
47 for i in range(len(alf0)):
48 alf0[i][2]+="s"
49 for j in range(len(alf1)):
50 alf1[j][2]+="f"
51 alf0=self.algoritmo(alf0,False)
52 alf1=self.algoritmo(alf1,False)
53 self.codigo=alf0+alf1
54 return self.codigo
55 else:
56 print "ind es nulo"
57 elif len(alf)==2:
58 self.codigo=alf
59 self.codigo[0][2]+="s"
60 self.codigo[1][2]+="f"
61 return self.codigo
62 elif len(alf)==1:
63 self.codigo=alf
64 return self.codigo
65 def decodificar(self,cad):
66 arc=open("shannon.log","w")
67 self.frase=""
68 self.codigo.sort()
69 self.codigo.reverse()
70 while cad!=None:
71 arc.write("Cadena a Decodificar: "+cad+"\n")
72 for i in range(len(self.codigo)):
73 tcomp=len(self.codigo[i][2])
74 arc.write("Palabra a Comparar: "+self.codigo[i][1]+"\n")
75 arc.write("Codigo de la palabra: "+self.codigo[i][2]+"\n")
76 arc.write("Trozo con el que se compara: "+cad[:tcomp]+"\n")
77 if self.codigo[i][2]==cad[:tcomp]:
78 self.frase+=self.codigo[i][1]
79 cad=cad[tcomp:]
80 if len(cad)==0:
81 cad=None
82 arc.write("Si son iguales.\n")
83 arc.write("Frase: "+self.frase+"\n")
84 break
85 arc.write("No son iguales.\n")
86 arc.write("_________________________________\n")
87 arc.write("*********************************\n")
88 arc.close()
89 return self.frase
90 """self.frase=""
91 self.codigo.sort()
92 self.codigo.reverse()
93 while cad!=None:
94 for i in range(len(self.codigo)):
95 tcomp=len(self.codigo[i][2])
96 if self.codigo[i][2]==cad[:tcomp]:
97 self.frase+=self.codigo[i][1]
98 cad=cad[tcomp:]
99 if len(cad)==0:
100 cad=None
101 break
102 return self.frase"""
103 def codificar(self,cad):
104 self.frase=""
105 other=""
106 acumular=True
107 cambio=False
108 self.codigo.sort()
109 self.codigo.reverse()
110 while cad!=None:
111 for i in range(len(self.codigo)):
112 tcomp=len(self.codigo[i][1])
113 if self.codigo[i][1]==cad[:tcomp]:
114 acumular=False
115 cambio=True
116 if other!="":
117 self.frase+=self.codigo_other()
118 other=""
119 self.frase+=self.codigo[i][2]
120 cad=cad[tcomp:]
121 if len(cad)==0:
122 cad=None
123 break
124 cambio=False
125 if i==len(self.codigo)-1:
126 if acumular:
127 other+=cad[0]
128 cad=cad[1:]
129 elif not cambio:
130 other=cad[0]
131 acumular=True
132 cad=cad[1:]
133 if len(cad)==0:
134 cad=None
135 return self.frase
136 """
137 self.frase=""
138 self.codigo.sort()
139 self.codigo.reverse()
140 while cad!=None:
141 for i in range(len(self.codigo)):
142 tcomp=len(self.codigo[i][1])
143 if self.codigo[i][1]==cad[:tcomp]:
144 self.frase+=self.codigo[i][2]
145 cad=cad[tcomp:]
146 if len(cad)==0:
147 cad=None
148 break
149 return self.frase"""
150 def codigo_other(self):
151 for i in self.codigo:
152 if i[1]=="*":
153 return i[2]
