Method and apparatus for lossless compression and decompression of data

• US 20050193022A1
• Filed: 03/21/2003
• Published: 09/01/2005
• Est. Priority Date: 03/22/2002
• Status: Abandoned Application

• Current Assignee: Sia Datoru Drosibas Tehnologijas
• Original Assignee: Sia Datoru Drosibas Tehnologijas
• Inventors: Rigerts, Aldis, Shkesters, Valdis
• Application Number:
  US10/508,770
• Publication Number:
  US 20050193022A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• 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
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

The present invention relates to universal lossless data compression and decompression methods, as well as to apparatus for their implementation. The method is based on predicting the characters of data stream being processed by comparing them with predictors in one or several predictor tables and counting consecutively predicted characters, thus reducing considerably the number of output operations. Addressing in predictor tables is performed by means of one or several hash strings, each of which being formed by means of an unique hash function correlative with the input data. Processing the data stream in such a way allows eliminating the compression rate limitation that depends on the taken character length, thus increasing the compression rate and, at the same time, decreasing data processing time sufficiently.

Claims

1. A method for coding an input data character stream to obtain a compressed output code stream, said method comprising the steps of:

counting consecutively predicted characters by comparing a character of the input data character stream with a predictor stored in a predictor table and addressed by a hash string, said predictor table comprising a plurality of predictors, said predictors being the characters of the input data stream and/or predetermined values, and said hash strings being formed by means of a hash function correlative with the input data;

coding a number of the consecutively predicted characters and an unpredicted character immediately succeeding the consecutively predicted characters;

optional updating the predictor table by storing the unpredicted character into a cell of the predictor table, said cell being addressed by said hash string;

updating the hash string.

2. The method according to claim 1, wherein the coding step further comprises the steps of:

comparing said unpredicted character with a predictor stored in the next predictor table;

coding the number of the consecutively predicted characters and an identifier of said next predictor table, if said unpredicted character matches the predictor stored in said next predictor table;

or

coding the number of the consecutively predicted characters and the unpredicted character immediately succeeding the consecutively predicted characters, if said unpredicted character does not match the predictor stored in said next predictor table.

3. The method according to claim 2, wherein, in case said unpredicted character does not match said predictor stored in said next predictor table, the steps are performed in a recursive way, until all the existing predictor tables are used.

4. The method according to claim 3, wherein two or more hash strings are used for addressing the predictors in various predictor tables, each hash string being formed by means of an unique function correlative with the input data.

5. The method according to claim 3, further including an optional step of updating the predictor tables in accordance with a predetermined strategy.

6. The method according to claim 3, wherein the character of input data stream is compared in parallel with the predictors stored in two or more existing predictor tables.

7. The method according to claim 1, further comprising the step of initiating said hash string at the beginning of the process, in which a predetermined value is assigned to said hash string.

8. A method of decompression for obtaining an initial input data character stream from the compressed code stream obtained by the compression method according to claim 1, the decompression method comprising the steps of:

decoding a number of consecutively predicted characters and an unpredicted character immediately succeeding the consecutively predicted characters;

outputting the predicted characters by retrieving a predictor stored in a predictor table and addressed by a hash string, the retrieving being continued until the initial value assigned to the counter in the compression process is reached;

outputting the unpredicted character;

optionally updating the predictor table by storing the unpredicted character into a cell of the predictor table, the cell being addressed by the hash string; and

updating the hash string.

9. Apparatus for coding an input data character stream in order to obtain a compressed output code stream, the apparatus comprising:

a predictor table comprising a plurality of predictors, said predictors being the characters of the input data stream and/or predetermined values;

counting means arranged to count, in use, consecutively predicted characters by comparing a character of the input data character stream with a predictor stored in a predictor table and addressed by a hash string, wherein the hash string is formed by means of a hash function correlative with the input data;

first coding means arranged to code, in use, a number of consecutively predicted characters and an unpredicted character immediately succeeding the consecutively predicted characters;

predictor table updating means arranged, in use, to optionally update the predictor table by storing an unpredicted character into a cell of the predictor table, said cell being addressed by said hash string; and

updating means arranged, in use, to update the hash string after the predictor table has been updated.

10. The apparatus according to claim 9, wherein the first coding means further comprises:

comparing means arranged to compare, in use, said unpredicted character with a predictor stored in the next predictor table;

second coding means for coding, in use, a number of the consecutively predicted characters and an identifier of said next predictor table, if said unpredicted character matches the predictor stored in said next predictor table or coding the number of the consecutively predicted characters and the unpredicted character immediately succeeding the consecutively predicted characters, if said unpredicted character does not match the predictor stored in said next predictor table.

11. The apparatus according to claim 10, wherein the apparatus is arranged such that, in the case said unpredicted character does not match said predictor stored in said next predictor table, the comparing means and second coding means are arranged to function, in use, means in a recursive way, until all existing predictor tables are used.

12. The apparatus according to claim 11, wherein the apparatus is arranged such that two or more hash strings can be used for addressing the predictors in various predictor tables, each hash string being formed by means of an unique hash function correlative with the input data.

13. The apparatus according to claim 11, optionally comprising means for updating the predictor tables in accordance with a predetermined strategy.

14. The apparatus according to claim 11, further comprising means for parallel comparing the character of input data stream with the predictors stored in two or more existing predictor tables.

15. The apparatus according to claim 9, further comprising means adapted for initiating said hash string at the beginning of the process by assigning a predetermined value to said string.

16. A decompression apparatus for obtaining an initial input data character stream from a compressed code stream obtained with the compression apparatus according to claim 9, the apparatus comprising:

decoding means arranged to decode, in use, a number of consecutively predicted characters and an unpredicted character immediately succeeding the consecutively predicted characters;

a predictor table comprising a plurality of predictors, said predictors being the characters of the input data stream and/or predetermined values;

retrieval means arranged to retrieve, in use, a predictor stored in the predictor table and addressed by a hash string, wherein the retrieving is continued, in use, until the initial value assigned to the counting means in the compression apparatus is reached;

output means arranged to output, in use, predicted characters retrieved by the retrieval means and an unpredicted character;

predictor table updating means arranged, in use, to optionally update the predictor table by storing an unpredicted character into a cell of a predictor table, the cell being addressed by the hash string;

hash string updating means arranged, in use, to update the hash string after the predictor table has been updated.