Short-record data compression and decompression system

• US 5,087,913 A
• Filed: 08/27/1990
• Issued: 02/11/1992
• Est. Priority Date: 08/27/1990
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Eastman, Willard L.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): Hoff, Marc S.
• Application Number:
  US07/572,647
• Time in Patent Office: 533 Days
• Field of Search: 341/65, 341/67, 341/79, 341/95, 341/51
• US Class Current: 341/95
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Short-data records are compressed and decompressed by Lempel-Ziv compression and decompression utilizing a fixed searchtree database, an encoder and a decoder. The searchtree database is incrementally grown by a file preprocessor from a sample of the input data. The searchtree is fixed either when the data sample or the storage space for the searchtree is exhausted. The encoder maintains an encoded-record directory for locating the compressed records. A record located by the directory is decompressed by the decoder, and may be modified and recompressed by the encoder. Lempel-Ziv compresssion and decompression of the type of U.S. Pat. No. 4,464,650 is utilized. The preprocessor also constructs, as part of the searchtree database, a last-descendant list for use by the decoder to extend internal nodes received as leaf pointers by the appropriate number of repetitions of the first encountered symbol of the alphabet.

Claims

1. Apparatus for compressing and decompressing short data records, said records being comprised of data over a predetermined alphabet, said apparatus comprising:

preprocessor means responsive to a sample of said data over said predetermined alphabet for constructing a searchtree database therefrom using Lempel-Ziv data compression, said searchtree database being incrementally grown until a predetermined limit is attained and thereafter maintained fixed, thereby constructing a fixed searchtree database,

storage means for storing said fixed searchtree database,

encoder means responsive to said fixed searchtree database in said storage means and to said short data records for compressing said short data records in accordance with said fixed searchtree database using said Lempel-Ziv data compression, thereby generating encoded records, said encoded records being stored in said storage means at locations thereof,

encoded-record directory means responsive to said encoder means for generating a directory of said encoded records in accordance with said locations, said directory means being stored in said storage means, and

decoder means responsive to said fixed searchtree database, said encoded records and said directory for decompressing, in accordance with said fixed Searchtree Database using Lempel-Ziv data decompression, an encoded record located by means of said directory, thereby generating a decompressed short-record.

2. The apparatus of claim 1 wherein said predetermined limit comprises exhaustion of said sample of said data.

3. The apparatus of claim 1 wherein said predetermined limit comprises exhaustion of said storage means for said fixed searchtree database.

4. The apparatus of claim 1 further including record modifier means responsive to said decompressed short-record for providing a modified short-record, said modified short-record being applied to said encoder means for recompression and storage back into said storage means.

5. The apparatus of claim 1 wherein said alphabet is comprised of a predetermined number of symbols, said Lempel-Ziv data compression and decompression utilized by said preprocessor means, said encoder means and said decoder means utilizes a count of the number of said symbols of said alphabet not yet encountered,

said preprocessor means including means for maintaining said count fixed at the number of said symbols not yet encountered when said predetermined limit is attained, thereby providing a fixed new symbol count, said fixed new symbol count being provided as part of said fixed searchtree database.

6. The apparatus of claim 5 wherein said searchtree database represents a searchtree having a plurality of nodes, said searchtree database further including

a last-descendant list utilized by said decoder means, said last-descendant list containing locations for said nodes, respectively, each said location containing the number of repetitions of the first symbol of said alphabet encountered by said preprocessor means to append to a string of symbols decoded by said decoder means.