huffman.doc

常用的无损压缩算法源代码

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

           H U F F M A N   C O D E   I M P L E M E N T A T I O N

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

               < ANSI C > version  2.05  -  05/30/95

       Amir Said: [e-mail] - [e-mail]
       DENSIS - Faculty of Electrical Enginnering
       UNICAMP - Campinas, SP, Brazil

       William A. Pearlman - [e-mail]
       Dept. of Electrical, Computer, and Systems Engineering
       Rensselaer Polytechnic Institute - Troy, NY 12180, USA


 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


DESCRIPTION
===========

The files "huffman.h" and "huffman.c" contain an implementation of the
Huffman code. The implementation was adapted to allow simultaneous coding
to more than one file and allows changing the code during the coding
process.

Please send corrections, suggestions and bug reports to 
[e-mail].



FILES
=====

-> huffman.h (header)

-> huffman.c (implementation)

-> hufftst.c (example and test).



REMARKS
=======

* Each encoder/decoder is uniquely associated with a code file,
  defined during initialization.

* The interface functions (with prototypes in "huffman.h") perform ALL
  operations required in the normal usage of the method. The content
  in the data structures should NOT be directly addressed by the user
  program, but only via the interface functions.

* The code can be changed during compression, but a function telling
  the decoder to read the new code must be used whenever it changes.

* There is no "end-of-file" predefined symbol. The encoder and decoder
  have byte counters that allow coding to a given rate and then finding
  the end of the file. Of course, the user can pre-define a special symbol
  to represent the end of the message.

* A code with M symbols will accept symbols from 0 to M-1.

* For faster compression/decompression, data can also be coded in
  binary (uncoded) format.


INCLUSION
=========

The header file "huffman.h" includes the ANSI standard C libraries
<stdlib.h> and <stdio.h>.



DATA TYPES
==========

-> struct Encoder

  * Contains the information about the code file and all the
    data required by the huffman coding algorithm.

-> struct Decoder

  * Contains the information about the code file and all the
    data required by the huffman decoding algorithm.




INTERFACE FUNCTIONS
===================


                          << Encoder >>
                          -------------

-> void Start_Encoder(Encoder * E, char * file_name)

  * Used for initialization. The encoder will overwrite or create the
    file with name "file_name". This function MUST be called before
    using the encoder, and CANNOT be used again unless the function
    "Stop_Encoder" is called first.

-> void Stop_Encoder(Encoder * E)

  * Stops the encoding process and closes the file assigned to the
    encoder.

-> void Write_Code(Encoder * E, int number_of_symbols, long frequency[])

  * Creates the Huffman code optimized for the given symbol frequencies.
    This function also writes the code to be read by the decoder. It must
    be used at least once before calling "Write_Symbol(...)", and can
    be used again whenever necessary.

-> void Write_Symbol(Encoder * E, Adaptive_Model * M, int symb)

  * Adds the symbol with number "symb" to the coded message, using
    the code defined by "Write_Code(...)". The value of "symb" must be
    in the interval [0, m-1], where m is the number of symbols in the data
    alphabet.

-> void Write_Bits(Encoder * E, int b, int word)

  * Writes the "b" least significant bits of "word" to the coded
    message.

-> void Write_Bits(Encoder * E, int b)

  * Writes a single bit defined by "b != 0".

-> long Bytes_Used(Encoder * E)

  * Returns the number of bytes already used by the message. A few
    bits are used to allow a message with an integer number of bytes.
    The result after calling "Stop_Encoder" includes those extra bits.



                          << Decoder >>
                          -------------


-> void Start_Decoder(Decoder * D, char * file_name)

  * Used for initialization (similar to "Start_Encoder").

-> void Stop_Decoder(Decoder * D)

  * Closes the code file.

-> int Read_Code(Decoder * E)

  * Reads the code information written by the encoder's function
    "Write_Code(...)". Must be used before reading any code symbol
    and whenever the code changes. Returns number of data symbols.

-> int Read_Symbol(Decoder * D, Adaptive_Model * M)

  * Reads the next symbol number from the coded message.

-> int Read_Bits(Decoder * D, int b)

  * Reads a word with "b" bits.

-> int Read_Bit(Decoder * D)

  * Reads a single bit d.

-> long Bytes_Read(Decoder * E)

  * Returns the number of bytes read by the decoder.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -