Essay Sample on Huffman Trees

Introduction

Huffman coding refers to an encoding algorithm that has lossless data. Huffman coding bases itself on the principle of using a lesser bit number to encode information that occurs more frequently. The method involves sorting values that are numerical from a specific set arranged by order of their frequency. The numbers that are less frequent are eliminated through the Huffman tree, the tree then takes the eliminated frequencies from the sorted list to a new branch (Huffman, 1952). This paper delves into the definition of a Huffman tree, the method of constructing a Huffman tree, the process of encoding and decoding using a Huffman tree and the advantages of Huffman trees.

Is your time best spent reading someone else’s essay? Get a 100% original essay FROM A CERTIFIED WRITER!

Save 25%

A Huffman tree refers to a binary tree applied for compressing data. Every leaf from the tree has a symbol and an integer value. The binary tree reduces the sum of f(i)D(i) over every leaf(i), whereby the terms f(i) refers to the weight or the frequency of the leaf(i). D(i) refers to the distance of the path from the leaf(i) to the root. Every character associated on the tree have unique codes, the codes are either 0's or 1's. The characters get the unique codes as they follow the path from the leaf to the root. The properties of Huffman trees include the following: each node has two children, the frequencies that are smaller have the furthest distance from the root, and the two lowest frequencies are known as siblings.

The method of constructing a Huffman tree is as follows: one should first have a set of numbers and their frequency. The set of numbers should then be sorted by frequency, after which the two numbers with the lowest frequencies are changed into leaves. This alteration leads to a parent node with a frequency that is the sum of the two lowest frequencies. The two lowest frequencies are then removed from the sorted list, and the parent node with the new frequency is inserted into the sorted list. After the shift is complete and the new parent node is inserted the process is repeated until there is only one frequency left on the list (Sharma, 2010). The last remaining frequency is known as the root of the binary tree.

With regards to encoding using a Huffman tree the following steps should be followed: Firstly one should count each character's frequency in the document or file to be encoded, one should then obtain a dummy character and proceed to label the file as its end. The next step is to place the characters as tree nodes and then place them in a priority queue. The frequency of the character in the priority queue acts as the priority of the node. After which one should begin constructing the Huffman tree as discussed above. After creating the tree one should then develop an encoding map, the tree should be inspected as one tries to reach every character. Every character visited to the left of the node that is a 0 and every character visited on the right that is a 1. The characters should then be stored in 0's and 1's, such that the 0's and 1's that one passed through to visit the character should be stated and stored in one sequence. Once the sequence is complete, it is stored in the encoding map together with the character. The next step involves encoding the file, every binary sequence for every character should be written.

With regards to decoding, the following should be applied: one should first read a list that Huffman was applied to encode. The header of the encoded file should be used to build a decoding tree. The same procedure used to make a Huffman tree should be applied. The binaries should then be read for every character. If a binary digit states 1, the right node is followed, and if the binary digit is 0, the left node is followed. After completion of these processes, one should continue until he or she reaches the End Of File (EOF). After reaching the EOF, the file is said to be decoded.

Conclusion

The advantages of Huffman trees include: the algorithm used is easy to apply, Huffman coding is also advantageous as it leads to lossless image compression. Huffman trees ensure that the space provided is efficient. Huffman trees apply prefix codes which ensures that there is a symbol that signifies the end of one code's transmission.

References

Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 1098-1101.

Sharma, M. (2010). Compression using Huffman coding. IJCSNS International Journal of Computer Science and Network Security, 133-141.