Shannon Fano Coding

Explanation

1. Purpose

This program implements Shannon-Fano Coding, a lossless data compression algorithm. It generates variable-length binary codes for a set of symbols, assigning shorter binary codes to higher-probability symbols to minimize average message length.

2. Key Concepts

• Divide-and-Conquer / Recursion: Successively dividing a set of symbols into two subsets of roughly equal total probability.
• Sorting (Bubble Sort): Rearranging symbols and tracking their original indices in descending order of probability.
• Prefix-Free Codes: Ensuring no code word is a prefix of another, enabling unambiguous decoding.

3. Code Walkthrough

1. Input & Bubble Sort (Lines 3–21):
   • Sets up probabilities p and symbol identifiers id.
   • Sorts p in descending order using a standard Bubble Sort while swapping id simultaneously to preserve symbol tracking.
2. Shannon-Fano Function (shannon_fano):
   • Base Case: If a group contains only one symbol (first >= last), recursion stops.
   • Optimal Partitioning: A loop finds the index split that minimizes the difference between the sum of probabilities on the left and right (diff = abs(s - (total - s))).
   • Bit Assignment: Appends '0' to all symbols in the left subgroup (first to split) and '1' to all symbols in the right subgroup (split + 1 to last).
   • Recursive Step: Calls itself recursively on the left and right halves.
3. Display (Lines 26–30):
   • Prints the original symbol label (m_id), its probability, and its assigned binary codeword.

4. Output

When executed, the program produces:

Shannon-Fano Codes
m_4 (p = 0.50) = 0
m_3 (p = 0.40) = 10
m_2 (p = 0.20) = 110
m_1 (p = 0.15) = 1110
m_5 (p = 0.08) = 11110
m_6 (p = 0.07) = 11111