Method and apparatus for compressing digital data

• US 6,011,871 A
• Filed: 10/09/1997
• Issued: 01/04/2000
• Est. Priority Date: 10/09/1997
• Status: Expired due to Term

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: Xu, Fan
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US08/947,665
• Time in Patent Office: 817 Days
• Field of Search: 382/232, 382/238, 382/240, 382/244, 395/601, 395/603, 395/605, 395/607, 395/611, 395/613, 395/427, 395/444, 341/51, 341/79
• US Class Current: 382/240
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

The present invention compresses data by initializing a compression tree and creating a plurality of first layer nodes therein. Then, digital data to be compressed is received. Child nodes which contain the digital data to be compressed are formed. A first portion of these child nodes is placed into the compression tree, with the child nodes in the first portion being referenced by child pointers. Next, a second portion of the child nodes is inserted into the compression tree in the form of a plurality of sibling groups, with each sibling group having a common parent node. The child nodes in each sibling group are arranged according to a predefined sorting criteria. Each of the child nodes in the sibling groups is referenced by a sibling pointer. As more data to compress is received, child nodes continue to be inserted into the sibling groups according to the predefined sorting criteria. As additional child nodes are inserted into the compression tree, index values which define a path from one of the first layer nodes to one of the child nodes are outpult, with the index values representing the compressed data. Data is decompressed by initializing a decompression tree and creating a plurality of first layer nodes therein. Then, the index values which represent the compressed digital data are processed. First, a matching node in the decompression tree is found which has the received index value. A path from the matching node to a node in the first layer of nodes is then found and the data values associated with nodes encountered in the path are output, thereby converting the index values into decompressed data.

Claims

1. A method for compressing digital data, comprising:

initializing a compression tree by creating a plurality of first layer nodes;

receiving digital data to be compressed;

creating child nodes which contain the digital data to be compressed;

placing a first portion of the child nodes into the compression tree, with the child nodes in the first portion being referenced by child pointers;

inserting a second portion of the child nodes into the compression tree in the form of a plurality of sibling groups, with each sibling group having a common parent node, wherein the child nodes in each sibling group are arranged according to a predefined sorting criteria, with the child nodes in the sibling groups being referenced by sibling pointers;

continuing to insert child nodes into the sibling groups according to the predefined sorting criteria as additional digital data to be compressed is received; and

outputting index values which define a path from one of the first layer nodes to one of the child nodes, wherein the index values represent the compressed digital data.

2. The method as recited in claim 1, further comprising:

initializing a decompression tree by creating a plurality of first layer nodes;

receiving the index values which represent the compressed digital data;

finding a matching node in the decompression tree which has the received index value;

traversing a path from the matching node to a node in the first layer of nodes; and

outputting data values associated with nodes encountered in the traversing step, wherein the compressed digital data represented by the index value is decompressed.

3. The method as recited in claim 2, further comprising:

receiving a subsequent index value;

determining a subsequent node in the first layer of nodes by traversing a path defined by the subsequent index value; and

adding a new node to the matching node, wherein the new node has a data value equal to the subsequent node, wherein the decompression tree is constructed to match the compression tree.

4. The method as recited in claim 2, further comprising reordering the data values from first to last before the outputting step.

5. The method as recited in claim 1, wherein each node in the sibling groups has a right sibling pointer and a left sibling pointer, and wherein the predefined sorting criteria arranges nodes in the sibling groups with the data value of a right node being greater than the data value of the node whose right pointer points to the right node, and the data value of a left node being less than the data value of the node whose left pointer points to the left node.

6. The method as recited in claim 5, wherein the inserting step includes identifying the sibling group into which a node will be placed, then traversing the sibling nodes in the sibling group using the right and left pointers of the sibling nodes to place the node according to the predefined sorting criteria.

7. The method as recited in claim 1, further comprising:

sending the index values generated from the compression tree of a first computer over a computer network; and

receiving the index values on a second computer via the computer network, wherein the data is decompressed.

8. The method as recited in claim 1, wherein the first layer nodes contain nodes having data values for each unit of digital data that can be received.

9. A data processing system for compressing digital data, comprising:

memory means for storing digital information;

processing means, connected to memory means, for operating upon the digital information in the memory means;

the data processing system being operable in a compression mode of operation, wherein,

a compression tree is initialized by creating a plurality of iirst layer nodes;

digital data to be compressed is received;

child nodes which contain the digital data to be compressed are created;

a first portion of the child nodes is placed into the compression tree, with the child nodes in the first portion being referenced by child pointers;

a second portion of the child nodes is inserted into the compression tree in the form of a plurality of sibling groups, with each sibling group having a common parent node, wherein the child nodes in each sibling group are arranged according to a predefined sorting criteria, with the child nodes in the sibling groups being referenced by sibling pointers;

child nodes continue to be inserted into the sibling groups according to the predefined sorting criteria as additional digital data to be compressed is received; and

index values which define a path from one of the first layer nodes to one of the child nodes are output, wherein the index values represent the compressed digital data.

10. The data processing system as recited in claim 9, with the data processing system being operable in a decompression mode of operation, wherein:

a decompression tree is initialized by creating a plurality of first layer nodes;

the index values which represent the compressed digital data are received;

a matching node in the decompression tree is found which has the received index value;

a path from the matching node to a node in the first layer of nodes is traversed; and

data values associated with nodes encountered in the traversing step are output, wherein the compressed digital data represented by the index value is decompressed.

11. The data processing system as recited in claim 10, wherein the decompression mode of operation further includes:

a subsequent index value being received;

a subsequent node in the first layer of nodes being determined by traversing a path defined by the subsequent index value; and

a new node being added to the matching node, wherein the new node has a data value equal to the subsequent node, wherein the decompression tree is constructed to match the compression tree.

12. The data processing system as recited in claim 10, wherein the decompression mode of operation further includes the data values being reordered from first to last before the data values are output.

13. The data processing system as recited in claim 9, wherein each node in the sibling groups has a right sibling pointer and a left sibling pointer, and wherein the predefined sorting criteria arranges nodes in the sibling groups with the data value of a right node being greater than the data value of the node whose right pointer points to the right node, and the data value of a left node being less than the data value of the node whose left pointer points to the left node.

14. The data processing system as recited in claim 13, wherein the compression mode of operation includes the sibling group into which a node will be placed being identified, then traversing the sibling nodes in the sibling group using the right and left pointers of the sibling nodes to place the node according to the predefined sorting criteria.

15. The data processing system as recited in claim 9, further comprising:

a computer network;

a first data processing unit connected to the computer network, wherein the first data processing unit generates the index values using the compression tree and sends the index values over the computer network; and

a second data processing unit connected to the computer network, wherein the second data processing unit receives the index values via the computer network, and decompresses the data.

16. The data processing system as recited in claim 9, wherein the first layer nodes contain nodes having data values for each unit of digital data that can be received.

17. A computer program product having stored computer-readable instructions for directing a data processing system to compress digital data, comprising:

means for initializing a compression tree by creating a plurality of first layer nodes;

means for receiving digital data to be compressed;

means for creating child nodes which contain the digital data to be compressed;

means for placing a first portion of the child nodes into the compression tree, with the child nodes in the first portion being referenced by child pointers;

means for inserting a second portion of the child nodes into the compression tree in the form of a plurality of sibling groups, with each sibling group having a common parent node, wherein the child nodes in each sibling group are arranged according to a predefined sorting criteria, with the child nodes in the sibling groups being referenced by sibling pointers;

means for continuing to insert child nodes into the sibling groups according to the predefined sorting criteria as additional digital data to be compressed is received; and

means for outputting index values which define a path from one of the first layer nodes to one of the child nodes, wherein the index values represent the compressed digital data.

18. The computer program product as recited in claim 17, further comprising:

means for initializing a decompression tree by creating a plurality of first layer nodes;

means for receiving the index values which represent the compressed digital data;

means for finding a matching node in the decompression tree which has the received index value;

means for traversing a path from the matching node to a node in the first layer of nodes; and

means for outputting data values associated with nodes encountered in the traversing step, wherein the compressed digital data represented by the index value is decompressed.

19. The computer program product as recited in claim 18, further comprising:

means for receiving a subsequent index value;

means for determining a subsequent node in the first layer of nodes by traversing a path defined by the subsequent index value; and

means for adding a new node to the matching node, wherein the new node has a data value equal to the subsequent node, wherein the decompression tree is constructed to match the compression tree.

20. The computer program product as recited in claim 18, further comprising means for reordering the data values from first to last before the outputting step.

21. The computer program product as recited in claim 17, wherein each node in the sibling groups has a right sibling pointer and a left sibling pointer, and wherein the predefined sorting criteria arranges nodes in the sibling groups with the data value of a right node being greater than the data value of the node whose right pointer points to the right node, and the data value of a left node being less than the data value of the node whose left pointer points to the left node.

22. The computer program product as recited in claim 21, wherein the means for inserting includes means for identifying the sibling group into which a node will be placed, then traversing the sibling nodes in the sibling group using the right and left pointers of the sibling nodes to place the node according to the predefined sorting criteria.

23. The computer program product as recited in claim 17, further comprising:

means for sending the index values generated from the compression tree of a first computer over a computer network; and

means for receiving the index values on a second computer via the computer network, wherein the data is decompressed.

24. The computer program product as recited in claim 17, wherein the first layer nodes contain nodes having data values for each unit of digital data that can be received.