Question

Suppose a file contains the letters \(a, b, c\), and \(d\). Nominally, we require 2 bits per letter to store such a file. (a) Assume the letter \(a\) occurs \(50 \%\) of the time, \(b\) occurs \(30 \%\) of the time, and \(c\) and \(d\) each occur \(10 \%\) of the time. Give an encoding of each letter as a bit string that provides optimal compression. Hint: Use a single bit for \(a\). (b) What is the percentage of compression you achieve above? (This is the average of the compression percentages achieved for each letter, weighted by the letter's frequency.) (c) Repeat this, assuming \(a\) and \(b\) each occur \(40 \%\) of the time, coccurs \(15 \%\) of the time, and \(d\) occurs \(5 \%\) of the time.

Short answer

The optimal encoding for (a) is a=1, b=01, c=001, and d=000, achieving 20% compression. For (c), there is no compression achieved.

Step-by-step solution

Title - Understand Huffman coding

Huffman coding is an algorithm used for lossless data compression. It assigns shorter bit codes to more frequent characters and longer bit codes to less frequent characters.

Title - Frequency of letters

(a) Based on the given frequencies: a: 50%, b: 30%, c: 10%, d: 10%.

Title - Create Huffman Tree

Create a Huffman tree to determine the optimal bit strings for each letter. Merge the least frequent nodes first: 1. c (10%) and d (10%) -> cd (20%) 2. cd (20%) and b (30%) -> bcd (50%) -> 3. bcd (50%) and a (50%) -> the root (100%)

Title - Assign bit strings

Assign bit strings based on the Huffman tree structure: a = 1 (single bit as per hint), b = 01, c = 001, d = 000.

Title - Calculate average bits per letter

Average bits per letter = 1*0.5 + 2*0.3 + 3*0.1 + 3*0.1 = 1.6 bits.

Title - Compute percentage of compression

Original bits per letter = 2. Percentage compression = (1 - (average bits/ original bits)) * 100 = (1 - (1.6 / 2)) * 100 = 20%.

Title - Repeat for new frequencies

(c) Frequencies: a: 40%, b: 40%, c: 15%, d: 5%

Title - New Huffman tree

1. c (15%) and d (5%) -> cd (20%) 2. cd (20%) and either a or b (40%) -> cd+a or cd+b (60%) 3. 60% node and remaining 40% node -> the root (100%)

Title - Assign new bit strings

a = 01 (or 10), b = 00, c = 111, d = 110.

Title - Calculate new average bits per letter

Average bits per letter = 2*0.4 + 2*0.4 + 3*0.15 + 3*0.05 = 2.15 bits.

Title - Compute new percentage of compression

New Percentage compression = (1 - (2.15 / 2)) * 100 = -7.5% (No compression achieved).

Key concepts

Data Compression

Data compression is a technique used to reduce the size of data files. One of the popular methods for data compression is called Huffman coding. This method assigns shorter bit codes to more frequent characters and longer bit codes to less frequent characters.
For example, if a file contains the letters 'a', 'b', 'c', and 'd', each requiring 2 bits for representation, Huffman coding can reduce the number of bits needed based on the frequency of each letter. By assigning shorter codes to more frequent letters, we can significantly reduce the file size.

Lossless Compression

Lossless compression is a type of data compression where the original data can be perfectly reconstructed from the compressed data. This is critical for applications where losing any part of the data is unacceptable, such as text files and certain image formats.
Huffman coding is a lossless compression algorithm. It ensures that once data is compressed and then decompressed, we obtain the exact original data. In our exercise on Huffman coding, each letter is assigned a unique bit string such that there is no ambiguity in decoding, ensuring that the exact input sequence is reconstructed.

Average Bits per Letter

The concept of average bits per letter is crucial for understanding the efficiency of a compression algorithm. It represents the average number of bits used to encode each letter based on its frequency in the data.
In our example, after utilizing Huffman coding with the given frequencies of letters (a, b, c, d), the average bits per letter can be calculated as follows:
a: 50% — 1 bit (0.5 * 1)
b: 30% — 2 bits (0.3 * 2)
c: 10% — 3 bits (0.1 * 3)
d: 10% — 3 bits (0.1 * 3)
Summing these gives the average bits per letter: 1.6 bits.
Lower average bits per letter indicate better compression.

Percentage of Compression

The percentage of compression achieved is another key metric to assess the effectiveness of data compression. It is calculated by comparing the average bits per letter before and after compression.
In our example, the original bits per letter are 2. Using Huffman coding, we achieve an average of 1.6 bits per letter. The percentage of compression can be calculated using the formula:
\[(1 - (bits_{average new} / bits_{original})) * 100\]
So, for our case:
\[(1 - (1.6 / 2)) * 100 = 20%\]
This tells us we achieved a 20% reduction in file size.