Duplicate coding

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 26 · page 26.2
Duplicate coding
Huffman's algorithm and optimal codes.
Huffman's algorithm
Builds an optimal prefix code: frequent characters get short codes, rare ones get long ones.
GEF
OGE No. 2
EEG No. 4
Communications.
Huffman uses wood from
Chapter 25
And the principle of greedy choice: we combine the two characters with the lowest frequencies.
01
Equitable and uneven codes
Equivalent code
- All code words of the same length (e.g. ASCII uses 8 bits for each symbol).
Uneven code
- Words of different lengths (e.g. Morse code, Huffman code).
Comparison
Text of AABSB (A:5, B:3, C:2):
Equal 2-bit:
10 symbols x 2 =
20 bits
Huffman:
A=0 (1), B=10 (2), C=110 (3) → 5×1 + 3×2 + 2×3 =
17 bits
Savings: 3 bits (15%).
02
Huffman's algorithm
Ideas
Greedy algorithm: frequent symbols of short codes, rare long codes. Optimal proven.
Algoritm
Create a page for each symbol with its frequency.
Repeat: Take two knots with the lowest frequency, merge into a new knot (sum of frequencies).
Until there is one knot (core) left.
Amount 0 on left rib, 1 on right. Path to sheet = code.
🔧
Huffman code builder
Text or frequency (A:5, B:3, C:7)
03
Average length and entropy
Average code length:
L = Σ pᵢ × lᵢ   (сумма частоты × длина для всех символов)
Shannon entropy:
H = − Σ pᵢ × log₂(pᵢ)   (минимальная возможная средняя длина)
For optimal code:
L ≈ H
The difference is over-coded.
Example
Symbols A(p=0.5), B(p = 0.25), C(p x 0.125), D(p) = 0.125:
H = (0.5 °log20.5 + 0.25·log20.25 + 0.125·log 20.125 + 0.12·log.20.125) = 1.75 bits
Haffman: A=0, B=10, C=110, D=111 \L = 0.5·1 + 0.25 + 0.225·3 + 0.125· 3 = 1.75 bits
The optimal code reaches entropy!
04
Efficiency calculator
📊
Comparison of even and Huffman
Frequencys (symbol: frequency, decimal place)
🎯
Mini-test: 5 questions
XP: 0
🧩
Check yourself out.
5 coding questions · 20 XP for each correct answer