gen-define-huffman-coding-and-give-one-short-worked-example-31eb

Define Huffman coding and give one short worked example.

# Huffman Coding **Huffman coding** is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequency of occurrence. More frequent characters get shorter codes, while less frequent characters get longer codes. ## Key Properties: - **Prefix-free**: No code is a prefix of another code - **Optimal**: Produces the minimum average code length for given character frequencies ## Worked Example **Encode the string: "AAAAABBBCCD"** ### Step 1: Count frequencies - A: 5 - B: 3 - C: 2 - D: 1 ### Step 2: Build Huffman tree (combine smallest frequencies repeatedly) ``` (11) / \ (5) (6) A / \ (3) (3) B / \ (2) (1) C D ``` ### Step 3: Assign codes (0=left, 1=right) - A: **0** - B: **10** - C: **110** - D: **111** ### Step 4: Encode "AAAAABBBCCD" → **0 0 0 0 0 10 10 10 110 110 111** **Result**: 21 bits (vs 44 bits using fixed 2-bit codes) **Compression ratio**: 21/44 ≈ 48% of original size