Huffman

Explanation

1. Purpose

This program implements the Huffman Coding algorithm from scratch to generate optimal, variable-length prefix codes for a given set of symbols based on their probabilities. It also calculates information theory metrics: Entropy, Average Code Length ($L_{avg}$), and Coding Efficiency.

2. Key Concepts

• Huffman Coding (Greedy Algorithm): Assigns shorter binary codes to more frequent symbols to achieve lossless data compression.
• Bubble Sort: A manual nested loop sort used to keep probabilities in ascending order at each step.
• Tracking with Cell Arrays: Uses dynamic cell arrays (id) to track which original symbols belong to merged nodes.
• Information Theory Metrics:
  • Entropy ($H$): Theoretical minimum average bits needed: $-\sum p_i \log_2(p_i)$.
  • Average Length ($L_{avg}$): Weighted average code length: $\sum p_i \times \text{length}(\text{code}_i)$.
  • Efficiency: Ratio of theoretical minimum to actual average: $(H / L_{avg}) \times 100%$.

3. Code Walkthrough

1. Initialization (Lines 2–8):
   Defines 9 symbols (A–I) and their probabilities. Sets up an array of empty strings code to build the bit sequences and a cell array id to track symbol indices.

2. Huffman Tree Construction (Lines 10–35):
   A while loop runs until all nodes are merged into one:

   • Sorts: Uses a bubble sort to place the two smallest probabilities at indices 1 and 2.
   • Assigns Bits: Prepends "0" to the code of the lowest probability node (L) and "1" to the second lowest (R).
   • Merges: Adds their probabilities, merges their index lists, and removes the first node from the array.

3. Metric Calculations (Lines 37–40):
   Calculates entropy, Lavg (using strlength), and efficiency according to their standard mathematical formulas.

4. Formatted Display (Lines 42–54):
   Uses fprintf to print a neatly aligned table of symbols, probabilities, and generated codes, followed by the calculated metrics.

4. Output

The program outputs:

1. A formatted table mapping each symbol (A through I) to its probability and resulting Huffman code (e.g., higher-probability symbols like 'A' get shorter codes, while 'I' gets a longer code).
2. Summary metrics:
   • Entropy (~2.69 bits/symbol)
   • $L_{avg}$ (~2.75 bits/symbol)
   • Efficiency (~97–98%)