• Choose a category
• All
• Classic-Fiction

By Root 1597 0

to the left, we append to the code; each time we move to the right, we append 1. Once we encounter a leaf node, we store the Huffman code into the table of codes at the appropriate entry. As we store each code, we call the network function htons as a convenient way to ensure that the code is stored in big-endian format. This is the format required when we actually generate the compressed data in the next step as well as when we uncompress it.

While generating the compressed data, we use ipos to keep track of the current byte being processed in the original data, and opos to keep track of the current bit we are writing to the buffer of compressed data. To begin, we write a header that will help to rebuild the Huffman tree in huffman_uncompress. The header contains a four-byte value for the number of symbols about to be encoded followed by the scaled frequencies of all 256 possible symbols, including those that are 0. Finally, to encode the data, we read one symbol at a time, look up its Huffman code in the table, and write each code to the compressed buffer. We allocate space for each byte in the compressed buffer as we need it.

The runtime complexity of huffman_compress is O (n), where n is the number of symbols in the original data. Only two parts of the algorithm depend on the size of the data: the part in which we determine the frequency of each symbol, and the part in which we read the data so we can compress it. Each of these runs in O (n) time. The time to build the Huffman tree does not affect the complexity of huffman_compress because the running time of this process depends only on the number of different symbols in the data, which in this implementation is a constant, 256.

huffman_uncompress

The huffman_uncompress operation (see Example 14.3) uncompresses data compressed with huffman_compress. This operation begins by reading the header prepended to the compressed data. Recall that the first four bytes of the header contain the number of encoded symbols. This value is stored in size. The next 256 bytes contain the scaled frequencies for all symbols.

Using the information stored in the header, we call build_tree to rebuild the Huffman tree used in compressing the data. Once we have rebuilt the tree, the next step is to generate the buffer of restored data. To do this, we read the compressed data bit by bit. Starting at the root of the Huffman tree, whenever we encounter a bit that is in the data, we move to the left; whenever we encounter a bit that is 1, we move to the right. Once we encounter a leaf node, we have obtained the Huffman code for a symbol. The decoded symbol resides in the leaf. Thus, we write this symbol to the buffer of restored data. After writing the symbol, we reposition ourselves at the root of the tree and repeat the process. We use ipos to keep track of the current bit being processed in the compressed data, and opos to keep track of the current byte we are writing to the buffer of restored data. Once opos reaches size, we have regenerated all of the symbols from the original data.

The runtime complexity of huffman_uncompress is O (n), where n is the number of symbols in the original data. This is because for each of the n symbols we decode, the number of levels we must descend in the Huffman tree is a bounded constant that depends on the number of different symbols in the data: in this implementation, 256. The time to build the Huffman tree does not affect the complexity of huffman_uncompress because this process depends only on the number of different symbols in the data.

Example 14.3. Implementation of Huffman Coding

/*****************************************************************************

* *

* ------------------------------- huffman.c ------------------------------ *

* *

*****************************************************************************/

#include

#include

#include

#include

#include "bit.h"

#include "bitree.h"

#include "compress.h"

#include "pqueue.h"

/*****************************************************************************