Method and system for compressing data

• US 8,463,759 B2
• Filed: 02/12/2008
• Issued: 06/11/2013
• Est. Priority Date: 09/24/2007
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Inventors: Johnson, Carl Eric
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): OWYANG, MICHELLE N
• Application Number:
  US12/029,943
• Publication Number:
  US 20090083267A1
• Time in Patent Office: 1,946 Days
• Field of Search: 707/693
• US Class Current: 707/693
• 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 substrings, each substring comprising a plurality of characters;

identifying a first substring in the at least one data string, the first substring comprising a plurality of characters that are the same as a plurality of characters of a second substring in the at least one data string;

generating, by one or more processors, a refer-back token associated with the second substring, the refer-back token indicating a position of the first substring within a token string, the token string being a compressed version of at least a portion of the at least one data string, the position indicated by the refer-back token expressed as an offset to a position of the refer-back token in the token string, the refer-back token further indicating a length of the first substring within the token string, the refer-back token including a header that specifies a number of bits used to store the offset expressed by the position indicated by the refer-back token;

placing the first substring and the refer-back token into the token string, the token string allowing the second substring to be reconstructed by accessing the refer-back token, moving to the position in the token string that is indicated by the refer-back token, and reading an amount of data according to the length indicated by the refer-back token;

identifying a third substring in the at least one data string, the third substring comprising a plurality of characters that are the same as a plurality of characters of a fourth substring in the at least one data string;

generating a second refer-back token associated with the third substring, the second refer-back token indicating a position of the fourth substring within the token string, the position indicated by the second refer-back token expressed as an offset to a position of the second refer-back token in the token string, the second refer-back token further indicating a length of the fourth substring within the token string, the second refer-back token including a second header that specifies a second number of bits used to store the offset expressed by the position indicated by the second refer-back token, the second number of bits different from the first number of bits; and

placing the fourth substring and the second refer-back token into the token string, the token string allowing the third substring to be reconstructed by accessing the second refer-back token, moving to the position in the token string that is indicated by the second refer-back token, and reading an amount of data according to the length indicated by the second refer-back token.

2. The method of claim 1, wherein:

the at least one 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 at least a portion of the token string is generated 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 first substring.

7. The method of claim 1, wherein the token string comprises a plurality of tokens and at least one token of the plurality of tokens 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;

identify a first substring in the at least one data string, the first substring comprising a plurality of characters that are the same as a plurality of characters of a second substring in the at least one data string;

generate a refer-back token associated with the second substring, the refer-back token indicating a position of the first substring within a token string, the token string being a compressed version of at least a portion of the at least one data string, the position indicated by the refer-back token expressed as an offset to a position of the refer-back token in the token string, the refer-back token further indicating a length of the first substring within the token string, the refer-back token including a header that specifies a number of bits used to store the offset expressed by the position indicated by the refer-back token;

place the first substring and the refer-back token into the token string, the token string allowing the second substring to be reconstructed by accessing the refer-back token, moving to the position in the token string that is indicated by the refer-back token, and reading an amount of data according to the length indicated by the refer-back token;

identify a third substring in the at least one data string, the third substring comprising a plurality of characters that are the same as a plurality of characters of a fourth substring in the at least one data string;

generate a second refer-back token associated with the third substring, the second refer-back token indicating a position of the fourth substring within the token string, the position indicated by the second refer-back token expressed as an offset to a position of the second refer-back token in the token string, the second refer-back token further indicating a length of the fourth substring within the token string, the second refer-back token including a second header that specifies a second number of bits used to store the offset expressed by the position indicated by the second refer-back token, the second number of bits different from the first number of bits; and

place the fourth substring and the second refer-back token into the token string, the token string allowing the third substring to be reconstructed by accessing the second refer-back token, moving to the position in the token string that is indicated by the second refer-back token, and reading an amount of data according to the length indicated by the second refer-back token.

9. The system of claim 8, wherein:

the at least one 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 at least a portion of 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 first substring.

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

15. Non-transitory computer readable media comprising logic, the logic being operable, when executed by a processor, to:

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

identify a first substring in the at least one data string, the first substring comprising a plurality of characters that are the same as a plurality of characters of a second substring in the at least one data string;

generate a refer-back token associated with the second substring, the refer-back token indicating a position of the first substring within a token string, the token string being a compressed version of at least a portion of the at least one data string, the position indicated by the refer-back token expressed as an offset to a position of the refer-back token in the token string, the refer-back token further indicating a length of the first substring within the token string, the refer-back token including a header that specifies a number of bits used to store the offset expressed by the position indicated by the refer-back token;

place the first substring and the refer-back token into the token string, the token string allowing the second substring to be reconstructed by accessing the refer-back token, moving to the position in the token string that is indicated by the refer-back token, and reading an amount of data according to the length indicated by the refer-back token;

identify a third substring in the at least one data string, the third substring comprising a plurality of characters that are the same as a plurality of characters of a fourth substring in the at least one data string;

generate a second refer-back token associated with the third substring, the second refer-back token indicating a position of the fourth substring within the token string, the position indicated by the second refer-back token expressed as an offset to a position of the second refer-back token in the token string, the second refer-back token further indicating a length of the fourth substring within the token string, the second refer-back token including a second header that specifies a second number of bits used to store the offset expressed by the position indicated by the second refer-back token, the second number of bits different from the first number of bits; and

place the fourth substring and the second refer-back token into the token string, the token string allowing the third substring to be reconstructed by accessing the second refer-back token, moving to the position in the token string that is indicated by the second refer-back token, and reading an amount of data according to the length indicated by the second refer-back token.

16. The non-transitory computer readable media of claim 15, wherein:

the at least one 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 non-transitory computer readable media of claim 15, wherein the logic is further operable to generate at least a portion of the token string using Run Length Encoding (RLE).

18. The non-transitory computer readable media of claim 15, wherein the logic is further operable to store the token string.

19. The non-transitory computer readable media 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 non-transitory computer readable media of claim 15, wherein the logic is further operable to store the first substring.