Project P091
Huffman coding
A text's character counts, the code tree built with a binary heap by always joining the two lightest pieces, the codes it gives and how the tree was built, the text encoded and decoded back, and the bits saved against fixed-width codes.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Short codes for common characters. The program counts a text's characters, builds the code tree, and shows the codes and how the tree was built. It encodes the text and decodes it back, and compares the bits with fixed-width codes. It starts with "this is an example of a huffman tree", which takes 135 bits.
main.eml- the menu, the code table, the building steps, and encoding and decodinghuffman.eml- character counts, the binary heap, building the tree, the codes, encoding and decoding
How each part works:
- Counts, as in the corpus case
char-frequency-table: each character once, with how many times it occurs. - The tree: every character starts as a piece weighing its count. The two lightest pieces are joined into one, again and again, until one piece - the whole tree - is left. The pieces wait in a binary heap, as in the corpus case
binary-heap, so the lightest is always on top. On a tie the older piece goes first, so the same text always gives the same tree. - Codes: 0 for each step to the left, 1 to the right, from the root down. Frequent characters end up near the root, with short codes. No code is the start of another, so a string of bits splits into characters only one way. A text of a single repeated character gets the code 0.
- Huffman's code is the shortest of all codes that write each character as its own run of bits: 135 bits here, against 144 for a 4-bit fixed code and 288 for 8 bits each.
What is checked: menu choices 1 to 6; a text of 2 to 200 characters; bits of 0 and 1 only, ending at the end of a code. An empty answer cancels.
Sessions: sessions/basic.in gives: - the codes and the building steps for the starting text, and its 135 bits decoded back; - "0110" decoded as m and "10010100001" as "the"; - "mississippi": 21 bits, against 22 at 2 bits each.
sessions/bad-input.in gives: - menu choices 0 and x; - the bits "0102" and "1" (it stops inside a code), then a cancel; - the text "a", too short; then "aaaa", whose one character gets the code 0, so "001" cannot be decoded and "000" is "aaa".
Built on the verified corpus cases char-frequency-table (counting each character) and binary-heap (the lightest piece always on top).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Huffman coding ==
Short codes for common characters: the tree, the codes, and the bits saved.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 0
Pick a number from 1 to 6.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> x
Pick a number from 1 to 6.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 0102
Cannot decode: bits are 0 or 1.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 1
Cannot decode: the bits stop in the middle of a character's code.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)>
Cancelled.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 5
text (2 to 200 characters)> a
A text is 2 to 200 characters.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 5
text (2 to 200 characters)> aaaa
A text of 4 characters.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 1
char count code
'a' 4 0
4 characters, 1 different: Huffman needs 4 bits, 1.000 a character.
A fixed code of 1 bit each needs 4; eight bits each, 32.
No other code that writes each character as its own run of bits needs fewer: Huffman's is the shortest.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 001
Cannot decode: with one character every bit is 0.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 000
decoded: aaa
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 6
Bye.
What was typed (18 lines)
0
x
4
0102
4
1
4
5
a
5
aaaa
1
4
001
4
000
6
basic
interpreter: byte-equal== Huffman coding ==
Short codes for common characters: the tree, the codes, and the bits saved.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 1
char count code
space 7 111
'a' 4 000
'e' 4 001
'f' 3 1101
'h' 2 0100
'i' 2 0101
'l' 1 10100
'm' 2 0110
'n' 2 0111
'o' 1 10101
'p' 1 10110
'r' 1 10111
's' 2 1000
't' 2 1001
'u' 1 11000
'x' 1 11001
36 characters, 16 different: Huffman needs 135 bits, 3.750 a character.
A fixed code of 4 bits each needs 144; eight bits each, 288.
No other code that writes each character as its own run of bits needs fewer: Huffman's is the shortest.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 2
join 'l' (1) and 'o' (1) into [2]
join 'p' (1) and 'r' (1) into [2]
join 'u' (1) and 'x' (1) into [2]
join 'h' (2) and 'i' (2) into [4]
join 'm' (2) and 'n' (2) into [4]
join 's' (2) and 't' (2) into [4]
join [2] and [2] into [4]
join [2] and 'f' (3) into [5]
join 'a' (4) and 'e' (4) into [8]
join [4] and [4] into [8]
join [4] and [4] into [8]
join [5] and space (7) into [12]
join [8] and [8] into [16]
join [8] and [12] into [20]
join [16] and [20] into [36]
Each time, the two lightest pieces are joined (on a tie, the older first); the last piece is the whole tree.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 3
bits: 100101000101100011101011000111000011111100111001000011010110101000011111010111011110001110100110... (135 in all)
decoded: this is an example of a huffman tree
The same text: no code is the start of another, so the bits split only one way.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 0110
decoded: m
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 4
bits to decode (0 and 1)> 10010100001
decoded: the
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 5
text (2 to 200 characters)> mississippi
A text of 11 characters.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 1
char count code
'i' 4 11
'm' 1 100
'p' 2 101
's' 4 0
11 characters, 4 different: Huffman needs 21 bits, 1.909 a character.
A fixed code of 2 bits each needs 22; eight bits each, 88.
No other code that writes each character as its own run of bits needs fewer: Huffman's is the shortest.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 3
bits: 100110011001110110111
decoded: mississippi
The same text: no code is the start of another, so the bits split only one way.
1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit
choice> 6
Bye.
What was typed (12 lines)
1
2
3
4
0110
4
10010100001
5
mississippi
1
3
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P091 Huffman coding: a text's character counts and their codes, how the
# tree was built, the text encoded and decoded back, and how many bits it
# saves against a fixed-width code.
import huffman
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def lpad(s, n):
while len(s) < n:
" " + s => s
return s
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def shown(c):
if c == " ":
return "space"
return "'" + c + "'"
def label(tree, node):
if tree[2][node] == -1:
return shown(tree[1][node]) + " (" + str(tree[0][node]) + ")"
return "[" + str(tree[0][node]) + "]"
def ratio(a, b, places):
# a / b to `places` decimals, cut off.
0 => w
a => r
while r >= b:
r - b => r
w + 1 => w
str(w) + "." => s
for i in [1:places]:
r * 10 => r
0 => d
while r >= b:
r - b => r
d + 1 => d
s + str(d) => s
return s
def analyse(text):
huffman.counts(text) => cn
huffman.build(cn[0], cn[1]) => tree
huffman.codes(tree) => table
return [cn, tree, table]
def show_codes(text, a):
a[0] => cn
a[2] => table
" char count code" ^0
0 => total
for i in [0:len(cn[0]) - 1]:
cn[0][i] => c
(" " + pad(shown(c), 7) + lpad(str(cn[1][i]), 5) + " " + table[c]) ^0
total + cn[1][i] * len(table[c]) => total
1 => width
2 => cap
while cap < len(cn[0]):
cap * 2 => cap
width + 1 => width
(str(len(text)) + " characters, " + str(len(cn[0])) + " different: Huffman needs " + str(total) + " bits, " + ratio(total, len(text), 3) + " a character.") ^0
"bits" => unit
if width == 1:
"bit" => unit
("A fixed code of " + str(width) + " " + unit + " each needs " + str(width * len(text)) + "; eight bits each, " + str(8 * len(text)) + ".") ^0
"No other code that writes each character as its own run of bits needs fewer: Huffman's is the shortest." ^0
def steps(a):
a[1] => tree
for st in tree[5]:
(" join " + label(tree, st[0]) + " and " + label(tree, st[1]) + " into [" + str(tree[0][st[2]]) + "]") ^0
"Each time, the two lightest pieces are joined (on a tie, the older first); the last piece is the whole tree." ^0
def round_trip(text, a):
huffman.encode(text, a[2]) => bits
if len(bits) <= 96:
("bits: " + bits) ^0
else:
("bits: " + bits[0:96] + "... (" + str(len(bits)) + " in all)") ^0
huffman.decode(bits, a[1]) => back
if back[0] == text:
("decoded: " + back[0]) ^0
"The same text: no code is the start of another, so the bits split only one way." ^0
def read_bits(a):
plain(input("bits to decode (0 and 1)> ")) => s
if s == "":
"Cancelled." ^0
return
huffman.decode(s, a[1]) => back
if back[1] == "":
("decoded: " + back[0]) ^0
else:
("Cannot decode: " + back[1] + ".") ^0
def new_text(text):
input("text (2 to 200 characters)> ") => s
if s == "":
"Cancelled." ^0
return text
if len(s) < 2 or len(s) > 200:
"A text is 2 to 200 characters." ^0
return text
("A text of " + str(len(s)) + " characters.") ^0
return s
"this is an example of a huffman tree" => text
analyse(text) => a
"== Huffman coding ==" ^0
"Short codes for common characters: the tree, the codes, and the bits saved." ^0
True => running
while running:
"" ^0
"1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show_codes(text, a)
elif choice == "2":
steps(a)
elif choice == "3":
round_trip(text, a)
elif choice == "4":
read_bits(a)
elif choice == "5":
new_text(text) => text
analyse(text) => a
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import huffman
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def lpad(s, n):
while len(s) < n:
s = " " + s
return s
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def shown(c):
if c == " ":
return "space"
return "'" + c + "'"
def label(tree, node):
if tree[2][node] == -1:
return shown(tree[1][node]) + " (" + str(tree[0][node]) + ")"
return "[" + str(tree[0][node]) + "]"
def ratio(a, b, places):
w = 0
r = a
while r >= b:
r = r - b
w = w + 1
s = str(w) + "."
for i in range(1, places+1):
r = r * 10
d = 0
while r >= b:
r = r - b
d = d + 1
s = s + str(d)
return s
def analyse(text):
cn = huffman.counts(text)
tree = huffman.build(cn[0], cn[1])
table = huffman.codes(tree)
return [cn, tree, table]
def show_codes(text, a):
cn = a[0]
table = a[2]
print(" char count code")
total = 0
for i in range(0, len(cn[0])):
c = cn[0][i]
print(" " + pad(shown(c), 7) + lpad(str(cn[1][i]), 5) + " " + table[c])
total = total + cn[1][i] * len(table[c])
width = 1
cap = 2
while cap < len(cn[0]):
cap = cap * 2
width = width + 1
print(str(len(text)) + " characters, " + str(len(cn[0])) + " different: Huffman needs " + str(total) + " bits, " + ratio(total, len(text), 3) + " a character.")
unit = "bits"
if width == 1:
unit = "bit"
print("A fixed code of " + str(width) + " " + unit + " each needs " + str(width * len(text)) + "; eight bits each, " + str(8 * len(text)) + ".")
print("No other code that writes each character as its own run of bits needs fewer: Huffman's is the shortest.")
def steps(a):
tree = a[1]
for st in tree[5]:
print(" join " + label(tree, st[0]) + " and " + label(tree, st[1]) + " into [" + str(tree[0][st[2]]) + "]")
print("Each time, the two lightest pieces are joined (on a tie, the older first); the last piece is the whole tree.")
def round_trip(text, a):
bits = huffman.encode(text, a[2])
if len(bits) <= 96:
print("bits: " + bits)
else:
print("bits: " + bits[0:96] + "... (" + str(len(bits)) + " in all)")
back = huffman.decode(bits, a[1])
if back[0] == text:
print("decoded: " + back[0])
print("The same text: no code is the start of another, so the bits split only one way.")
def read_bits(a):
s = plain(input("bits to decode (0 and 1)> "))
if s == "":
print("Cancelled.")
return
back = huffman.decode(s, a[1])
if back[1] == "":
print("decoded: " + back[0])
else:
print("Cannot decode: " + back[1] + ".")
def new_text(text):
s = input("text (2 to 200 characters)> ")
if s == "":
print("Cancelled.")
return text
if len(s) < 2 or len(s) > 200:
print("A text is 2 to 200 characters.")
return text
print("A text of " + str(len(s)) + " characters.")
return s
text = "this is an example of a huffman tree"
a = analyse(text)
print("== Huffman coding ==")
print("Short codes for common characters: the tree, the codes, and the bits saved.")
running = True
while running:
print("")
print("1) codes 2) how the tree was built 3) encode and decode 4) decode bits 5) new text 6) quit")
choice = plain(input("choice> "))
if choice == "1":
show_codes(text, a)
elif choice == "2":
steps(a)
elif choice == "3":
round_trip(text, a)
elif choice == "4":
read_bits(a)
elif choice == "5":
text = new_text(text)
a = analyse(text)
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
huffman.eml
eml# P091 Huffman coding - a text's character counts, the code tree built by
# always joining the two lightest pieces, the codes it gives, and the text
# encoded and decoded. The tree lives in lists, one entry per node: its
# weight, its character ("" for a joint), and its two children (-1 for a
# leaf). Ties go to the older node, so the same text always gives the same
# tree.
def counts(text):
# The corpus case char-frequency-table: [the characters, sorted],
# [their counts].
{} => seen
[] => chars
for c in text:
if c in seen:
seen[c] + 1 => seen[c]
else:
1 => seen[c]
chars + [c] => chars
# sort the characters, so the tree does not depend on the text's order
for i in [1:len(chars) - 1]:
chars[i] => x
i - 1 => j
while j >= 0 and chars[j] > x:
chars[j] => chars[j + 1]
j - 1 => j
x => chars[j + 1]
[0] * len(chars) => ns
for i in [0:len(chars) - 1]:
seen[chars[i]] => ns[i]
return [chars, ns]
def lighter(w, a, b):
# Node a comes before node b: smaller weight, or the same weight and
# made earlier.
return w[a] < w[b] or (w[a] == w[b] and a < b)
def push(heap, w, x):
# The corpus case binary-heap: add at the end, then swap upwards while
# the parent is heavier.
heap + [x] => heap
len(heap) - 1 => i
while i > 0:
int((i - 1) / 2) => p
if lighter(w, heap[i], heap[p]):
heap[p] => t
heap[i] => heap[p]
t => heap[i]
p => i
else:
0 => i
return heap
def pop(heap, w):
# Take the top, move the last to the top, swap downwards. [top, heap].
heap[0] => top
heap[len(heap) - 1] => last
heap[0:len(heap) - 1] => heap
if len(heap) > 0:
last => heap[0]
0 => i
True => going
while going:
2 * i + 1 => l
l + 1 => r
i => s
if l < len(heap) and lighter(w, heap[l], heap[s]):
l => s
if r < len(heap) and lighter(w, heap[r], heap[s]):
r => s
if s == i:
False => going
else:
heap[s] => t
heap[i] => heap[s]
t => heap[i]
s => i
return [top, heap]
def build(chars, ns):
# [weights, characters, lefts, rights, root, steps]: join the two
# lightest until one is left; each step is [a, b, new node].
[] => w
[] => ch
[] => left
[] => right
[] => heap
for i in [0:len(chars) - 1]:
w + [ns[i]] => w
ch + [chars[i]] => ch
left + [-1] => left
right + [-1] => right
push(heap, w, i) => heap
[] => steps
while len(heap) > 1:
pop(heap, w) => r
r[0] => a
r[1] => heap
pop(heap, w) => r
r[0] => b
r[1] => heap
w + [w[a] + w[b]] => w
ch + [""] => ch
left + [a] => left
right + [b] => right
len(w) - 1 => node
steps + [[a, b, node]] => steps
push(heap, w, node) => heap
return [w, ch, left, right, heap[0], steps]
def codes(tree):
# Each character's code: 0 for the left branch, 1 for the right, from
# the root down. A tree of one character gives it the code "0".
tree[1] => ch
tree[2] => left
tree[3] => right
{} => out
if left[tree[4]] == -1:
"0" => out[ch[tree[4]]]
return out
[[tree[4], ""]] => todo
while len(todo) > 0:
todo[len(todo) - 1] => top
todo[0:len(todo) - 1] => todo
top[0] => node
if left[node] == -1:
top[1] => out[ch[node]]
else:
todo + [[right[node], top[1] + "1"], [left[node], top[1] + "0"]] => todo
return out
def encode(text, table):
"" => bits
for c in text:
bits + table[c] => bits
return bits
def decode(bits, tree):
# Walk from the root, left on 0 and right on 1, and start again at each
# leaf. [text, ""] or ["", why].
tree[1] => ch
tree[2] => left
tree[3] => right
tree[4] => root
"" => out
if left[root] == -1:
for b in bits:
if b != "0":
return ["", "with one character every bit is 0"]
out + ch[root] => out
return [out, ""]
root => node
for b in bits:
if b == "0":
left[node] => node
elif b == "1":
right[node] => node
else:
return ["", "bits are 0 or 1"]
if left[node] == -1:
out + ch[node] => out
root => node
if node != root:
return ["", "the bits stop in the middle of a character's code"]
return [out, ""]
Python projection (huffman.py)
def counts(text):
seen = {}
chars = []
for c in text:
if c in seen:
seen[c] = seen[c] + 1
else:
seen[c] = 1
chars = chars + [c]
for i in range(1, len(chars)):
x = chars[i]
j = i - 1
while j >= 0 and chars[j] > x:
chars[j + 1] = chars[j]
j = j - 1
chars[j + 1] = x
ns = [0] * len(chars)
for i in range(0, len(chars)):
ns[i] = seen[chars[i]]
return [chars, ns]
def lighter(w, a, b):
return w[a] < w[b] or w[a] == w[b] and a < b
def push(heap, w, x):
heap = heap + [x]
i = len(heap) - 1
while i > 0:
p = int((i - 1) / 2)
if lighter(w, heap[i], heap[p]):
t = heap[p]
heap[p] = heap[i]
heap[i] = t
i = p
else:
i = 0
return heap
def pop(heap, w):
top = heap[0]
last = heap[len(heap) - 1]
heap = heap[0:len(heap) - 1]
if len(heap) > 0:
heap[0] = last
i = 0
going = True
while going:
l = 2 * i + 1
r = l + 1
s = i
if l < len(heap) and lighter(w, heap[l], heap[s]):
s = l
if r < len(heap) and lighter(w, heap[r], heap[s]):
s = r
if s == i:
going = False
else:
t = heap[s]
heap[s] = heap[i]
heap[i] = t
i = s
return [top, heap]
def build(chars, ns):
w = []
ch = []
left = []
right = []
heap = []
for i in range(0, len(chars)):
w = w + [ns[i]]
ch = ch + [chars[i]]
left = left + [-1]
right = right + [-1]
heap = push(heap, w, i)
steps = []
while len(heap) > 1:
r = pop(heap, w)
a = r[0]
heap = r[1]
r = pop(heap, w)
b = r[0]
heap = r[1]
w = w + [w[a] + w[b]]
ch = ch + [""]
left = left + [a]
right = right + [b]
node = len(w) - 1
steps = steps + [[a, b, node]]
heap = push(heap, w, node)
return [w, ch, left, right, heap[0], steps]
def codes(tree):
ch = tree[1]
left = tree[2]
right = tree[3]
out = {}
if left[tree[4]] == -1:
out[ch[tree[4]]] = "0"
return out
todo = [[tree[4], ""]]
while len(todo) > 0:
top = todo[len(todo) - 1]
todo = todo[0:len(todo) - 1]
node = top[0]
if left[node] == -1:
out[ch[node]] = top[1]
else:
todo = todo + [[right[node], top[1] + "1"], [left[node], top[1] + "0"]]
return out
def encode(text, table):
bits = ""
for c in text:
bits = bits + table[c]
return bits
def decode(bits, tree):
ch = tree[1]
left = tree[2]
right = tree[3]
root = tree[4]
out = ""
if left[root] == -1:
for b in bits:
if b != "0":
return ["", "with one character every bit is 0"]
out = out + ch[root]
return [out, ""]
node = root
for b in bits:
if b == "0":
node = left[node]
elif b == "1":
node = right[node]
else:
return ["", "bits are 0 or 1"]
if left[node] == -1:
out = out + ch[node]
node = root
if node != root:
return ["", "the bits stop in the middle of a character's code"]
return [out, ""]