📄 273-278.html
字号:
<!DOCTYPE HTML PUBLIC "html.dtd"><HTML><HEAD><TITLE>The Data Compression Book-:LZ78 Compression</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=9//--><!-- PAGES=273-278//--><!-- UNASSIGNED1//--><!-- UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="271-273.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="279-287.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><H3><A NAME="Heading13"></A><FONT COLOR="#000077">The Code</FONT></H3><P>The source code for a complete twelve-bit version of LZW compression and decompression follows.</P><!-- CODE //--><PRE>/************************* Start of LZW12.C **************************** This is 12 bit LZW program, which is discussed in the first part* of the chapter. It uses a fixed size code, and does not attempt* to flush the dictionary after it fills up.*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include "errand.h"#include "bitio.h"/** Constants used throughout the program. BITS defines how many bits* will be in a code. TABLE_SIZE defines the size of the dictionary* table.*/#define BITS 12#define MAX_CODE ( ( 1 << BITS ) - 1 )#define TABLE_SIZE 5021#define END_OF_STREAM 256#define FIRST_CODE 257#define UNUSED -1/** Local prototypes.*/#ifdef __STDC__unsigned int find_child_node( int parent_code, int child_character );unsigned int decode_string( unsigned int offset, unsigned int code );#elseunsigned int find_child_node ();unsigned int decode_string ();#endifchar *CompressionName = "LZW 12 Bit Encoder";char *Usage = "in-file out-file\n\n";/** This data structure defines the dictionary. Each entry in the* dictionary has a code value. This is the code emitted by the* compressor. Each code is actually made up of two piece: a* parent_code, and a character. Code values of less than 256 are* actually plain text codes.*/struct dictionary { int code_value; int parent_code; char character;} dict[TABLE_SIZE ];char decode_stack[ TABLE_SIZE };/** The compressor is short and simple. It reads in new symbols one* at a time from the input file. It then checks to see if the* combination of the current symbol and the current code are already* defined in the dictionary. If they are not, they are added to the* dictionary, and we start over with a new one symbol code. If they* are, the code for the combination of the code and character becomes* our new code.*/void CompressFile( input, output, argc, argv )FILE *input;BIT_FILE *output;int argc;char *argv[];{ int next_code; int character; int string_code; unsigned int index; unsigned int i; next_code = FIRST_CODE; for ( i = 0 ; i < TABLE_SIZE ; i++ ) dict[ i ].code_value = UNUSED; if ( ( string_code = getc( input ) )== EOF ) string_code = END_OF_STREAM; while ( ( character = getc( input ) ) != EOF ) { index = find_child_node( string_code, character ); if ( dict[ index ].code_value != - 1) string_code = dict[ index ].code_value; else { if ( next_code <= MAX_CODE ) { dict[ index ].code_value = next_code++; dict[ index ].parent_code = string_code; dict[ index ].character = (char) character; } OutputBits( output, (unsigned long) string_code, BITS ); string_code = character; } } OutputBits( output, (unsigned long) string_code, BITS ); OutputBits( output, (unsigned long) END_OF_STREAM, BITS ); while ( argc-- > 0 ) printf( "Unknown argument: %s\n", *argv++ ); }/** The file expander operates much like the encoder. It has to* read in codes, then convert the codes to a string of characters.* The only catch in the whole operation occurs when the encoder* encounters a CHAR+STRING+CHAR+STRING+CHAR sequence. When this* occurs, the encoder outputs a code that is not presently defined* in the table. This is handled as an exception.*/void ExpandFile( input, output, argc, argv )BIT_FILE *input;FILE *output;int argc;char *argv[];{ unsigned int next_code; unsigned int new_code; unsigned int old_code; int character; unsigned int count; next_code = FIRST_CODE; old_code = (unsigned int) InputBits( input, BITS ); if ( old_code == END_OF_STREAM ) return; character = old_code; putc( old_code, output );while ( ( new_code = (unsigned int) InputBits( input, BITS ) ) != END_OF_STREAM ) {/*** This code checks for the CHARACTER+STRING+CHARACTER+STRING+CHARACTER** case which generates an undefined code. It handles it by decoding** the last code, and adding a single character to the end of the** decode string.*/ if (new_code >= next_code ) { decode_stack[ 0 ] = (char) character; count = decode_string( 1, old_code ); } else count = decode_string( 0, new_code ); character = decode_string[ count - 1 ]; while ( count > 0 ) putc( decode_stack[ --count ], output ); if ( next_code <= MAX_CODE ) { dict[ next_code ].parent_code = old_code; dict[ next_code ].character = (char) character; next_code++; } old_code = new_code; } while ( argc-- > 0 ) print( "Unknown argument: %s\n", *argv++ );}/** This hashing routine is responsible for finding the table location* for a string/character combination. The table index is created* by using an exclusive OR combination of the prefix and character.* This code also has to check for collisions, and handles them by* jumping around in the table.*/unsigned int find_child_node( parent_code, child_character )int parent_code;int child_character;{ int index; int offset; index = ( child_character << ( BITS - 8 ) ) ^ parent_code; if ( index == 0 ) offset = 1; else offset = TABLE_SIZE - index; for ( ; ; ) { if ( dict[ index ].code_value == UNUSED ) return( index ); if ( dict[ index ].parent_code == parent_code && dict[ index ].character == (char) child_character ) return( index ); index -= offset; if ( index < 0 ) index += TABLE_SIZE; }}/** This routine decodes a string from the dictionary, and stores it* in the decode_stack data structure. It returns a count to the* calling program of how many characters were placed in the stack.*/unsigned int decode_string( count, code )unsigned int count;unsigned int code;{ while ( code > 255 ) { decode_stack[ count++ ] = dict[ code ].character; code = dict[ code ].parent_code; } decode_stack[ count++ ] = (char) code; return( count );}/*************************** End of LZW12.C ****************************/</PRE><!-- END CODE //--><P><BR></P><CENTER><TABLE BORDER><TR><TD><A HREF="271-273.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="279-287.html">Next</A></TD></TR></TABLE></CENTER></TD></TR></TABLE></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -