Text Storage Basics

• English text stored as 8 bits (1 byte) per character
• 256 possible combinations of ones/zeros
• Covers English alphabet, numbers, punctuation
• 8 bits chosen: big enough for American computers, power of 2 for programming efficiency
• Fixed bits per character enables fast searching, easy length calculation
• Computers see continuous stream of ones/zeros without spaces

Compression Challenge

• Goal: fit maximum text into minimum bits
• Initial approach: assign most common characters to smaller bit arrangements
  • Space bar = 0
  • Lowercase 'e' = 1
  • Lowercase 't' = 00
• Problem: ambiguity in decoding (00 could be 't' or two spaces)
• No way to distinguish without separators

Huffman Coding Solution (1952)

• Invented by mathematician David Huffman
• Foundation of modern text compression
• Creates unambiguous variable-length codes

Huffman Algorithm Process

• Count character frequency in text
• Create ordered list by usage
• Build Huffman tree:
  • Take two least-used characters as bottom branches
  • Connect with sum of frequencies
  • Add sum back to list in proper position
  • Repeat until single item remains at top
• Assign codes: left path = 0, right path = 1
• Common characters get shorter codes, rare characters get longer codes

Practical Example: "Wild Wild West" Lyrics

• Original: 3,684 characters, nearly 30,000 bits
• Compressed to just over 20,000 bits
• 30% size reduction achieved
• Uppercase 'W': 5 bits instead of 8 (141 occurrences)
• Lowercase 'i': 4 bits (more common)
• 'K': 7 bits (less common)
• Some letters exceed 8 bits but rarely used

Decompression Process

• Read bit stream left to right
• Follow tree: 0 = left fork, 1 = right fork
• When reaching letter, output and restart from top
• Unambiguous path guarantees correct decoding

Efficiency and Limitations

• Huffman coding mathematically optimal for single characters
• Must store translation tree with compressed data
• Inefficient for short texts due to tree overhead
• Modern improvements work on character blocks larger than one
• Basis for ZIP file compression algorithms