What is Huffman Text Compression?
I was in my second semester of computer science engineering, when our professor asked me and my friends to create a file compression program. So we searched about various methods to perform this operation.
Huffman Compression is a Greedy-based algorithm which is also known as lossless data compression technique.
What is Huffman Compression?
Huffman coding is a method which is used to compress data and reduce it’s size. This method is named behind its developer David Huffman. It is generally used to compress the data based on the frequency of character.
How does Huffman Coding works?
The Huffman compression works in 6 different phases, it works by assigning variable-length codes to characters or symbols in a way that more frequent characters are assigned shorter codes, and less frequent characters are assigned longer codes. This results in a compact representation of the data, where frequently occurring symbols are encoded with fewer bits, while less frequent symbols are encoded with more bits.
- Frequency Table: The First step is to analyze the input and create a table which has a counter of chracthers.
- Building Huffman Tree: After building Frequency table we will proceed to Tree building. The Huffman tree is a binary tree where each leaf node represents a character or symbol, and each internal node represents a combined frequency of its child nodes. Each tree consist of single character and its frequency. Select 2 trees with lowest frequency and merge them into internal node. The Frequency of new internal node is the sum of its frequencies. Will will do this process until one tree remains.
3. Assigning Huffman Codes: Now we will Traverse through the Huffman tree from the root to each leaf, generating the Huffman codes for each character as you go. Assign ‘0’ for a left branch and ‘1’ for a right branch. The path from the root to each leaf node gives the binary representation of the character’s Huffman code.
4. Creating Encoded Data: Replace each character in the original input data with its corresponding Huffman code. This transforms the input data into a sequence of bits that represents the compressed data.
5. Storing Huffman Tree Information: At the end of the coded part we will attach the Huffman Tree information as well as it needs to be decoded later for that we need this information.
6. Compression: The compression achieved by Huffman Coding depends on the frequency distribution of characters in the input data. Characters with higher frequencies are assigned shorter codes, leading to more efficient storage for frequently occurring symbols.
In our project we were compressing a basic txt file. So i am attaching the code for that, with the help of that code you can compress any txt file. As we did not had much time to complete this project so we only submitted compressor but it is fairly easy to convert the file into original file.
For better understanding you can read C program for Text Compression using Huffman Coding written by Adeesha Savinda de Silva. He wrote a very indepth blog on this topic and his blog helped us out for the project. As his blog is not showing on intial search result that’s why i re-wrote a blog on this topic.
Example
We executed the program with sample file named Check.txt
After entering the filename it will read the file and prints a sample output. And it will also proint the frequency table output and Encoded part.
As you can see in second image the Input byte was 46 and Output byte was 24 the program was able to compress the file by 47.83%.
The output will return a coded file and a frequency table file.
