System, method and algorithm for the optimization of entropy for lossless compression

• US 7,111,094 B1
• Filed: 08/02/2000
• Issued: 09/19/2006
• Est. Priority Date: 08/02/1999
• Status: Expired due to Fees

• Current Assignee: Stargate, Ltd.
• Original Assignee: Transfinity Corp.
• Inventors: Liu, Shin-Ping, Harold, Michael D., Tucker, Dennis
• Primary Examiner(s): Elamin, A.
• Application Number:
  US09/631,368
• Time in Patent Office: 2,239 Days
• Field of Search: 710/65, 710/68, 358/1.15, 358/68, 701/3, 382/232, 382/244, 382/246, 382/247, 382/248, 341/51, 381/51
• US Class Current: 710/65
• CPC Class Codes: H04B 1/662 using a time/frequency relationship, e.g. time compression or expansion

Abstract

A system, method and algorithm for performing statistical analysis on an input data source to determine an optimal token size resulting in an increased ratio value is described. Changes to the values of the tokens prior to compression may result in an overall compression increase even if the data source has been previously compressed. Specific techniques for modifying the tokens include varying the base size, rearrangement of the tokens, and modifications by matrix multiplication. After modification of the tokens, compression of the data using one or more lossless compression methods may be performed. The technique may be repeated by using the output of previous compression processes as input to additional entropy and compression optimization.

Claims

1. A method for lossless compression of input data, said method comprising the steps of:

receiving said input data, said input data having a first entropy ratio associated therewith and being ordered pursuant to a first format;

transforming said input data into a plurality of blocks pursuant to a second format;

calculating a second entropy ratio associated with said transformed input data;

comparing said second entropy ratio associated with said transformed input data to a reference entropy ratio;

if said reference entropy ratio is less than said second entropy ratio, said reference entropy ratio is set equal to said second entropy ratio; and

compressing said transformed input data in response to the second entropy ratio.

2. The method according to claim 1, wherein said step of transforming divides said input data into said plurality of blocks, each of said blocks having a given size.

3. The method according to claim 1, wherein said step of transforming rearranges a plurality of data within said input data, said second entropy ratio being calculated from said rearranged input data.

4. The method according to claim 3, wherein said plurality of data are rotated.

5. The method according to claim 3, wherein said step of transforming modifies said input data via matrix multiplication.

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

repeating said steps of comparing and transforming for a plurality of additional formats, and selecting one of the plurality of additional formats with the greatest entropy ratio.

7. A system for compressing input data, said system comprising:

an input device operable to receive said input data, said input data being ordered pursuant to a first format; and

a processor operable to divide the input data into a first plurality of tokens and modify the format of the input data included within each of the tokens included in the first plurality of tokens, said processor further operable to determine a first entropy ratio associated with the first plurality of tokens, said processor further operable to divide the input data into a second plurality of tokens and modify the format of the input data included within each of tokens included in the second plurality of tokens, said processor further operable to determine a second entropy ratio associated with the second plurality of tokens, said processor further operable to compress the second plurality of tokens in response to comparing the second entropy ratio to the first entropy ratio.

8. The system of claim 7, wherein said input device is a communications interface.

9. The system of claim 7, wherein said input device is a memory.

10. The system of claim 7, and further comprising memory in communication with said processor, said memory operable to store the transformed input data.

11. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for compressing input data, the computer readable program code means in said article of manufacture comprising:

computer readable program means for receiving said input data, said input data having a first entropy ratio associated therewith and being ordered pursuant to a first format;

computer readable program means for transforming said input data into a plurality of blocks pursuant to a second format;

computer readable program means for calculating a second entropy ratio associated with said transformed input data;

computer readable program means for comparing said second entropy ratio to a reference entropy ratio;

computer readable program means for setting said reference entropy ratio equal to said second entropy ratio if said second entropy ratio exceeds said reference entropy ratio; and

computer readable program means for compressing the transformed input data.

12. A method for compressing input data, said method comprising:

receiving said input data, said input data having a first entropy ratio and having a first format;

changing said format of said input data from said first format to said second format;

calculating a second entropy ratio associated with said second format of said input data;

comparing said second entropy ratio to a reference entropy ratio;

setting said reference entropy ratio equal to said second entropy ratio if said second entropy ratio exceeds said reference entropy ratio; and

compressing said second format of input data using said second entropy ratio.

13. The method of claim 12, wherein changing said format of said input data includes subdividing an initial block of said input data into a plurality of smaller blocks, each of said smaller blocks having less data than said initial block.

14. The method of claim 12, wherein changing said format of said input data includes rearranging an order of data within said input data.

15. The method of claim 12, wherein changing said format of said input data includes rotating said input data.

16. The method according to claim 12, wherein changing said format of said input data includes modifying said input data via matrix multiplication.