Optimal sequential (de)compression of digital data

• US 9,298,722 B2
• Filed: 09/28/2009
• Issued: 03/29/2016
• Est. Priority Date: 07/16/2009
• Status: Active Grant

• Current Assignee: Novell Incorporated (Open Text Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Teerlink, Craig N.
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US12/568,190
• Publication Number:
  US 20110016096A1
• Time in Patent Office: 2,374 Days
• Field of Search: 707/741, 707/693
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: Y10S 707/972 Partitioning

Abstract

Methods and apparatus involve an original data stream arranged as a plurality of symbols. Of those symbols, all possible tuples are identified and the highest or most frequently occurring tuple is determined. A new symbol is created and substituted for each instance of the highest occurring tuple, which results in a new data stream. The new data stream is encoded and its size determined. Also, a size of a dictionary carrying all the original and new symbols is determined. The encoding size, the size of the dictionary and sizes of any other attendant overhead is compared to a size of the original data to see if compression has occurred, and by how much. Upon reaching pre-defined objectives, compression ceases. Decompression occurs oppositely. Other features include resolving ties between equally occurring tuples, path weighted Huffman coding, storing files, decoding structures, and computing arrangements and program products, to name a few.

Claims

1. In a computing system environment, a method of utilizing a computing device for compressing original data arranged as a plurality of symbols, comprising:

recursively and sequentially advancing through the plurality of symbols to determine a most frequently occurring tuple of the plurality of symbols, wherein a tuple comprises at least two symbols;

recursively replacing, in the original data, the determined most frequently occurring tuple by a new symbol to generate a new compressed data stream;

recursively comparing a size of a most recent new compressed data stream and attendant overhead to a size of an immediately preceding new compressed data stream and attendant overhead to determine if a compression goal for the original data has been achieved, wherein the attendant overhead indicates an amount of computing resources required to operate a corresponding compressing operation; and

terminating the recursively determining, replacing, and comparing on determining that the compression goal has been achieved.

2. The method of claim 1, further including creating a dictionary for every symbol in the plurality of symbols.

3. The method of claim 2, further including encoding all of the plurality of symbols.

4. The method of claim 3, further including calculating a size for each of the encoded plurality of symbol.

5. The method of claim 2, further including calculating a size for the dictionary.

6. The method of claim 1, further including determining whether a compression goal has been achieved relative to a size of the original data.

7. The method of claim 1, wherein the determining the most frequently occurring tuple of the plurality of symbols further includes resolving ties between two or more tuples occurring a same number of times.

8. The method of claim 7, further including using the Pythagorean Theorem when resolving ties.

9. A method utilizing a computing device for compressing original data arranged as a plurality of symbols, comprising:

recursively and sequentially advancing through the original data to determine all possible two-adjoining symbols of the plurality of symbols;

recursively replacing in the original data a new symbol for a determined pair of most frequently occurring two-adjoining symbols of the plurality of symbols to generate a new compressed data stream;

recursively comparing a size of a most recent new compressed data stream and attendant overhead to a size of an immediately preceding new compressed data stream and attendant overhead to determine if a compression goal for the original data has been achieved, wherein the attendant overhead indicates an amount of computing resources required to operate a corresponding compressing operation; and

terminating the recursively determining, replacing, and comparing on determining that the compression goal has been achieved.

10. The method of claim 9, further including adding an entry for the new symbol to a dictionary already representing the plurality of symbols.

11. The method of claim 9, further including encoding the new compressed data stream and calculating a size of the new compressed data stream.

12. The method of claim 11, determining whether the size of the encoded new compressed data stream and associated attendant overhead is smaller or greater than a size of the original data.

13. The method of claim 12, if the size of the encoded new compressed data stream and the associated attendant overhead is not smaller than the size of the original data, repeating the replacing and the encoding until such time as the size of the new compressed data stream becomes smaller than the size of the original data.

14. In a computing system environment, a method utilizing a computing device for compressing original data arranged as a plurality of symbols, comprising:

recursively advancing through the plurality of symbols sequentially to determine all possible tuples of the plurality of symbols, wherein a tuple comprises two or more symbols;

recursively determining most frequently occurring tuple of the identified all possible tuples;

recursively replacing in the original data a new symbol for the determined most frequently occurring tuple to generate a new compressed data stream;

recursively encoding the new compressed data stream;

recursively comparing a size of a most recent encoded new compressed data stream and attendant overhead to a size of an immediately preceding encoded new compressed data stream and attendant overhead to determine if a compression goal for the original data has been achieved; and

terminating the recursively advancing, determining, replacing, encoding, and comparing on determining that the compression goal has been achieved.

15. The method of claim 14, further including creating a dictionary for every symbol in the new compressed data stream.

16. The method of claim 15, further including calculating a size for the encoded new compressed data stream and the dictionary.

17. The method of claim 16, further including comparing the calculated size of the new compressed data stream to a size of the original data to determine whether a pre-defined compression goal has been achieved.

18. The method of claim 14, wherein the determining the most frequently occurring tuple further includes resolving ties between two or more tuples occurring a same number of times.

19. The method of claim 15, further including decompressing the encoded new compressed data stream using the dictionary having every symbol in the new compressed data stream.