Coded data generation or conversion – Digital code to digital code converters – Tree structure
Patent
1994-08-10
1995-05-02
Hoff, Marc S.
Coded data generation or conversion
Digital code to digital code converters
Tree structure
341 51, H03M 738
Patent
active
054123844
ABSTRACT:
A system for creating a static data compression dictionary adapted to a hardware-based data compression architecture. A static Ziv-Lempel dictionary is created and stored in memory for use in compressing database records. No data compression occurs during dictionary construction. A fixed-size Ziv-Lempel parse-tree is adapted to database characteristics in one of two alternate ways. First, the parse-tree is overbuilt substantially and then pruned back to a static size by eliminating the least recently used (LRU) nodes having the lowest use count. Alternatively, the parse-tree is built to a static size and thereafter selected nodes are replaced with new nodes upon database sampling. This node recycling procedure chooses the least-useful nodes for replacement according to a use count and LRU strategy while exhausting the database sample. The pruned Ziv-Lempel parse-tree is then transformed to a static dictionary configuration and stored in memory for use in a hardware-based database compression procedure. Completion of the static dictionary before starting data compression eliminates the initial compression inefficiencies well-known for the Ziv-Lempel procedure. The parse-tree construction is enhanced by initializing the tree with NULL and DEFAULT sequences from database definitions before examining any data.
REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4814746 (1989-03-01), Miller et al.
patent: 5087913 (1992-02-01), Eastman
patent: 5150119 (1992-09-01), Yoshida et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5153591 (1992-10-01), Clark
Terry A. Welch, "A technique for High-Performance Data Compression", Computer, Jun. 1984, pp. 8-19.
Victor S. Miller, Mark N. Wegman, "Variations on a Theme by Ziv and Lempel", Research Report/Computer Science, Jul. 31, 1984, 11 pages.
Glen G. Langdon, Jr., "A note on the Ziv-Lempel Model for Compressing Individual Sequences", IEEE Transactions on Information Theory, vol. IT-29, No. 2, Mar. 1983, pp. 284-287.
Jacob Ziv, Abraham Lempel, "Compression of Individual Sequences via Variable-Rate Coding", IEEE Transactions on Information Theory, vol. IT-24, No. 5, Sep. 1978, pp. 530-536.
Kent Anderson, "Methods of Data Compression after the Manner of Lempel and Ziv", Optical Information Systems, Jan.-Feb. 1990, pp. 40-43.
Chang Chung-Chia
Davoll Gregory L.
El-Ruby Mohamed H.
Friske Craig A.
Iyer Balakrishna R.
Hoff Marc S.
International Business Machines - Corporation
LandOfFree
Method and system for adaptively building a static Ziv-Lempel di does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for adaptively building a static Ziv-Lempel di, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for adaptively building a static Ziv-Lempel di will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1140674