Skip to content

Instantly share code, notes, and snippets.

@lovasoa
Forked from anonymous/gist:1dffa21ee8c4b9d7a277f4cf29c04057
Last active July 27, 2016 17:57
Show Gist options
  • Save lovasoa/233f5520aec531320407db60ad226867 to your computer and use it in GitHub Desktop.
Save lovasoa/233f5520aec531320407db60ad226867 to your computer and use it in GitHub Desktop.
from heapq import heappush, heapify, heappop
#Question1
def table_frequences(texte):
table={}
for i in texte:
if i in table:
table[i]=table[i]+1
else:
table[i]=1
return table
#question2
class OccuLettre(tuple):
def __lt__(self, other):
return self[0] < other[0]
def __eq__(self, other):
return self[0] == other[0]
def arbre_huff(occurrences):
#construction d'un tas
tas=[OccuLettre((occ, lettre)) for (lettre, occ) in occurrences.items()]
heapify(tas) #trier le tas
while len(tas)>=2:
occ1, noeud1 = heappop(tas) #noeud de + petit poids occ1
occ2, noeud2 = heappop(tas) #noeud de 2ème + petit poids
heappush(tas, OccuLettre((occ1+occ2,{0: noeud1, 1: noeud2}))) #ajoute au tas le noeud de poids occ1+occ2
return heappop(tas)[1]
def affiche_encodage(texte):
table = table_frequences(texte)
arbre = arbre_huff(table)
res = []
def print_arbre(a, path=""):
for k,v in a.items():
pathv = path + str(k)
if isinstance(v, dict):
print_arbre(v, pathv)
else:
res.append((pathv, v))
print_arbre(arbre)
res.sort()
return res
texte = input("Texte? ")
print(affiche_encodage(texte))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment