US5087913A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Short-record data compression and decompression system
Assignee: Unisys Corp
•
Filing: 1990-08-27
•
Granted: 1992-02-11
•
Expires: 2010-08-27
Abstract
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.
Inventors
- 👤 Willard L. Eastman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 11:48
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
198 words
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.
Claim 2
Dependent Claim
198 words
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.
Claim 3
Dependent Claim
17 words
The apparatus of claim 1 wherein said predetermined limit comprises exhaustion of said sample of said data.
Claim 4
Dependent Claim
20 words
The apparatus of claim 1 wherein said predetermined limit comprises exhaustion of said storage means for said fixed searchtree database.
Claim 5
Dependent Claim
38 words
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.
Claim 6
Dependent Claim
95 words
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.
Claim 7
Dependent Claim
71 words
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.
References Cited (Backward Citations)
US4464650A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4876541A
Cited
US4906991A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-02-10 | 1995-08-12 | 1996-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-02-10 | 1999-08-12 | 2000-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-02-10 | 2003-08-12 | 2004-02-11 | $7700.00 | Window Closed / Lapsed |