📄 238-242.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=238-242//--><!-- UNASSIGNED1//--><!-- UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="235-238.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="242-244.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><H4 ALIGN="LEFT"><A NAME="Heading17"></A><FONT COLOR="#000077">DeleteString()</FONT></H4><P>DeleteString() is called from the main compression loop every time a new character is read into the look-ahead buffer. It uses a standard binary tree deletion algorithm to delete a phrase from the text window.</P><P>DeleteString() first determines whether the node is really in the tree. It is possible for the AddString() routine to have already deleted a string because it was a duplicate. If this is the case, the work has been done, and the routine can return.</P><!-- CODE //--><PRE>void DeleteString( int p ){ int replacement; if ( tree[ p ].parent == UNUSED ) return; if ( tree[ p ].larger_child == UNUSED ) ContractNode( p. tree[ p ].smaller_child ); else if ( tree[ p ].smaller_child == UNUSED) ContractNode( p, tree[ p ].larger_child ); else { replacement = FindNextNode( p ); DeleteString( replacement ); ReplaceNode( p, replacement ); }}</PRE><!-- END CODE //--><P>If the string is presently in the tree, there are two possibilities for a deletion strategy. If either of the node’s children are unused, deleting the node is just a matter of closing the link between the current node’s parent and the child in use, effectively pulling the node out of the tree. This is done by a routine called ContractNode().</P><P><A NAME="Fig9"></A><A HREF="javascript:displayWindow('images/08-09.jpg',452,197)"><IMG SRC="images/08-09t.jpg"></A><BR><A HREF="javascript:displayWindow('images/08-09.jpg',452,197)"><FONT COLOR="#000077"><B>Figure 8.9</B></FONT></A> Tree before contraction of node p.</P><P><A NAME="Fig10"></A><A HREF="javascript:displayWindow('images/08-10.jpg',451,149)"><IMG SRC="images/08-10t.jpg"></A><BR><A HREF="javascript:displayWindow('images/08-10.jpg',451,149)"><FONT COLOR="#000077"><B>Figure 8.10</B></FONT></A> Tree after contraction of node p.</P><P>The situation is a little more complicated if the node to be deleted has children on both the larger_child and smaller_child nodes. When this is the case, the alternate deletion algorithm has to be used. The way to delete node p when both children are used to find the node in the tree either directly before or indirectly after node p in the ordered list of nodes. In this program, we find the next smaller node. This is done in the FindNextNode() routine and is accomplished by taking the first smaller_child branch, then following the larger_child branches until an UNUSED smaller_child is found. This next smaller node in the list is the replacement node.</P><P>The replacement node is then deleted from the tree, with a recursive call to DeleteString(). Out of control recursion is not a worry at this point, since the replacement node by definition has at least one UNUSED child. This means we will never go more than one level deep in our recursion.</P><P>After the replacement node has been deleted, it is used to replace the original deleted node. This is done by a routine called ReplaceNode() which simply inserts it in the tree in the same position as the original node.</P><H4 ALIGN="LEFT"><A NAME="Heading18"></A><FONT COLOR="#000077">Binary Tree Support Routines</FONT></H4><P>The support routines used by AddString() and DeleteString() are ContractNode(), ReplaceNode(), and FindNextNode(). ContractNode() deletes a node when one of the children is UNUSED. To do this, the used child is linked with the parent, effectively pulling the node out of the tree. The deleted node has its parent node set to UNUSED, which is what is used internally to determine if a node is in use.</P><!-- CODE //--><PRE>void ContractNode( int old_node, int new_node ){ tree[ new_node ].parent = tree[ old_node ].parent; if ( tree[ tree[ old_node ].parent ].larger_child == old_node ) tree[ tree[ old_node ].parent ].larger_child = new_node; else tree[ tree[ old_node ].parent ].smaller_child = new_node; tree[ old_node ].parent = UNUSED;}</PRE><!-- END CODE //--><P>ReplaceNode() is used during the deletion process when a new_node is going to be dropped into the tree on top of the old_node. It is assumed that the new_node is not currently linked to the tree. When the operation completes, the old_node will have been removed, and this is indicated by setting the parent to UNUSED.</P><!-- CODE //--><PRE>void ReplaceNode( int old_node, int new_node ){ int parent; parent = tree[ old_node ].parent; if ( tree[ parent ].smaller_child == old_node ) tree[ parent ].smaller_child = new_node; else tree[ parent ].larger_child = new_node; tree[ new_node ] = tree[ old_node ]; tree[ tree[ new_node ].smaller_child ].parent = new_node; tree[ tree[ new_node ].larger_child ].parent = new_node; tree[ old_node ].parent = UNUSED;}</PRE><!-- END CODE //--><P>FindNextNode() is called when the DeleteString() routine needs to find the next smaller node in the sorted list. It first takes the smaller branch from the starting node, then follows the larger branches until an UNUSED child is located. The node with the UNUSED larger_child is the next highest in the list. This routine assumes that the node has a next smallest node, meaning it has to have a smaller_child branch.</P><!-- CODE //--><PRE>int FindNextNode( int node ){ int next; next = tree[ node ].smaller_child; while ( tree[ next ].larger_child != UNUSED ) next = tree[ next ].larger_child; return( next );}</PRE><!-- END CODE //--><P><BR></P><CENTER><TABLE BORDER><TR><TD><A HREF="235-238.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="242-244.html">Next</A></TD></TR></TABLE></CENTER></TD></TR></TABLE></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -