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

• US 5,412,384 A
• Filed: 08/10/1994
• Issued: 05/02/1995
• Est. Priority Date: 04/16/1993
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Plambeck, Kenneth E., Friske, Craig A., Iyer, Balakrishna R., Wilhite, David, El-Ruby, Mohamed H., Lazarus, John P., Davoll, Gregory L., Chang, Chung-Chia
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/288,675
• Time in Patent Office: 265 Days
• Field of Search: 341/51, 341/67, 341/79
• US Class Current: 341/79
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

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.

Claims

1. In a computer-implemented system for compressing input data consisting of sequences of source symbols selected from a source alphabet to form output data consisting of sequences of code symbols selected from a code alphabet according to a static dictionary stored in memory, said dictionary representing a static parse-tree having nodes representing said code symbols, said nodes being linked into paths representing said source symbol sequences, a method for creating said static dictionary comprising the steps of:

(a) repeatedly performing the steps of

(a.1) determining a source symbol sequence from said input data,

(a.2) adding at least one node to said parse-tree responsive to said source symbol sequence, and

(a.3) assigning a use count value to said at least one node responsive to the number of said source symbol sequence occurrences; and

(b) reducing said parse-tree to a first predetermined plurality of nodes by repeatedly deleting from said parse-tree one or more childless nodes having a use count value less than a predetermined use count value threshold.

2. The method of claim 1 wherein said reducing step (b) comprises the additional step of:

(b.1) combining with its parent node at least one childless node having a single-child parent node for which said use count differs by no more than one from said use count value for said at least one childless node, thereby forming a new childless node.

3. In a computer-implemented system for compressing input data arranged in a data stream of one or more records consisting of sequences of source symbols selected from a source alphabet to form output data consisting of sequences of code symbols selected from a code alphabet according to a static dictionary stored in a memory, said dictionary representing a static parse-tree having nodes representing said code symbols, said nodes being linked into paths representing said source symbol sequences, a method for creating said static dictionary comprising the steps of:

(a) initializing a parse-tree with a plurality of said paths representing a set of said source symbol strings, each said path having at least one node with a unity use count value;

.

(b) setting a current input pointer at the beginning of said data stream;

performing the steps of

(c.1) determining the longest said source symbol sequence S, represented by a path P in said parse-tree, that matches a current said source symbol sequence in said data stream beginning at said current input pointer,

(c.2) incrementing said use count value for all nodes in said path P,

(c.3) adding a new node N having a unity use count value to the end of said path P to form a new path P'"'"' representing a new source symbol sequence S'"'"' consisting of said string S extended by at least one immediately subsequent source symbol in said data stream, and

(c.4) advancing said current input pointer to immediately after said sequence S'"'"' in said data stream;

(s) if said parse-tree contains less than a first predetermined plurality of nodes, repeating said performing step (c);

(e) combining with its parent node one or more child nodes in said parse-tree, said child nodes each having a single-child parent node for which said use count value differs by no more than one from said use count value for each child node, thereby forming one or more new leaf nodes;

(f) assembling said nodes with the associated said paths to form said static dictionary; and

(g) storing said static dictionary in said memory.

4. The method of claim 3 further comprising the steps of:

(e.1) initializing a use count value threshold to unity;

(e.2) performing the steps of

(e.2.1) deleting each said childless node having a use count value less than or equal to said use count value threshold, and

(e.2.2) incrementing said use count value threshold; and

(e.3) if said parse-tree contains more than a second predetermined plurality of said nodes, repeating said performing step (e.2).

5. The method of claim 3 further comprising the steps of:

(e.1) creating a leaf chain by sequentially linking each childless node in said parse tree;

(e.2) combining with its parent node one or more child nodes in said leaf chain, said child nodes each having a single-child parent node for which said use count value differs by no more than one from said use count value for said each child node, thereby forming one or more new leaf nodes;

(e.3) adding said new leaf node to said leaf chain;

(e.4) repeating said combining step (e.2) and adding step (e.3) until no more said new nodes are formed;

(e.5) initializing a use count value threshold to unity;

(e.6) performing the steps of

(e.6.1) deleting each said leaf node having a use count value less than or equal to said use count value threshold, and

(e.6.2) incrementing said use count value threshold; and

(e.7) if said parse-tree contains more than a second predetermined plurality of said nodes, repeating said performing step (e.6).

6. In a computer-implemented system for compressing input data arranged in a data stream of one or more records consisting of sequences of source symbols selected from a source alphabet to form output data consisting of sequences of code symbols selected from a code alphabet according to a static dictionary stored in a memory, said dictionary representing a static parse-tree having nodes representing said code symbols, said nodes being Linked into paths representing said source symbol sequences, a method for creating said static dictionary comprising the steps of:

(a) initializing a parse-tree with a plurality of said paths representing a set of said source symbol strings, each said path having at least one node with a unity use count value;

(b) setting a current input pointer at the beginning of said data stream;

(c) until said data stream is exhausted, repeatedly performing the steps of;

(c.1) determining the longest said source symbol sequence S, represented by a path P in said parse-tree, that matches a current said source symbol sequence in said data stream beginning at said current input pointer,

(c.2) incrementing said use count value for all nodes in said path P,

(c.3) if said sequence S is not the final sequence in a record, adding a new node N having a unity use count value to said path P to form a new path P'"'"' representing a new source symbol sequence S'"'"' consisting of said sequence S extended by at least one immediately subsequent said source symbol in said data stream,

(c.4) linking said new node N to the end of a LRU chain,

(c.5) advancing said current input pointer to the end of said sequence S'"'"' in said data stream, and

(c.6) performing the steps of

(e.6.1) initializing a use count value threshold to a fourth predetermined value, and

(e.6.2) discarding from said LRU chain one said node whose use count value does not exceed said use count value threshold;

(d) assembling said nodes with the associated said paths to form said static dictionary; and

(e) storing said static dictionary in said memory.

7. The method in claim 6 wherein said data stream is organized as a series of database records.

8. The method of claim 7 wherein said database records are organized in accordance with definitions for a NULL string and one or more DEFAULT strings and wherein said initializing step (a) comprises the additional step of:

(a.1) initializing said parse-tree with a second plurality of nodes forming one or more said paths, each said path representing one of said NULL and DEFAULT source symbol string definitions.

9. The method of claim 9 wherein said linking step (c.4) comprises the steps of:

(c.4.1) creating a leaf chain by sequentially linking each childless node in said LRU chain; and

(c.4.2) combining with its parent node one or more child nodes in said leaf chain, said child nodes each having a single-child parent node for which said use count value differs by no more than one from said use count value for said each child node, thereby forming one or more new leaf nodes.

10. A computer-implemented system for compressing input data arranged in a data stream of one or more records consisting of sequences of source symbols selected from a source alphabet to form output data consisting of sequences of code symbols selected from a code alphabet according to a static dictionary stored in a memory, said dictionary representing a static parse-tree having nodes representing said code symbols, said nodes being linked into paths representing said source symbol sequences, said system comprising

primer means for initializing a parse-tree with a plurality of said paths representing a set of said source symbol strings, each said path having at least one node with a unity use count value;

pointer means for setting a current input pointer at the beginning of said data stream;

comparator means for determining the longest said source symbol sequence S, represented by a path P in said parse-tree, that matches a current said source symbol sequence in said data stream beginning at said current input pointer;

adder means for incrementing said use count value for all nodes in said path P;

extender means for adding a new node N having a unity use count value to the end of said path P to form a new path P'"'"' representing a new source symbol sequence S'"'"' consisting of said string S extended by at least one immediately subsequent source symbol in said data stream;

register means for advancing said current input pointer to immediately after said sequence S'"'"' in said data stream;

counter means for determining when the number of said nodes in said parse-tree exceeds a first predetermined plurality of nodes;

first linker means for sequentially linking each childless node in said parse tree to form a leaf node chain;

node combiner means for combining with its parent node a child node in said leaf node chain having a single-child parent node for which said use count value differs by no more than one from said use count value for said child node, thereby forming a new leaf node;

transformer means for assembling said nodes with the associated said paths to form said static dictionary; and

storage means for storing said static dictionary in said memory.

11. The computer implemented system of claim 10 further comprising:

node pruner means for deleting each said node in said leaf node chain having a use count value less than or equal to a predetermined use count value threshold.

12. The computer-implemented system of claim 10 further comprising:

linker means for adding said new node N to the end of a LRU chain; and

node recycler means for discarding from said LRU chain one said node whose use count value does not exceed a predetermined use count value threshold.