Huffman, a graduate student at MIT in 1952, published this paper to outline what became known as Huffman coding, the most efficient binary code. Fano, his teacher, worked with Shannon to create Shannon-Fano coding, which used a top-down binary tree to create their own encoding. Huffman coding uses bottom-up encoding, which is provably optimal.
from collections import Counter
from heapq import heapify, heappop, heappush
from dataclasses import dataclass
from typing import Optional
@dataclass
class Node:
ch: Optional[str]
freq: int
left: Optional['Node'] = None
right: Optional['Node'] = None
def __lt__(self, other):
return self.freq < other.freq
def get_huffman_tree(text):
if not text:
return
freq = Counter(text)
pq = [Node(k, v) for k, v in freq.items()]
heapify(pq)
while len(pq) > 1:
left, right = heappop(pq), heappop(pq)
new_freq = left.freq + right.freq
heappush(pq, Node(None, new_freq, left, right))
return pq[0]
print(get_huffman_tree('AADDDDDBBBE'))