Compressing sets of integers

• US 5,940,833 A
• Filed: 07/12/1996
• Issued: 08/17/1999
• Est. Priority Date: 07/12/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Benson, Max L.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/678,966
• Time in Patent Office: 1,131 Days
• Field of Search: 341/51, 341/67, 707/1, 707/101, 707/102, 707/200, 707/100, 707/2
• US Class Current: 1/1
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

In one aspect, the disclosed technique detects common leading byte patterns in the integers so that these patterns need only be stored once in the encoded byte stream. Those integers that share a common leading byte pattern are stored in truncated form, without their common leading bytes. These truncated integers may themselves be further examined to determine if any of them share additional common leading bytes beyond those already detected. Thus, the technique lends itself naturally to description using the language of trees. Integers with a common leading byte pattern are stored as child nodes, their parent being the node containing the common byte pattern. Child nodes consist only of those bytes remaining after the initial byte pattern has been extracted; the greater the number of children, the greater are the efficiency gains. All the children of a given tree or subtree are similarly examined for common leading byte patterns, ignoring those bytes that are already accounted for in their ancestor nodes. In a second aspect, the disclosed technique makes use of "clustering", a second type of locality that is not reached by the interval concept. A cluster is a sequence of singleton integers that are very close together but do not form a contiguous interval. The technique recognizes that such a cluster can be compactly stored as a bitmap, in which each active bit ("1-bit") represents a member of the cluster. The choice of bitmap size (e.g., 1 byte, 2 bytes, etc.) can be calibrated to suit the clustering characteristics of the input data set.

Claims

1. A computer implemented method of compressing a data stream that includes a set of integers in order to produce a compressed byte stream, the method comprising the steps of:

examining the data stream to identify a subset of integers that share one or more common leading bytes;

general a first group of bytes that represents the common leading bytes of the identified subset of integers, the first group of bytes comprising only a single instance of the common leading bytes in order to compress the overall data stream;

generating a second group of bytes that represents a truncated form of the integers of the identified subset, the truncated form resulting from removal of the common leading bytes; and

generating a compressed byte stream that includes the first and second groups of bytes.

2. The method of claim 1, wherein the set of integers included in the data stream comprises a subset of one or more contiguous integers represented as an interval comprising a low bound and a high bound.

3. The method of claim 1, wherein the set of integers included in the data stream comprises integers arranged in sorted order, and no integer in the set appears more than once.

4. The method of claim 1, further comprising the steps of:

examining the integers in truncated form in the second group of bytes to identify a subset of truncated integers that share one or more common leading bytes;

generating a third group of bytes that represents the common leading bytes of the identified subset of truncated integers, the third group of bytes comprising only a single instance of the common leading bytes of the identified subset of truncated integers to further compress the overall data stream;

generating a fourth group of bytes that represents a further truncated form of the truncated integers of the identified subset of truncated integers, the further truncated form resulting from removal of the common leading bytes of the identified subset of truncated integers; and

including the third and fourth groups of bytes in the compressed byte stream.

5. The method of claim 1, wherein according to a tree model representation of the compressed byte stream, the bytes of the compressed byte stream comprise at least one tree, one node, and a plurality of leaves.

6. The method of claim 1, wherein the integers represent database record IDs.

7. The method of claim 1, wherein the step of generating the second group of bytes includes a step of representing the truncated form of the integers of the identified subset using a bitmap, comprising the steps of:

selecting the lowest-value integer of the identified subset as a bitmap reference point and including the truncated form of the selected lowest-value integer in the second group of bytes;

creating a bitmap having a size of one byte or larger, wherein each of the integers in the identified subset, other than the lowest-value integer, is mapped in the bitmap; and

including the bitmap in the second group of bytes.

8. A computer implemented method of compressing a data stream that includes a set of integers in order to produce a compressed byte stream, the method comprising the steps of:

examining the data stream to identify a subset of integers that share one or more common leading bytes that are suited for representation using a bitmap having a size equal to a selected number of bytes;

generating a first group of bytes that represents the common leading bytes of the identified subset of integers, the first group of bytes comprising only a single instance of the common leading bytes in order to compress the overall data stream;

generating a second group of bytes that represents a truncated form of the integers of the identified subset, the truncated form resulting from removal of the common leading bytes, comprising the steps of;

selecting the lowest-value integer of the identified subset as a bitmap reference point and including the truncated form of the selected lowest-value integer in the second group of bytes;

creating a bitmap having a size equal to the selected number of bytes, wherein each of the integers in the identified subset, other than the lowest-value integer, is mapped in the bitmap; and

including the bitmap in the second group of bytes; and

generating a compressed byte stream that includes the first and second groups of bytes.

9. The method of claim 8, wherein the set of integers included in the data stream comprises a subset of one or more contiguous integers represented as an interval comprising a low bound and a high bound.

10. The method of claim 8, wherein the set of integers included in the data stream comprises integers arranged in sorted order, and no integer in the set appears more than once.

11. The method of claim 8, wherein the bitmap is created by selectively setting the state of particular bits in the bitmap in order to specify the value, I, of each of the integers in the identified subset, other than the lowest-value integer, according to the function I(b,r)=r+b+1, where r is the bitmap reference point and b is the position of the particular bit in the bitmap.

12. The method of claim 8, wherein the integers represent database record IDs.

13. A computer program, residing on a computer readable medium, for compressing a data stream that includes a set of integers in order to produce a compressed byte stream, the computer program comprising instructions for executing the steps of:

examining the data stream to identify a subset of integers that share one or more common leading bytes;

generating a first group of bytes that represents the common leading bytes of the identified subset of integers, the first group of bytes comprising only a single instance of the common leading bytes in order to compress the overall data stream;

generating a second group of bytes that represents a truncated form of the integers of the identified subset, the truncated form resulting from removal of the common leading bytes; and

generating a compressed byte stream that includes the first and second groups of bytes.

14. The computer program of claim 13, wherein the set of integers included in the data stream comprises a subset of one or more contiguous integers represented as an interval comprising a low bound and a high bound.

15. The computer program of claim 13, wherein the set of integers included in the data stream comprises integers arranged in sorted order, and no integer in the set appears more than once.

16. The computer program of claim 13, further comprising instructions for executing the steps of:

examining the integers in truncated form in the second group of bytes to identify a subset of truncated integers that share one or more common leading bytes;

generating a third group of bytes that represents the common leading bytes of the identified subset of truncated integers, the third group of bytes comprising only a single instance of the common leading bytes of the identified subset of truncated integers to further compress the overall data stream;

generating a fourth group of bytes that represents a further truncated form of the truncated integers of the identified subset of truncated integers, the further truncated form resulting from removal of the common leading bytes of the identified subset of truncated integers; and

including the third and fourth groups of bytes in the compressed byte stream.

17. The computer program of claim 13, wherein according to a tree model representation of the compressed byte stream, the bytes of the compressed byte stream comprise at least one tree, one node, and a plurality of leaves.

18. The computer program of claim 13, wherein the integers represent database record IDs.

19. The computer program of claim 13, wherein the step of generating the second group of bytes includes a step of representing the truncated form of the integers of the identified subset using a bitmap, comprising the steps of:

selecting the lowest-value integer of the identified subset as a bitmap reference point and including the truncated form of the selected lowest-value integer in the second group of bytes;

creating a bitmap having a size of one byte or larger, wherein each of the integers in the identified subset, other than the lowest-value integer, is mapped in the bitmap; and

including the bitmap in the second group of bytes.

20. A computer program, residing on a computer readable medium, for compressing a data stream that includes a set of integers in order to produce a compressed byte stream, the computer program comprising instructions for executing the steps of:

examining the data stream to identify a subset of integers that share one or more common leading bytes and that are suited for representation using a bitmap having a size equal to a selected number of bytes;

generating a first group of bytes that represents the common leading bytes of the identified subset of integers, the first group of bytes comprising only a single instance of the common leading bytes in order to compress the overall data stream;

generating a second group of bytes that represents a truncated form of the integers of the identified subset, the truncated form resulting from removal of the common leading bytes comprising the steps of;

selecting the lowest-value integer of the identified subset as a bitmap reference point and including the truncated form of the selected lowest-value integer in the second group of bytes;

creating a bitmap having a size equal to the selected number of bytes, wherein each of the integers in the identified subset, other than the lowest-value integer, is mapped in the bitmap; and

including the bitmap in the second group of bytes; and

generating a compressed byte stream that includes the first and second groups of bytes.

21. The computer program of claim 20, wherein the set of integers included in the data stream comprises a subset of one or more contiguous integers represented as an interval comprising a low bound and a high bound.

22. The computer program of claim 20, wherein the integers included in the data stream comprises integers arranged in sorted order, and no integer in the set appears more than once.

23. The computer program of claim 20, wherein the bitmap is created by selectively setting the state of particular bits in the bitmap in order to specify the value, I, of each of the integers in the identified subset, other than the lowest-value integer according to the function I(b, r)=r+b+1, where r is the bitmap reference point and b is the position of the particular bit in the bitmap.

24. The computer program of claim 20, wherein the integers represent database record IDs.

25. A computer implemented method of compressing a set of integers to produce an encoded byte stream, the method comprising:

selecting a subset of integers suited for bitmap representation;

selecting a reference point; and

creating a bitmap of one or more bytes in which the state of a particular bit represents whether a particular integer is contained in the subset and in which the location of the particular bit in the bitmap represents the location of the integer relative to the reference point, wherein the integer whose location is relative to the reference point is given by the function I(b,r)=r+b+1, where r is the reference point and b is the bit position in the bitmap.

26. A computer program, residing on a computer readable medium, for compressing a set of integers to produce an encoded byte stream, the computer program comprising instructions for:

selecting a subset of integers suited for bitmap representation;

selecting a reference point; and

creating a bitmap of one or more bytes in which the state of a particular bit represents whether a particular integer is contained in the subset and in which the location of the particular bit in the bitmap represents the location of the integer relative to the reference point, wherein the integer whose location is relative to the reference point is given by the function I(b,r)=r+b+1, where r is the reference point and b is the bit position in the bitmap.