How to Compress Data Using Huffman Encoding

Encoding

1. How to Compress Data Using Huffman Encoding Picture 1
   Count the frequency of each character in the file to be encoded. Include a dummy character to mark the end of the file -- this will be important later. For now, call it the EOF (end of file) and mark it as having a frequency of 1.

   1. For example, if you want to encode a text file reading "ab ab cab," you would have 'a' with frequency 3, 'b' with frequency 3, ' ' (space) with frequency 2, 'c' with frequency 1, and EOF with frequency 1.
2. How to Compress Data Using Huffman Encoding Picture 2
   Store characters as tree nodes and put them into a priority queue. You'll be building a big binary tree with each character as a leaf, so you should store the characters in a format such that they can become nodes of the tree. Place these nodes into a priority queue with each character's frequency as its node's priority.

   1. A binary tree is a data format where each piece of data is a node that can have up to one parent and two children. It's often drawn as a branching tree, hence the name.
   2. A queue is an aptly named data collection where the first thing to go into the queue is also the first thing to come out (like waiting in line). In a priority queue, the data are stored in order of their priority, so that the first thing to come out is the most urgent thing, the thing with the smallest priority, rather than the first thing enqueued.
   3. In the "ab ab cab" example, your priority queue would look like this: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
3. How to Compress Data Using Huffman Encoding Picture 3
   Begin to build your tree. Remove (or dequeue) the two most urgent things from the priority queue. Create a new tree node to be the parent of these two nodes, storing the first node as its left child and the second as its right child. The priority of the new node should be the sum of the priorities of its child. Then enqueue this new node in the priority queue.

   1. The priority queue now looks like this: {' ':2, new node:2, 'a':3, 'b':3}
4. How to Compress Data Using Huffman Encoding Picture 4
   Finish building your tree: repeat the above step until there is only one node in the queue. Note that in addition to the nodes you created for the characters and their frequencies, you will also be dequeuing, turning into trees, and re-enqueueing parent nodes, nodes that are already themselves trees.

   1. When you're finished, the last node in the queue will be the root of the encoding tree, with all the other nodes branching off from it.
   2. The most frequently used characters will be the leaves closest to the top of the tree, while the rarely used characters will be positioned at the bottom of the tree, farther away from the root.
5. How to Compress Data Using Huffman Encoding Picture 5
   Create an encoding map. Walk through the tree to reach each character. Every time you visit a node's left child, that's a '0'. Every time you visit a node's right child, that's a '1'. When you get to a character, store the character with the sequence of 0s and 1s that it took to get there. This sequence is what the character will be encoded as in the compressed file. Store the characters and their sequences in a map.

   1. For example, start at the root. Visit the root's left child, and then visit that node's left child. Since the node you're at now doesn't have any children, you've reached a character. This is ' '. Since you walked left twice to get here, the encoding for ' ' is "00".
   2. For this tree, the map will look like this: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
6. How to Compress Data Using Huffman Encoding Picture 6
   In the output file, include the encoding map as a header. This will allow the file to be decoded.
7. How to Compress Data Using Huffman Encoding Picture 7
   Encode the file. For each character in the file to be encoded, write the binary sequence you've stored in the map. Once you've finished encoding the file, make sure to add the EOF to the end.

   1. For the file "ab ab cab", the encoded file will look like this: "1011001011000101011011".
   2. Files are stored as bytes (8 bits, or 8 binary digits). Because the Huffman Encoding algorithm doesn't use the 8-bit format, encoded files will often not have lengths that are multiples of 8. The remaining digits will be filled in with 0s. In this case, two 0s would be added at the end of the file, which looks like another space. This could be a problem: how would the decoder know when to stop reading? However, because we included an end-of-file character, the decoder will get to this and then stop, ignoring anything else that's been added on after.