📄 235-238.html

📁 The primary purpose of this book is to explain various data-compression techniques using the C progr
💻 HTML
字号:
<!DOCTYPE HTML PUBLIC "html.dtd"><HTML><HEAD><TITLE>The Data Compression Book-:Sliding Window 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=8//--><!-- PAGES=235-238//--><!-- UNASSIGNED1//--><!-- UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="232-235.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="238-242.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><H4 ALIGN="LEFT"><A NAME="Heading16"></A><FONT COLOR="#000077">AddString()</FONT></H4><P>The bulk of the work done by the compression routine takes place in AddString(). This routine does two jobs. First, it adds a new string to the binary tree. Second, it tracks the string currently in the tree that best matches the one being inserted.</P><P>The process of locating the node for inspection of the new string uses standard techniques for traversing a binary tree. AddString first checks to see if the new string is the END_OF_STREAM node. If it is, it shouldn&#146;t be inserted into the tree, so it takes immediate return with a match_length of zero. This forces the encoder to output a single character instead of trying to encode a phrase at index 0.</P><P>After checking for a bad node, the test_node and initial match_length are set up. Throughout the main loop, test_node will point to the current node that will be compared to the new_node. The match_length variable will contain the current longest match found during traversal of the tree.</P><!--  CODE //--><PRE>int AddString( int new_node, int *match_position ){  int i;  int test_node;  int delta;  int match_length;  int *child;  if ( new_node == END_OF_STREAM )   return( 0 );  test_node = tree[ TREE_ROOT ].larger_child;  match_length = 0;  for ( ; ; ) {    for ( i = 0 ; i &lt; LOOK_AHEAD_SIZE ; i++ ) {     delta = window[ MOD_WINDOW( new_node + i ) ] -       window[ MOD_WINDOW( test_node + i ) ];     if ( delta != 0 )      break;  }  if ( i &gt;= match_length ){    match_length = i;    *match_position = test_node;       if ( match_length &gt;= LOOK_AHEAD_SIZE ) {         ReplaceNode( test_node, new_node );         return( match_length );       }    }    if ( delta &gt;= 0 )      child = &#38;tree[ test_node ].larger_child;    else      child = &#38;tree[ test_node ].smaller_child;    if ( *child == UNUSED ) {      *child = new_node;      tree[ new_node ].parent = test_node;      tree[ new_node ].larger_child = UNUSED;      tree[ new_node ].smaller_child = UNUSED;      return( match_length );    }    test_node = *child;  }}</PRE><!--  END CODE //--><P>At this point, the main comparison loop is entered. The first section executes a comparison of the test_node and the new_node. Two pieces of information are available after falling out of the loop. The first is the value of delta. The delta variable will be less than one if the string at new_node is less than the test_node, zero if they are the same, and one if the new_node is greater. The second, found in the loop variable i, tells how many characters in the two strings were identical, or the match_length for a particular string.</P><!--  CODE SNIP //--><PRE>for ( i = 0 ; i &lt; LOOK_AHEAD_SIZE ; i++ ) {  delta = window[ MOD_WINDOW( new_node + i ) ] -          window[ MOD_WINDOW( test_node + i ) ];  if ( delta != 0 )    break;}</PRE><!--  END CODE SNIP //--><P>After the comparison code completes, the main loop tests whether the match for this phrase is the longest one recorded so far. If it is, the match_length variable is updated, and the test_node position is saved.</P><!--  CODE SNIP //--><PRE>if ( i &gt;= match_length ) {  match_length = i;  *match_position = test_node;  if ( match_length &gt;= LOOK_AHEAD_SIZE ) {    ReplaceNode( test_node, new_node );    return( match_length );  }}</PRE><!--  END CODE SNIP //--><P>Frequently, the phrase in the look-ahead buffer is an exact match for the test_node. When this is the case, two things happen. First, since the longest match is found, the code will exit the AddString() routine. But before exiting, it performs a node replacement by deleting the test_node and replacing it with the new_node. It could just add new_node to the binary tree, but there is really no point to it, test_node will be redundant data taking up time in the search path if it just uses the normal insertion code. Instead, a special routine replaces test_node with new_node and returns. This leaves a sparser tree that can be searched more quickly. And, since test_node would have been deleted before new_node, it doesn&#146;t sacrifice any compression by doing this.</P><P>The final section of the main test loop is the tree navigation step. The delta variable tells whether to follow the larger_child or smaller_child branches from the test_node. If the child we are supposed to follow is UNUSED, we have gone as far as we can in the tree. At this point, the code inserts new_node into the binary tree at the correct child and returns. Otherwise, it moves to the new test_node and goes back to the start of the test loop.</P><!--  CODE //--><PRE>if ( delta &gt;= 0 )  child = &#38;tree[ test_node ].larger_child;else  child = &#38;tree[ test_node ].smaller_child;if ( *child == UNUSED ) {  *child = new_node;  tree[ new_node ].parent = test_node;  tree[ new_node ].larger_child = UNUSED;  tree[ new_node ].smaller_child = UNUSED;  return( match_length );}test_node = *child;</PRE><!--  END CODE //--><P><BR></P><CENTER><TABLE BORDER><TR><TD><A HREF="232-235.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="238-242.html">Next</A></TD></TR></TABLE></CENTER></TD></TR></TABLE></BODY></HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -