📄 101-112.html
字号:
<!DOCTYPE HTML PUBLIC "html.dtd"><HTML><HEAD><TITLE>The Data Compression Book-:A Significant Improvement: Adaptive Huffman Coding</TITLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><SCRIPT><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes');}//--></SCRIPT></HEAD><BODY BGCOLOR="#FFFFFF" VLINK="#DD0000" TEXT="#000000" LINK="#DD0000" ALINK="#FF0000"><TD WIDTH="540" VALIGN="TOP"><!-- <CENTER><TABLE><TR><TD><FORM METHOD="GET" ACTION="http://search.itknowledge.com/excite/cgi-bin/AT-foldocsearch.cgi"><INPUT NAME="search" SIZE="20" VALUE=""><BR><CENTER><INPUT NAME="searchButton" TYPE="submit" VALUE="Glossary Search"></CENTER><INPUT NAME="source" TYPE="hidden" VALUE="local" CHECKED> <INPUT NAME="bltext" TYPE="hidden" VALUE="Back to Search"><INPUT NAME="sp" TYPE="hidden" VALUE="sp"></FORM></TD><TD><IMG SRC="http://www.itknowledge.com/images/dotclear.gif" WIDTH="15" HEIGHT="1"></TD><TD><FORM METHOD="POST" ACTION="http://search.itknowledge.com/excite/cgi-bin/AT-subscriptionsearch.cgi"><INPUT NAME="search" SIZE="20" VALUE=""><BR><CENTER><INPUT NAME="searchButton" TYPE="submit" VALUE=" Book Search "></CENTER><INPUT NAME="source" TYPE="hidden" VALUE="local" CHECKED> <INPUT NAME="backlink" TYPE="hidden" VALUE="http://search.itknowledge.com:80/excite/AT-subscriptionquery.html"><INPUT NAME="bltext" TYPE="hidden" VALUE="Back to Search"><INPUT NAME="sp" TYPE="hidden" VALUE="sp"></FORM></TD></TR></TABLE></CENTER> --><!-- ISBN=1558514341//--><!-- TITLE=The Data Compression Book-//--><!-- AUTHOR=Mark Nelson//--><!-- PUBLISHER=IDG Books Worldwide, Inc.//--><!-- IMPRINT=M & T Books//--><!-- CHAPTER=4//--><!-- PAGES=101-112//--><!-- UNASSIGNED1//--><!-- UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="097-101.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="../ch05/113-115.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><H3><A NAME="Heading17"></A><FONT COLOR="#000077">The Code</FONT></H3><P>The code for the Adaptive Huffman compressor is listed next. This single module is contained on the source disk in the file AHUFF.C. Building the compression routine requires that you compile this file and link it with the utility routines discussed in the last chapter: BITIO.C, ERRHAND.C, and MAIN-C.C. To build the decompression routine you substitute MAIN-E.C. The two arguments for both programs are simply an input file followed by an output file.</P><!-- CODE //--><PRE>/*************************** Start of AHUFF.C *************************/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>#include "bitio.h"#include "errhand.h"char *CompressionName = "Adaptive Huffman coding, with escape codes";char *Usage = "infile outfile";#define END_OF_STREAM 256#define ESCAPE 257#define SYMBOL_COUNT 258#define NODE_TABLE_COUNT ( ( SYMBOL_COUNT * 2 ) - 1 )#define ROOT_NODE 0#define MAX_WEIGHT 0X8000#define TRUE 1#define FALSE 0*/* This data structure is all that is needed to maintain an adaptive* Huffman tree for both encoding and decoding. The leaf array is a* set of indices into the nodes that indicate which node is the* parent of a symbol. For example, to encode 'A', we would find the* leaf node by way of leaf[ 'A' ]. The next_free_node index is used* to tell which node is the next one in the array that can be used.* Since nodes are allocated when characters are read in for the first* time, this pointer keeps track of where we are in the node array.* Finally, the array of nodes is the actual Huffman tree. The child* index is either an index pointing to a pair of children, or an* actual symbol value, depending on whether 'child_is_leaf' is true* or false.*/typedef struct tree { int leaf[ SYMBOL_COUNT ]; int next_free_node; struct node { unsigned int weight; int parent; int child_is_leaf; int child; } nodes [ NODE_TABLE_COUNT ];} TREE;/** The Tree used in this program is a global structure. Under other* circumstances it could just as well be a dynamically allocated* structure built when needed, since all routines here take a TREE* pointer as an argument.*/TREE Tree;/** Function prototypes for both ANSI C compilers and their K&R breth-* ren.*/#ifdef __STDC__void CompressFile( FILE *input, BIT_FILE *output, int argc, char *argv[] );void ExpandFile( BIT_FILE *input, FILE *output, int argc, char *argv[] );void InitializeTree( TREE *tree );void EncodeSymbol( TREE *tree, unsigned int c, BIT_FILE *output );int DecodeSymbol( TREE *tree, BIT_FILE *input );void UpdateModel( TREE *tree, int c );void RebuildTree( TREE *tree );void swap_nodes( TREE *tree, int i, int j );void add_new_node( TREE *tree, int c );void PrintTree( TREE *tree );void print_codes( TREE *tree );void print_code( TREE *tree, int c );void calculate_rows( TREE *tree, int node, int level );int calculate_columns( TREE *tree, int node, int starting_guess );int find_minimum_column( TREE *tree, int node, int max_row );void rescale_columns( int factor );#elsevoid CompressFile();void ExpandFile();void InitializeTree();void EncodeSymbol();int DecodeSymbol();void UpdateModel();void RebuildTree();void swap_nodes();void add_new_node();#endif/** The high level view of the compression routine is very simple.* First, we initialize the Huffman tree, with just the ESCAPE and* END_OF_STREAM symbols. Then, we sit in a loop, encoding symbols,* and adding them to the model. When there are no more characters* to send, the special END_OF_STREAM symbol is encoded. The decoder* will later be able to use this symbol to know when to quit.*/void CompressFile( input, output, argc, argv )FILE *input;BIT_FILE *output;int argc;char *argv[];{ int c; InitializeTree( &Tree ); while ( ( c = getc( input ) ) != EOF ) { EncodeSymbol( &Tree, c, output ); UpdateModel( &Tree, c ); } EncodeSymbol( &Tree, END_OF_STREAM, output ); while ( argc— > 0 ) { printf( "Unused argument: %s\n", *argv ); argv++; }}/** The Expansion routine looks very much like the compression routine.* It first initializes the Huffman tree, using the same routine as* the compressor did. It then sits in a loop, decoding characters and* updating the model until it reads in an END_OF_STREAM symbol. At* that point, it is time to quit.*/void ExpandFile( input, output, argc, argv )BIT_FILE *input;FILE *output;int argc;char *argv[];{ int c; while ( argc–– > 0 ) printf( "Unused argument: %s\n", *argv++ ); InitializeTree( &Tree ); while ( ( c = DecodeSymbol( &Tree, input ) ) != END OF STREAM ) { if ( putc( c, output ) == EOF ) fatal_error( "Error writing character" ); UpdateModel( & Tree, c ); }}/** When performing adaptive compression, the Huffman tree starts out* very nearly empty. The only two symbols present initially are the* ESCAPE symbol and the END_OF_STREAM symbol. The ESCAPE symbol has to* be included so we can tell the expansion program that we are* transmitting a previously unseen symbol. The END_OF_STREAM symbol* is here because it is greater than eight bits, and our ESCAPE* sequence only allows for eight bit symbols following the ESCAPE* code.** In addition to setting up the root node and its two children, this* routine also initializes the leaf array. The ESCAPE and* END_OF_STREAM leaves are the only ones initially defined, the rest* of the leaf elements are set to -1 to show that they aren't present* in the Huffman tree yet.*/void InitializeTree( tree )TREE *tree;{ int i; tree->nodes[ ROOT_NODE ].child = ROOT_NODE + 1; tree->nodes[ ROOT_NODE ].child_is_leaf = FALSE; tree->nodes[ ROOT_NODE ].weight = 2; tree->nodes[ ROOT_NODE ].parent = -1; tree->nodes[ ROOT_NODE + 1 ].child = END_OF_STREAM; tree->nodes[ ROOT_NODE + 1 ].child_is_leaf = TRUE; tree->nodes[ ROOT_NODE + 1 ].weight = 1; tree->nodes[ ROOT_NODE + 1 ].parent = ROOT_NODE; tree->leaf[ END_OF_STREAM ] = ROOT_NODE + 1; tree->nodes[ ROOT_NODE + 2 ].child = ESCAPE; tree->nodes[ ROOT_NODE + 2 ].child_is_leaf = TRUE; tree->nodes[ ROOT_NODE + 2 ].weight = 1; tree->nodes[ ROOT_NODE + 2 ].parent = ROOT_NODE; tree->leaf[ ESCAPE ] = ROOT_NODE + 2; tree->next_free_node = ROOT_NODE + 3; for ( i = 0 ; i < END_OF_STREAM ; i++ ) tree->leaf[ i ] = -1; }/** This routine is responsible for taking a symbol, and converting⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -