from heapq import heappush, heappop
C = "abcdef"
freq = {'a': 0.45, 'b': 0.13, 'c': 0.12, 'd': 0.16, 'e': 0.09, 'f': 0.05}
def huffman(C, freq):
h = []
n = len(C)
for c in C:
heappush(h, (freq[c], [c]))
for _ in range(n - 1): # Répéter n - 1 fois
fl, l = heappop(h)
fr, r = heappop(h)
heappush(h, (fl + fr, [l, r]))
_, l = heappop(h)
return l
tree = huffman(C, freq)
print(tree)
def encode(tree, s):
code = {}
def extract(tree, path):
if len(tree) == 1: # C'est une feuille
letter = tree[0]
code[letter] = path
else: # C'est un nœud
l, r = tree
extract(l, path + "0")
extract(r, path + "1")
extract(tree, "")
encoding = ""
for letter in s:
encoding += code[letter]
return encoding
print(encode(tree, "cafe"))
def decode(tree, s):
t = tree
plaintext = ""
for letter in s:
if len(t) == 1: # C'est une feuille
plaintext += t[0] # On ajoute l'étiquette de la feuille au message en clair
t = tree
l, r = t
if letter == '0':
t = l
else:
t = r
if len(t) == 1:
plaintext += t[0]
t = tree
return plaintext
print(decode(tree, encode(tree, "cafe")))
