| Author | Josh MacDonald (jmacd@XCF.Berkeley.EDU) |
| Organization | XCF |
| Date | Aug 9, 1996 |
| Purpose | This is a library for adaptive Huffman encoding, as described by Knuth in "Dynamic Huffman Coding", Journal of Algorithms vol 6. |
| Portability | ANSI |
| HuffStruct | This struct has no user defined operations and is left unspecified. It contains the state of the huffman codec and is passed as an argument to allmost all the routines in this package. |
| Bit | If you have to ask, you don't know. |
| Function | Description | Doc |
| Huff_Dump_Stats() | write a table. | N/A |
| Huff_Delete() | deletion. | N/A |
| Huff_Decode_Data() | once ReceiveBit returns 1, this retrieves an index into the alphabet otherwise this returns 0, indicating more bits are required. | N/A |
| Huff_Decode_Bit() | receives a bit at a time and returns true when a complete code has been received. | N/A |
| Huff_Get_Encoded_Bit() | Should be called as many times as Huff_Encode_Data returns. | N/A |
| Huff_Encode_Data() | Takes Huffman transmitter h and n, the nth elt in the alphabet, and returns the number of required to encode n. | N/A |
| Huff_Initialize_Adaptive_Encoder() | returns an initialized Huffman encoder for an alphabet with the given size. returns NULL if enough memory cannot be allocated | N/A |
| Huff_Initialize_Training_Encoder() | returns an initialized encoder for encoding via a fixed table and raining that table for future uses. | More |
| Huff_Initialize_Fixed_Encoder() | returns an initialized encoder for encoding via a fixed table which was hard coded. The header to include can be produced by a stats file using the utility stats2header. | N/A |
| huff.h | Interface |
| huff.c | Implementation |
| stats2header.c | A utility for generating header files from tables. |
| stats.h | Table of frequencies for Huffman compression trees (automatically generated by stat2header. |
See the bottom of huff.c for an example.
This is a library for adaptive Huffman encoding, as described by Knuth in "Dynamic Huffman Coding", Journal of Algorithms vol 6.
A test program compact is compiled by default, which uses the algorithm to compress and uncompress files. The driver is very simple and accepts only the -d flag, and will not use the standard io. The -d flag or calling the program under the name 'uncompact' will cause it to uncompress. It writes compressed files with a .jz extensions.
The stats2header file takes 3 arguments, infile outfile table_name. infile is the name of a file containing whitespace separated numbers, the first being the alphabet size and the rest being the frequency of each element in the alphabet.
Do not use zero-frequency elements in these stats files, I haven't accounted for those yet.