Data compression method and apparatus

• US 5,850,565 A
• Filed: 08/26/1996
• Issued: 12/15/1998
• Est. Priority Date: 08/26/1996
• Status: Expired due to Term

• Current Assignee: Micro Focus Software, Inc. (Open Text Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Wightman, Andrew Thomas
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US08/697,292
• Time in Patent Office: 841 Days
• Field of Search: 395/821, 395/309, 395/888, 395/892, 707/10, 341/67, 341/95, 341/106, 370/473
• US Class Current: 710/1
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A data compressor scans one or more data files to locate variable-length strings of characters (data) that can be more efficiently compressed by delta compression (i.e. by referring to a string in an earlier version of the data file) than by traditional compression (i.e. by referring to a string of characters that occurs earlier in the data file). The compressor employs a criterion to select the strings that are likely to be most amenable to delta compression, i.e. to provide the highest overall compression ratio. The compressor creates a dictionary that describes the selected strings, which can then be advantageously used to delta-compress edited (changed) versions of the data files for transmission to another computer. In addition, a "dual-mode" data compressor employs a combination of delta and traditional compression to efficiently compress data and send one or more files from a sending computer to a receiving computer, where a decompressor reconstitutes a copy of the files. As the dual-mode compressor processes the files, it creates a dictionary.

Claims

1. A method of sending data from an input file that is stored by a sending computer, over a communication channel, to a receiving computer, the receiving computer storing earlier data, the method comprising the steps:

(a) providing to the sending computer one or more first keys, each first key corresponding to an incompressible group of data in the earlier data, each incompressible group of data in the earlier data comprising a respective portion of non-preset size of said earlier data and being located between two respective compressible groups of data in said earlier data;

(b) determining a second key that corresponds to a second group of data in the input file;

(c) ascertaining whether the second key matches one of the first keys;

(d) if the second key matches one of the first keys, sending a control signal from the sending computer to the receiving computer, the control signal causing the receiving computer to copy, from the earlier data, the incompressible group of data that corresponds to the matching first key;

(e) if the second key does not match any of the first keys, sending, from the sending computer to the receiving computer, a representation of at least some of the second group of data in the input file; and

(f) repeating steps (b), (c), (d) and (e) for additional second groups of data in the input file until all data in the input file has been processed.

2. The method defined in claim 1, wherein step (a) comprises the steps of:

(a1) providing, on the sending computer, second earlier data that is identical to the earlier data stored by the receiving computer;

(a2) identifying one or more incompressible groups of data in the second earlier data; and

(a3) for each identified incompressible group of data, determining a first key that corresponds to the identified incompressible group of data.

3. The method defined in claim 1, wherein step (a) comprises the steps of:

(a1) identifying one or more incompressible groups of data in the earlier data stored by the receiving computer;

(a2) for each identified incompressible group of data, determining a first key that corresponds to the identified incompressible group of data; and

(a3) sending the determined first keys to the sending computer.

4. A method of producing a dictionary that contains descriptions of one or more incompressible groups of data, the incompressible groups of data being stored in one or more computer-readable files, the method comprising the steps:

(a) locating, in the one or more computer-readable files, a group of data that cannot be compressed in accordance with a compression method and that is located next to at least one group of data that can be compressed in accordance with said compression method, each of the located incompressible group of data and the group of data that can be compressed in accordance with said compression method being of a respective non-preset size;

(b) determining a key that corresponds to the located incompressible group of data;

(c) storing, in a memory, an address of the located incompressible group of data and the key that corresponds to the located incompressible group of data; and

(d) repeating steps (a), (b) and (c) to produce each description in the dictionary.

5. The method defined in claim 4, wherein the address of the located incompressible group of data comprises an offset within the one or more computer-readable files of the located incompressible group of data and a length of the located incompressible group of data.

6. The method defined in claim 5, wherein the address of the located incompressible group of data further comprises an identification of one of the one or more computer-readable files.

7. The method defined in claim 4, wherein the key that corresponds to the located incompressible group of data is determined from at least some of the located incompressible group of data.

8. The method defined in claim 4, wherein the key comprises a CRC value that is calculated from at least some of the located incompressible group of data.

9. The method defined in claim 8, wherein the key additionally comprises a hash value that is calculated from at least some of the located incompressible group of data.

10. A method of sending data from an input file stored by a sending computer, over a communication channel, to a receiving computer, the method comprising the steps:

(a) dividing the input file into portions of respective non-preset sizes;

(b) for each portion of the input file;

(b1) selecting one of a plurality of compression methods;

(b2) processing the portion of the input file in accordance with the selected compression method to produce resulting data; and

(b3) sending the resulting data from the sending computer, over the communication channel, to the receiving computer.

11. The method defined in claim 10, wherein the plurality of compression methods comprises a traditional compression method and a delta compression method.

12. The method defined in claim 11, wherein step (b1) comprises the step of ascertaining which of the plurality of compression methods can compress, with a larger compression ratio, each respective portion of the input file.

13. The method defined in claim 11, wherein step (b1) comprises the steps of:

(i) ascertaining whether each respective portion of the input file can be compressed using the delta compression method;

(ii) if a given portion of the input file can be compressed using the delta compression method, selecting the delta compression method otherwise selecting the traditional compression method.

14. The method defined in claim 11, wherein the receiving computer stores earlier data, the method additionally comprising the steps of:

(c) providing to the sending computer one or more dictionary entries, each dictionary entry corresponding to a portion of the earlier data;

(d) ascertaining whether a respective portion of the input file is described by one of the dictionary entries; and

(e) if the respective portion of the input file is described by one of the dictionary entries, selecting the delta compression method otherwise selecting the traditional compression method.

15. The method defined in claim 14, wherein each dictionary entry stores a first CRC value ascertained from at least part of the corresponding portion of the earlier data and step (d) comprises the steps of:

(d1) ascertaining a second CRC value from the respective portion of the input file and

(d2) ascertaining whether the second CRC value is equivalent to the first CRC value stored in one of the dictionary entries.

16. The method defined in claim 10, wherein said respective sizes permit said input file to be partitioned such that, if possible, at least one of said portions is more amenable to compression by a certain one of said compression methods than by another of said compression methods, and both said certain one and said another of said compression methods are used to compress said input file.

17. The method defined in claim 16, wherein said certain one of said compression methods comprises delta compression.

18. The method defined in claim 17, wherein said at least one portion is located between and is contiguous with two other respective portions of said input file that are more amenable to compression by said another compression method than by said delta compression.

19. The method defined in claim 18, wherein each of said at least one and said two other respective portions of said input file are of different respective sizes.