Method and apparatus for data compression and decompression

• US 5,703,581 A
• Filed: 06/14/1996
• Issued: 12/30/1997
• Est. Priority Date: 06/14/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Sahinalp, Suleyman Cenk, Matias, Yossi
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/665,188
• Time in Patent Office: 564 Days
• Field of Search: 341/67, 341/50, 341/51, 341/87, 364/514 R, 395/800, 395/602
• US Class Current: 341/67
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A data compression technique for encoding a data stream of symbols processes a current sequence of symbols in the stream using an adaptive look-up table containing strings of different lengths by identifying whether a match of a longest string from the table or a shorter string would produce a lower compression ratio by "looking ahead" and identifying a match between a next sequence in the data stream and strings in the table. The compression technique identifies those situations where it is advantageous to use a compressed code identifier for a current sequence that is shorter than the longest matching sequence. Such situations exist when the compression ratio achieved for compressing the current sequence in combination with the next sequence in the stream is greater when other than the longest match is employed for the first sequence. A corresponding decompression technique to decode data encoded using a similar "look ahead" technique is also disclosed.

Claims

1. A method for processing a stream of data symbols into a variable-length compressed code stream comprising:

first parsing said symbol stream and storing in a table strings of symbols encountered in said stream, said stored strings having respective codes associated therewith, each string of symbols containing more than one symbol including a prefix string of symbols and an extension symbol, said prefix string corresponding to a string stored in said table;

second parsing said symbol stream, said second parsing successively partitioning said symbol stream for identifying codes in the table associated with table strings that correspond to the successive partitioning;

said second parsing step determining said successive partitioning by determining the symbol sequence length of a current symbol sequence in the stream when sequences of at least two different lengths correspond to entries in the table for said current sequence based on determining last encountered symbol positions of corresponding next sequences in the stream that correspond to strings in the table and which start at next symbol positions in the stream after said sequences of at least two different lengths; and

providing the identified codes in said second parsing step for said compressed code stream.

2. The method of claim 1 wherein a first symbol location of said current sequence is parsed by said first parsing step prior to said second parsing step.

3. The method of claim 1 wherein said first and second parsings are performed substantially simultaneously.

4. The method of claim 3 wherein said first parsing is interleaved with said second parsing.

5. The method of claim 1 wherein said code is provided for the compressed code stream for said current sequence having a length based on a determination that a last symbol of a corresponding next sequence in the symbol stream is at a later encountered stream position than at least one last symbol of a next sequence corresponding to said current sequence having a different length.

6. The method of claim 5 wherein said code is provided for the compressed code stream for said current sequence having a length based on a determination that a last symbol of a corresponding next sequence in the symbol stream is at a relatively latest encountered stream position.

7. The method of claim 1 further comprising initializing said table to include a set of symbols from which the data stream was generated.

8. The method of claim 1 wherein said first parsing is performed according to the Lempil-Ziv-78 technique.

9. The method of claim 1 wherein said first parsing is performed according to the Lempil-Ziv-Welch technique.

10. A method for processing a stream of data symbols into a variable-length compressed code stream comprising:

first parsing said symbol stream and storing in a table strings of symbols encountered in said stream, said stored strings having respective codes associated therewith, each string of symbols containing more than one symbol including a prefix string of symbols and an extension symbol, said prefix string corresponding to a string stored in said table; and

second parsing said symbol stream, said second parsing encountering an i-th symbol of said stream after or simultaneously with said first parsing encountering a symbol after a j-th symbol of said stream, wherein i<

j, said second parsing comprising,

identifying a symbol sequence beginning with a k-th symbol between the i-th and the j-th symbol which corresponds to a previously stored string in the table and which extends to a relatively later encountered symbol in the stream than at least one other symbol sequence corresponding to a previously stored string in the table that starts from a symbol between the i-th to thej-th encountered symbol other than the k-th symbol,

identifying the code in the table corresponding to the symbol sequence from the i-th symbol to the symbol immediately prior to the identified k-th symbol, and

providing the identified code for part of said compressed code stream.

11. The method of claim 10 wherein the step of identifying a symbol sequence beginning with a k-th encountered symbol identifies the symbol sequence that extends to a relatively latest encountered symbol in the stream.

12. The method of claim 10 wherein said first and second parsings are performed substantially simultaneously.

13. The method of claim 12 wherein said first parsing is interleaved with said second parsing.

14. The method of claim 13 wherein said step of identifying a symbol sequence beginning with a k-th symbol encountered in the stream from the i-th to thej-th symbol is performed immediately after said j-th symbol is processed by said first parsing step.

15. The method of claim 10 wherein said first parsing is performed according to the Lempil-Ziv-78 technique.

16. The method of claim 10 further comprising initializing said table to include a set of symbols from which the data stream was generated.

17. A storage medium manufactured in accordance with a process comprising the steps of:

first parsing a stream of data symbol and storing in a table strings of symbols encountered in said stream, said stored strings having respective codes associated therewith, each said string of symbols including a prefix string of symbols and an extension symbol, said prefix string corresponding to a string stored in said table;

second parsing said symbol stream, said second parsing encountering an i-th symbol of said stream after or simultaneously with said first parsing encountering a symbol after a j-th symbol of said stream, wherein i<

j, said second parsing comprising,

identifying a symbol sequence beginning with a k-th symbol encountered in the stream from the i-th to thej-th symbol which corresponds to a previously stored string in the table and which extends to a relatively later encountered symbol in the stream than at least one other symbol sequence corresponding to a previously stored string in the table that starts from a symbol between the i-th to thej-th encountered symbol other than the k-th symbol,

identifying the code in the table corresponding to the symbol sequence from the i-th symbol to the symbol immediately prior to the identified k-th symbol, and

providing the identified code for part of a corresponding compressed code stream;

applying a recording signal to the storage medium, the recording signal representing said codes of said compressed code stream; and

recording the recording signal onto the storage medium.

18. The storage medium of claim 17 wherein said storage medium is a CD-ROM.

19. The storage medium of claim 17 wherein said storage medium is a magnetic floppy disk.

20. A method for recovering a stream of data symbols by processing a compressed code stream comprising:

sequentially processing codes encountered in said compressed code stream, said sequentially processing of each code comprising,

identifying whether a string entry is present in a table of strings for said code, said table having initial entries of strings of a set of symbols used to generate said stream of symbols, said stored strings having respective codes associated therewith,

if said entry is present in said table, a) retrieving the string entry from said table corresponding to said code, b) concatenating the retrieved string to said stream of symbols and c) storing a new string entry in said table with a respective code associated therewith, said new entry corresponding to a shortest sequence in said generated symbol stream not in said table, and

if said entry is not present in said table, a) concatenating said immediate previous retrieved string to the end of the stream of symbols at least once to produce an expanded stream of symbols, b) identifying a shortest symbol sequence in said generated expanded symbol stream not in said table, c) storing a new string entry in said table with a respective code associated therewith corresponding to said identified shortest symbol sequence, and d) amending said expanded stream of symbols so as to contain said symbol stream prior to expansion concatenated with said new string entered in said table.

21. The method of claim 20 further comprising initializing said table to include a set of symbols from which the data stream was generated.