Placing characters with a higher frequency closer to the root of the tree than characters with a lower one. The algorithm in its core works by building a binary tree based on the frequency of the individual characters. In this example we assume the data we are compressing is a piece of text, as text lends itself very well for compression due to repetition of characters. In this post we walk through implementing a Huffman coder and decoder from scratch using Elixir ⚗️ It utilizes a binary tree as its base and it's quite an easy to grasp algorithm. The smallest piece of data that NSData understands is the byte, but we are dealing in bits, so we need to translate between the two.Huffman coding is a pretty straight-forward lossless compression algorithm first described in 1992 by David Huffman. The codeīefore we get to the actual Huffman coding scheme, it is useful to have some helper code that can write individual bits to an NSData object. For example, if the bits are 11010, we start at the root and go left, left again, right, left, and a final right to end up at d. The value of that leaf node is the uncompressed byte. It reads the compressed bits one-by-one and traverses the tree until it reaches to a leaf node. This gives the Huffman code as 0011 for c.ĭecompression works in exactly the opposite way. When we take a right branch, we emit a 0-bit.įor example, to go from the root node to c, we go right ( 0), right again ( 0), left ( 1), and left again ( 1). Every time we take a left branch, we emit a 1-bit. Notice how each left branch is always 1 and each right branch is always 0.Ĭompression is then a matter of looping through the input bytes and for each byte traversing the tree from the root node to that byte's leaf node. These correspond to the bit-encodings of the leaf nodes. The edges between the nodes are either "1" or "0". The count of the root node is therefore the total number of bytes in the input. The number shown in these nodes is the sum of the counts of their child nodes. The other nodes are "intermediate" nodes. Each leaf node also shows the count of how often it occurs. Note that the tree has 16 leaf nodes (the grey ones), one for each byte value from the input. Based on this table, the algorithm creates a binary tree that describes the bit strings for each of the input bytes.įor our example, the tree looks like this: When compressing a stream of bytes, the algorithm first creates a frequency table that counts how often each byte occurs. Because of the overhead of this frequency table (about 1 kilobyte), it is not beneficial to use Huffman encoding on small inputs.
Given a word build huffman code tree how to#
Otherwise, the decoder does not know how to interpret the bits. That table needs to be transmitted or saved along with the compressed data. To be able to decode these bits, we need to have the original frequency table. We were able to compress the original 34 bytes into merely 16 bytes, a space savings of over 50%!
Given a word build huffman code tree full#
The extra 0-bit at the end is there to make a full number of bytes. Now if we replace the original bytes with these bit strings, the compressed output becomes: 101 10 11010 101
We might get something like this: space: 5 010 u: 1 11001 The more common a byte is, the fewer bits we assign to it. We can assign bit strings to each of these bytes. If you count how often each byte appears, you can see some bytes occur more than others: space: 5 u: 1 Suppose you have the following text, where each character is one byte: so much words wow many compression The idea: To encode objects that occur often with a smaller number of bits than objects that occur less frequently.Īlthough any type of objects can be encoded with this scheme, it is common to compress a stream of bytes.
0 kommentar(er)
