US5850565A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression method and apparatus
Assignee: Micro Focus Software Inc
•
Filing: 1996-08-26
•
Granted: 1998-12-15
•
Expires: 2016-08-26
Abstract
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.
Inventors
- 👤 Andrew Thomas Wightman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:53
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
238 words
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.
Claim 2
Independent Claim
238 words
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.
Claim 3
Dependent Claim
70 words
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.
Claim 4
Dependent Claim
63 words
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.
Claim 5
Independent Claim
163 words
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.
Claim 6
Independent Claim
163 words
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.
Claim 7
Dependent Claim
43 words
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.
Claim 8
Dependent Claim
29 words
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.
Claim 9
Dependent Claim
31 words
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.
Claim 10
Dependent Claim
27 words
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.
Claim 11
Dependent Claim
28 words
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.
Claim 12
Independent Claim
92 words
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.
Claim 13
Independent Claim
92 words
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.
Claim 14
Dependent Claim
22 words
The method defined in claim 10, wherein the plurality of compression methods comprises a traditional compression method and a delta compression method.
Claim 15
Dependent Claim
35 words
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.
Claim 16
Dependent Claim
59 words
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.
Claim 17
Dependent Claim
89 words
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.
Claim 18
Dependent Claim
71 words
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.
Claim 19
Dependent Claim
66 words
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.
Claim 20
Dependent Claim
17 words
The method defined in claim 16, wherein said certain one of said compression methods comprises delta compression.
Claim 21
Dependent Claim
43 words
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.
Claim 22
Dependent Claim
28 words
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.
References Cited (Backward Citations)
US4701745A
Cited
US5016009A
Cited
US5126739A
Cited
US5479654A
Cited
US5261060A
Cited
US5229768A
Cited
US5446888A
Cited
US5598543A
Cited
EP0713183A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-14 | 2002-06-15 | 2002-12-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-14 | 2006-06-15 | 2006-12-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-14 | 2010-06-15 | 2010-12-15 | $7700.00 | Window Closed / Lapsed |