Method and apparatus for compressing and decompressing short blocks of data

• US 5,488,365 A
• Filed: 03/01/1994
• Issued: 01/30/1996
• Est. Priority Date: 03/01/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Lempel, Abraham, Seroussi, Gadiel
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/204,712
• Time in Patent Office: 700 Days
• Field of Search: 341/50, 341/51, 341/106
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A scheme for compression of large sets of short blocks of data for storage in a storage medium, such as a read-only memory. Applications of the scheme include compression of fonts for printers, ROM disks in portable PCs, and others. These applications require random access to individual blocks, and fast, real-time decompression. The scheme applies an asymmetrical three-stage methodology in which a first stage provides training and optimization for a set of data blocks; a second stage effects data compression; and a third stage effects data decompression.

Claims

1. A method for coding a data set made up of several short blocks of data, comprising the steps of:

inputting said data set;

partitioning said data set such that each data block is assigned to a specific cluster of data blocks;

generating a set of encoding tables for each cluster that specify a translation of said data blocks into binary codes, said table generating step further comprising the steps of;

grouping said data blocks according to a selected common characteristic to produce a number of data clusters; and

assigning said data blocks to said data clusters such that the sum;

space="preserve" listing-type="equation">S=S.sub.T +S.sub.E

is minimized, where S_T denotes the size of the encoding tables that are stored together with the encoded data blocks, S_E denotes the size of the encoded data blocks, and S denotes the total size of the compressed data set;

encoding said data blocks by applying the translation contained in said encoding tables to said data blocks;

generating an index table that references each data block to a corresponding encoding table;

translating said encoding table into a decoding table;

producing a compressed file including said index table, said decoding tables, and said encoded data blocks; and

storing said file on a storage medium.

2. The method of claim 1, further comprising the step of:

locating a data block and a corresponding decoding table in said index;

randomly and independently decompressing said data blocks by applying the translation contained in said decoding table to said data block; and

outputting said uncompressed data block.

3. The method of claim 1, said partitioning step further comprising the step of:

independently parsing each data block to generate a sequence of events based upon the largest possible string match in each data block.

4. The method of claim 3, said parsing step applying a Lempel-Ziv methodology.

5. The method of claim 3, said parsing step further comprising the step of:

Huffman encoding said events to assign shorter codes to more frequently occurring events and longer codes to less frequently occurring events.

6. The method of claim 1, said table generating step further comprising the steps of:

sorting said data blocks by a compressibility index obtained by compressing each block; and

clustering blocks having similar compressibility indices.

7. The method of claim 1, said data set further comprising a plurality of glyphs;

said table generating step further comprising the step of;

clustering said glyphs having known morphological similarities within said data set.

8. The method of claim 1, said table generating step further comprising the steps of:

dividing said data blocks into subsets; and

optimizing the number of subsets thus obtained.

9. The method of claim 1, wherein the file produced by said file producing step comprises:

a compressed file structure having an index table containing one index record for each compressed data block, said index record containing any of the following;

an address of a decoding table associated with a cluster containing a data block;

an address of the beginning of a compressed data block; and

a length of a compressed data block.

10. The method of claim 1 further comprising the step of:

decoding a data set made of several short blocks of data, said decoding step comprising the steps of;

locating an encoded data block and a corresponding decoding table in an index;

randomly and independently decoding said data blocks by applying a translation contained in a decoding table to said data block; and

outputting said decoded data block.

11. An apparatus for coding a data set made up of several short blocks of data, comprising:

an input for receiving said data set;

means for partitioning said data set such that each data block is assigned to a specific cluster of data blocks;

means for generating a set of encoding tables for each cluster that specify a translation of said data blocks into binary codes;

means for encoding said data blocks by applying the translation contained in said encoding tables to said data blocks;

means for generating an index table that references each data block to a corresponding encoding table, said table generating means further comprising;

means for grouping said data blocks according to a selected common characteristic to produce a number of data clusters; and

means for assigning said data blocks to said data clusters such that the sum;

space="preserve" listing-type="equation">S=S.sub.T +S.sub.E

is minimized, where S_T denotes the size of the encoding tables that are stored together with the encoded data blocks, S_E denotes the size of the encoded data blocks, and S denotes the total size of the compressed data set;

means for generating a set of decoding tables from said encoding tables;

means for producing a compressed file including said index table, said decoding tables, and said encoded data blocks; and

means for storing said file on a storage medium.

12. The apparatus of claim 11, further comprising:

means for locating a data block and a corresponding decoding table in said index;

means for randomly and independently decoding said data blocks by applying the translation contained in said decoding table to said data block; and

means for outputting said decoded data block.

13. The apparatus of claim 11, said partitioning means further comprising:

means for independently parsing each data block to generate a sequence of events based upon the largest possible string match in each data block.

14. The apparatus of claim 13, said parsing means applying a Lempel-Ziv methodology.

15. The apparatus of claim 13, said parsing means further comprising:

a Huffman encoder for encoding said events to assign shorter codes to more frequently occurring events and longer codes to less frequently occurring events.

16. The apparatus of claim 11, said table generating means further comprising:

means for sorting said data blocks by a compressibility index obtained by compressing each data block; and

means for clustering data blocks having similar compressibility indices.

17. The apparatus for claim 11, said data set further comprising:

a plurality of glyphs;

said table generating means further comprising;

means for clustering glyphs having known morphological similarities within said data set.

18. The apparatus of claim 11, said table generating means further comprising:

means for dividing said data blocks into subsets; and

means for optimizing the number of subsets thus obtained.

19. The apparatus of claim 11, wherein the file produced by said file producing means comprises:

a compressed file structure having an index table containing one index record for each compressed data block, said index record containing any of the following;

an address of a decoding table associated with a cluster containing a data block;

an address of the beginning of a compressed data block; and

a length of a compressed data block.

20. The apparatus of claim 11, further comprising:

means for decoding a data set made of several short blocks of data, said decoding means comprising;

means for locating an encoded data block and a corresponding decoding table in an index;

means for randomly and independently decoding said data blocks by applying a translation contained in a decoding table to said data block; and

means for outputting said decoded data block.