Textual substitution data compression with finite length search windows

• US 4,906,991 A
• Filed: 04/29/1988
• Issued: 03/06/1990
• Est. Priority Date: 04/29/1988
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Greene, Daniel H., Fiala, Edward R.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): Young, Brian
• Application Number:
  US07/187,793
• Time in Patent Office: 676 Days
• Field of Search: 341/51, 341/64, 341/65, 341/67, 341/87, 341/90, 341/95, 341/107, 364/200, 364/260.6, 364/513.5, 364/148, 370/83, 370/79, 370/84
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

In accordance with the present invention source data is encoded by literal codewords of varying length value, with or without the encoding of copy codewords of varying length and displacement value. Copy codeword encoding is central to textual substitution-style data compression, but the encoding of variable length literals may be employed for other types of data compression.

Claims

1. In a textual substitution data compressor, the improvement comprising

a finite, substantially fixed length search window for storing recently compressed data symbols;

a search tree data structure having a predetermined cut-off depth for linking said recently compressed symbols to each other in accordance with the order of their occurrence and for tracking said recently compressed symbols as they advance across said search window, the cut-off depth of said search tree being selected based on a maximum permissible copy length;

means for inserting uncompressed symbols into said search tree for identifying prior occurrences of reoccurring symbol strings and for determining the string length and position within said search window of the longest of said prior occurrences for each of said reoccurring symbol strings; and

means for providing copy codewords and literal codewords with a variable number of appended literal symbols for encoding said uncompressed symbols depending on whether said uncompressed symbols define or fail to define, respectively, reoccurring symbol strings of minimum length;

each of said copy codewords identifying the length and the search window position of the prior occurrence of the reoccurring symbol string it represents; and

each of said literal codewords identifying the number of literal symbols that are appended to it.

2. The improvement of claim 1 wherein said copy codewords and said literal codewords have fixed lengths.

3. The improvement of claim 1 wherein the minimum reoccurring string length for encoding with a copy codeword is increased by one symbol while symbols are being accumulated for a literal codeword.

4. The improvement of claim 3 wherein the minimum reoccurring string length for encoding with a copy codeword is increased from two symbols to three symbols while symbols are being accumulated for a literal codeword.

5. The improvement of claim 1 wherein said copy codewords and said literal codewords have statistically sensitive, variable lengths.

6. The improvement of claim 1 wherein

said search tree has a root and nodes representing symbols within said search window, and

said uncompressed symbols are inserted into said tree by returning to its root to find a search path for the insertion of each symbol string.

7. The improvement of claim 6 wherein

said nodes include position fields for identifying the search window position of the symbols they represent, and

the position fields of the nodes on the search path for each symbol string inserted into said tree are updated to refer to the most recent occurrence of the symbols they represent as said symbol string is being inserted into said tree.