Method of encoding compressed data

• US 5,001,478 A
• Filed: 12/28/1989
• Issued: 03/19/1991
• Est. Priority Date: 12/28/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nagy, Michael E.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): Hoff, Marc S.
• Application Number:
  US07/458,118
• Time in Patent Office: 446 Days
• Field of Search: 341/51, 341/65, 341/67, 341/106, 341/107
• US Class Current: 341/67
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A method of encoding compressed data for transmission or storage. The method includes converting the input data stream into a sequence of literal references, history references, and lexicon references. Each literal reference includes a literal identifier. Each history reference includes a history identifier. Each lexicon reference includes a lexicon identifier. The history references and lexicon references specify the location of strings of symbols in a history buffer and lexicon, respectively. The encoding method of the present invention encodes the location information in an optimal manner.

Claims

1. A method of encoding a compressed data stream made up of a sequence of literal references, lexicon references and history references, which comprises the steps of:

assigning to each literal reference a literal identifier;

assigning to each history reference a history identifier;

assigning to each lexicon reference a lexicon identifier; and

emitting a data stream with said identifiers assigned to said references.

2. The method as claimed in claim 1, wherein said literal identifier consists of a zero bit.

3. The method as claimed in claim 2, wherein said history identifier consists of a one bit followed by a zero bit, and said lexicon reference consists of a one bit followed by a one bit.

4. A method of encoding a data stream made up of a sequence of symbols, which comprises the steps of:

recording in a history buffer symbols of said sequence;

emitting a history reference, which includes a history identifier, an offset value and a length value, whenever a string of symbols from said sequence is duplicated in said history buffer;

recording in a lexicon strings of symbols that have been emitted by means of history references;

emitting a lexicon reference, which includes a lexicon identifier and an index value, whenever a string of symbols from said sequence is duplicated in said lexicon; and

emitting a literal reference whenever a symbol is not duplicated in either said history buffer or said lexicon, said literal reference including a literal identifier and said symbol.

5. The method as claimed in claim 4, including the step of noting the current maximum offset into said history buffer.

6. The method as claimed in claim 5, wherein the offset portion of said history reference has a length equal to the base two logarithm, rounded up to the nearest integer value, of said current maximum offset into said history buffer

7. The method as claimed in claim 4, including the step of noting the current number of entries in said lexicon.

8. The method as claimed in claim 7, wherein the length of said lexicon reference is equal to the base two logarithm, rounded up to the nearest integer value, of said current number of lexicon entries.

9. The method as claimed in claim 4, including the step of emitting a reference identifier when said data stream is exhausted.

10. The method as claimed in claim 9, wherein said reference identifier is a literal identifier.