Compression of structured data

• US 5,864,860 A
• Filed: 09/30/1996
• Issued: 01/26/1999
• Est. Priority Date: 02/08/1996
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Holmes, Keith
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/723,073
• Time in Patent Office: 848 Days
• Field of Search: 341/51, 395/888, 707/100, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for compressing a data sequence having a plurality of records, where each record has a plurality of fields with each field being arranged to contain a data item. The system compares a data item in a current field of a current record with a data item of a corresponding field of a preceding record. If there is a match, the current data item is replaced by a token indicating the match.

Claims

1. A method of compressing a data sequence comprising a plurality of records, each record having a plurality of fields and each field being arranged to contain a data item, the method comprising the steps of:

(a) for a current field within a current record other than the first record in the data sequence;

(i) comparing (250) the data item in the current field with the data item in the corresponding field of a preceding record;

(ii) if the data item matches the data item in the corresponding field, replacing (270) the current field, data item by a token indicating the match; and

(b) repeating step (a) for a predetermined number of fields in a plurality of records of the data sequence.

2. A method as claimed in claim 1, wherein said step (a) is repeated for said predetermined number of fields in every record of the data sequence.

3. A method as claimed in claim 1, wherein the predetermined number of fields is every field in the current record.

4. A method as claimed in claim 1, wherein, at step (a)(i), the data item in the current field is compared with the data item in the corresponding field of the immediately preceding record, and the method further comprises, subsequent to performing the comparison step (a) for the predetermined number of fields in the current record, the step (290) of storing the uncompressed current record as the immediately preceding record for use in the performance of said step (a)(i) on the predetermined number of fields of a subsequent record.

5. A method as claimed in claim 1, wherein steps (a) and (b) are performed by a processor of a server computer (30), the method comprising the further step of sending the data records of the data sequence as compressed by steps (a) and (b) over a network to a client computer (10).

6. A method of decompressing a data sequence compressed according to the method as claimed in claim 1, comprising the steps of:

(A) for each field within a current record other than the first record in the data sequence;

determining whether the field contains the token;

if the field does contain the token, replacing the token by the data item in the corresponding field of a preceding record; and

(B) repeating step (A) for a plurality of records of the data sequence.

7. A system for compressing a data sequence comprising a plurality of records, each record having a plurality of fields and each field being arranged to contain a data item, the system comprising:

comparison means (60) which, for a current field within a current record other than the first record in the data sequence, is arranged to compare the data item in the current field with the data item in the corresponding field of a preceding record; and

match indication means (70), responsive to a signal from the comparison means (60) indicating that the data item matches the data item in the corresponding field, for replacing the current field data item by a token indicating the match;

the comparison means (60) being arranged to repetitively perform the comparison process on a predetermined number of fields in a plurality of records of the data sequence.

8. A system as claimed in claim 7, wherein the comparison means (60) is arranged to perform the comparison process on the predetermined number of fields in every record of the data sequence.

9. A system as claimed in claim 7, wherein the predetermined number of fields is every field in the current record.

10. A system as claimed in claim 7, wherein the comparison means (60) is arranged to compare the data item in the current field with the data item in the corresponding field of the immediately preceding record, and the system further comprises storing means operable, subsequent to the comparison means having performed the comparison for the predetermined number of fields in the current record, to store (290) the uncompressed current record as the immediately preceding record for use by the comparison means (60) when performing the comparison step on the predetermined number of fields of a subsequent record.

11. A system as claimed in claim 7, wherein the system is incorporated within a server computer (30), the server being arranged to output the data records of the data sequence as compressed by the system for transfer over a network to a client computer (10).