-
Notifications
You must be signed in to change notification settings - Fork 1
StuffItAlgorithm3
Miëtek Bak edited this page Dec 1, 2015
·
1 revision
This algorithm simply uses Huffman encoding to encode individual bytes. The data begins with a header specifying the Huffman tree, followed by a bit stream of Huffman codes. All values are read most significant bit first, starting from the most significant bit of each consecutive byte.
The bit stream begins with a header encoding the tree of Huffman codes. To read it, read the root node using this node-reading algorithm:
- Read a single bit from the input stream.
- If this bit is 1, the node being read is a leaf node. Read 8 bits to find the byte value of this leaf.
- If the bit is 0, the node being read is a branch node. Read the 0-branch node followed by the 1-branch node.
To read a byte from the input stream, start at the top node of the Huffman tree. Read a bit, and take the 0 or 1 branch of the tree depending. When you end up at a leaf node, you have the byte value. Do this for all bytes in the stream.