Method and apparatus for adaptive data compression

• US 5,949,355 A
• Filed: 08/21/1997
• Issued: 09/07/1999
• Est. Priority Date: 12/06/1994
• Status: Expired due to Fees

• Current Assignee: Compression Financing, LLC
• Original Assignee: Cennoid Technologies, Inc.
• Inventors: Panaoussis, Spyros
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/915,961
• Time in Patent Office: 747 Days
• Field of Search: 341/51, 341/63, 341/76, 341/106
• US Class Current: 341/51
• 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

Abstract

The present invention relates to data compression systems and methods wherein text can be compressed by encoding repetitions of blocks of characters, or through a straight encoding scheme that converts eight-bit character values to four-bit character values by eliminating values for characters that are not valid word-starting characters or valid next-letter characters for a given preceding letter. Block compression is accomplished through the use of data structures that track the successive occurrence of valid block-repetition starting characters, and their lengths. Repeat-relative block compression is accomplished by detecting character sequences that can be expressed as the value of a previously-occurring character sequence plus or minus an offset.

Claims

1. A method of data compression for compressing a data record made up of a plurality of data elements each made up of a plurality of bits comprising:

a) scanning the data record to characterize the data content of the record by at least identifying and counting the occurrence of types of data elements, and classifying data elements according to a set of predetermined groups;

b) determining within the data record the most significant of the set of predetermined groups;

c) identifying patterns of data elements in the data record in response to the step of determining including detecting and encoding repeating blocks of data elements;

d) assigning at least one of a set of predetermined compression modes in response to the identifying step; and

e) compressing the data record according to at least one of the compression modes responsive to the assigning.

2. The method of claim 1 wherein at least some data elements are eight bit bytes and further comprising determining if data is full range binary data including tracking the eighth bit of the eight bit data elements.

3. The method of claim 1 further comprising compressing the data record using at least one of the predetermined compression modes assigned based upon at least the predetermined groups, and the patterns.

4. The method of claim 3 wherein at least some data elements are represented by eight bit numeric codes, further comprising compressing the eight bit numeric codes with a corresponding four bit code.

5. The method of claim 1 further comprising:

detecting a repeat-relative character sequence that can be expressed as the value of the code for a previously-occurring character sequence plus or minus a given number;

converting the repeat-relative character sequence to a compressed code, said compressed code comprising a repeat-relative prefix, a sign flag, and an offset value, wherein said repeat-relative prefix identifies the type of coding, the sign flag indicates the sign of the offset value, and the offset value indicates the value to be added or subtracted from the value of the code for the previously-occurring character sequence.

6. A system for compressing a data record made up of a plurality of data elements each made up of a plurality of bits comprising:

a) means for scanning the data record to characterize the data content of the record by at least identifying and counting the occurrence of types of data elements, and classifying data elements according to a set of predetermined groups;

b) means for determining within the data record the most significant of the set of predetermined groups;

c) means for identifying patterns of data elements in the data record in response to the step of determining including detecting and encoding repeating blocks of data elements;

d) means for assigning at least one of a set of predetermined compression modes in response to the identifying step; and

e) means for compressing the data record according to at least one of the compression modes responsive to the assigning.

7. The system of claim 6 wherein at least some data elements are eight bit bytes and further comprising means for determining if data is full range binary data including tracking the eighth bit of the eight bit data elements.

8. The system of claim 6 further comprising means for compressing the data record using at least one of the predetermined compression modes assigned based upon at least the predetermined groups, and the patterns.

9. The system of claim 8 wherein at least some data elements are represent ed by eight bit numeric codes, further comprising means for compressing the eight bit numeric codes with a corresponding four bit code.

10. The system of claim 6 further comprising:

means for detecting a repeat-relative character sequence that can be expressed as the value of the code for a previously-occurring character sequence plus or minus a given number; and

means for converting the repeat-relative character sequence to a compressed code, said compressed code comprising a repeat-relative prefix, a sign flag, and an offset value, wherein said repeat-relative prefix identifies the type of coding, the sign flag indicates the sign of the offset value, and the offset indicates the value to be added or subtracted from the value of the code for the previously-occurring character sequence.