Method and System for Compressing Data

• US 20090083267A1
• Filed: 02/12/2008
• Published: 03/26/2009
• Est. Priority Date: 09/24/2007
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Johnson, Carl Eric
• Granted Patent: US 8,463,759 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

The present disclosure is directed to a method and system for compressing data. In accordance with a particular embodiment of the present disclosure, at least one data string is received. The at least one data string includes characters. A token string corresponding to the at least one data string is generated. At least one repeated substring in the at least one data string is identified. A refer-back token associated with the at least one repeated substring is generated. The refer-back token indicates a position of the at least one repeated substring and a length of the at least one repeated substring.

Claims

1. A method for compressing data, comprising:

receiving at least one data string, the at least one data string comprising a plurality of characters;

generating a token string corresponding to the at least one data string;

identifying at least one repeated substring in the at least one data string; and

generating a refer-back token associated with the at least one repeated substring, the refer-back token indicating a position of the at least one repeated substring and a length of the at least one repeated substring.

2. The method of claim 1, wherein:

the data string has a first byte length;

the token string has a second byte length; and

the first byte length is greater than the second byte length.

3. The method of claim 1, wherein generating a token string corresponding to the at least one data string comprises generating the token string using Run Length Encoding (RLE).

4. The method of claim 1, further comprising storing the token string.

5. The method of claim 1, wherein identifying at least one repeated substring in the at least one data string comprises identifying at least two matching characters in the at least one data string.

6. The method of claim 1, further comprising storing the repeated substring.

7. The method of claim 1, wherein at least one token in the token string comprises an exact text token.

8. A system for compressing data, comprising:

a processor; and

a storage device embodying a program of instructions operable, when executed on the processor, to;

receive at least one data string, the at least one data string comprising a plurality of characters;

generate a token string corresponding to the at least one data string;

identify at least one repeated substring in the at least one data string; and

generate a refer-back token associated with the at least one repeated substring, the refer-back token indicating a position of the at least one repeated substring and a length of the at least one repeated substring.

9. The system of claim 8, wherein:

the data string has a first byte length;

the token string has a second byte length; and

the first byte length is greater than the second byte length.

10. The system of claim 8, wherein the program of instructions is further operable to generate the token string using Run Length Encoding (RLE).

11. The system of claim 8, wherein the program of instructions is further operable to store the token string.

12. The system of claim 8, wherein the program of instructions is further operable to identify at least two matching characters in the at least one data string.

13. The system of claim 8, wherein the program of instructions is further operable to store the repeated substring.

14. The system of claim 8, wherein at least one token in the token string comprises an exact text token.

15. Logic encoded in media, the logic being operable, when executed on a processor, to:

receive at least one data string, the at least one data string comprising a plurality of characters;

generate a token string corresponding to the at least one data string;

identify at least one repeated substring in the at least one data string;

generate a refer-back token associated with the at least one repeated substring, the refer-back token indicating a position of the at least one repeated substring and a length of the at least one repeated substring.

16. The logic of claim 15, wherein:

the data string has a first byte length;

the token string has a second byte length; and

the first byte length is greater than the second byte length.

17. The logic of claim 15, wherein the logic is further operable to generate the token string using Run Length Encoding (RLE).

18. The logic of claim 15, wherein the logic is further operable to store the token string.

19. The logic of claim 15, wherein the logic is further operable to identify at least two matching characters in the at least one data string.

20. The logic of claim 15, wherein the logic is further operable to store the repeated substring.