HUFFMAN CODING
Huffman Coding Encoding
During encoding, Huffman coding constructs a binary tree based on the frequency of symbols in the input data. This tree is then traversed to assign variable-length codes to each symbol, with more frequent symbols receiving shorter codes.
Huffman Coding Decoding
During decoding, the encoded data is passed through the Huffman tree, with each bit sequentially used to traverse the tree until a leaf node (symbol) is reached, which corresponds to the original symbol.
Advantages and Disadvantages of Huffman coding
-Advantages
- Provides lossless compression, meaning no data is lost during compression and decompression.
- Achieves good compression ratios, particularly for data with uneven symbol frequencies.
- Relatively simple to implement.
- Disadvantages
- Requires the frequency of symbols in the input data to be known in advance for efficient compression.
- Not suitable for all types of data; compression effectiveness depends on the distribution of symbol frequencies.
Where is Huffman coding applied?
- Text compression: Huffman coding is particularly effective for compressing text files due to the varying frequencies of characters.
- Image compression: Huffman coding can be used as a component in image compression algorithms, especially in lossless compression techniques.
Performance issues of Huffman coding:
- Timing - Huffman coding typically has fast encoding and decoding times.
- Compression Factor - The compression factor depends on the distribution of symbol frequencies in the input data.
- Suitability for Real-Time - Huffman coding is suitable for real-time applications with relatively low computational overhead.
Compress "BILL BEATS BEN." using Huffman coding
BILL BEATS BEN.
- First, calculate the frequency of each character:
- B: 3, I: 1, L: 2, E: 2, A: 1, T: 2, S: 1, N: 1, .: 1
- Construct a Huffman tree based on the character frequencies.
- Assign codes to each character based on the Huffman tree:
- B: 0, I: 101, L: 100, E: 110, A: 1110, T: 1111, S: 1100, N: 1010, .: 11101
- Encode the message using the assigned codes: 010011001011100111110111001.
- The compressed message is "010011001011100111110111001."
Huffman Coding #huffmanCoding
Comments
Post a Comment