Method and system for adaptively building a static Ziv-Lempel dictionary for database compression

US5534861A · kind A · utility

Assignee

• International Business Machines Corporation · US

Inventors

• Chung-Chia Chang · San Jose, US
• Gregory L. Davoll · Los Gatos, US
• Mohamed H. El-Ruby · San Jose, US
• Craig A. Friske · San Jose, US
• Balakrishna Raghavendra Iyer · Fremont, US
• John P. Lazarus · San Jose, US
• David G. Wilhite, Jr. · Santa Clara, US
• Kenneth E. Plambeck · Poughkeepsie, US

Key dates

• Filing date: Mar 8, 1995
• Grant date: Jul 9, 1996
• Expiry date: Mar 8, 2015

Classification

• Technology area (CPC G): Physics
• CPC primary: G06T9/005
• WIPO field: Basic communication processes
• WIPO sector: Electrical engineering

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 constru…