Short-record data compression and decompression system
First Claim
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, anddecoder 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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
6 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
Specification