Compressing log files

• US 7,224,297 B2
• Filed: 11/02/2005
• Issued: 05/29/2007
• Est. Priority Date: 11/02/2005
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Lycos Incorporated (Brightcom Group Ltd.)
• Inventors: Trout, Jeffrey
• Primary Examiner(s): Barnie, Rexford
• Assistant Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US11/265,491
• Publication Number:
  US 20070096952A1
• Time in Patent Office: 573 Days
• Field of Search: 341/87, 341/50, 375/361, 709/224
• US Class Current: 341/87
• 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

Data is compressed, which includes first through sixth patterns having respective first through sixth values, where the first pattern precedes the second pattern in the data, the third pattern precedes the fourth pattern in the data, and the fifth pattern precedes the sixth pattern in the data. Compression includes outputting a first code and the second value if the second value exceeds the first value by more than a predetermined amount, outputting a second code and a difference between the third and fourth values if the fourth value does not exceed the third value by more than the predetermined amount, and outputting the fifth value and the sixth value if the sixth value exceeds the fifth value by a predefined number.

Claims

1. A method of compressing data comprised of first through sixth patterns having respective first through sixth values, where the first pattern precedes the second pattern in the data, the third pattern precedes the fourth pattern in the data, and the fifth pattern precedes the sixth pattern in the data, the method comprising:

providing first compressed data comprising a first code and the second value if the second value exceeds the first value by more than a predetermined amount;

providing second compressed data comprising a second code and a difference between the third and fourth values if the fourth value does not exceed the third value by more than the predetermined amount;

providing third compressed data comprising the fifth value and the sixth value if the sixth value exceeds the fifth value by a predefined number; and

storing, in memory, at least one of the first compressed data, the second compressed data, and the third compressed data.

2. The method of claim 1, further comprising:

scanning the data for a pattern that repeats; and

replacing the pattern that repeats with a run-length value.

3. The method of claim 1, wherein the data comprises a string comprised of the first through sixth patterns;

and

wherein the first and second patterns are adjacent in the string, the third and fourth patterns are adjacent in the string, and the fifth and sixth patterns are adjacent in the string.

4. The method of claim 1, wherein the data comprises date information that is part of a log file of a Web server.

5. The method of claim 1, further comprising:

providing the second code and a difference between the first and second values if the second value does not exceed the first value by more than the predetermined amount; and

providing the first code and the third value if the fourth value exceeds the third value by more than the predetermined amount.

6. A method of compressing data comprised of a sequence of data strings, the method comprising:

providing first compressed data comprising a first code for a first data string that occurs more than once in the data;

providing second compressed data comprising a second code and a corresponding second string identifier for a second data string in the data, the second string identifier being predefined;

providing third compressed data comprising a third code, a corresponding third string length, and a corresponding third string identifier for a third data string in the data;

providing fourth compressed data comprising a fourth code and a corresponding fourth run length value for a fourth data string that occurs repeatedly in the data, the fourth run length value corresponding to a number of consecutive repetitions of the fourth data string; and

storing, in memory, at least one of the first compressed data, the second compressed data, the third compressed data, and the fourth compressed data.

7. The method of claim 6, further comprising:

providing, along with the first code, a corresponding first run length value for the first data string, the first run length value corresponding to a number of consecutive repetitions of the first data string.

8. The method of claim 6, further comprising:

identifying the first data string in the data; and

storing the first code;

wherein providing the first compressed data comprises encountering the first data string and retrieving the first code for output.

9. The method of claim 6, wherein the first code is stored in a table that indexes the first code to the first data string.

10. A method of compressing data, the method comprising:

storing compression rules in association with corresponding user request identifiers (URIs), wherein different URIs are associated with one or more arguments having different structures, and each compression rule is associated with a URI and is for compressing at least one argument having a fixed structure that is associated with the URI

receiving an input argument, the input argument corresponding to a URI;

identifying a stored compression rule by matching the URI of the input argument to the URI of the stored compression rule;

compressing the input argument according to the stored compression rule to produce a compressed input argument; and

storing the compressed input argument in memory.

11. One or more machine-readable media for storing instructions to compress data comprised of first through sixth patterns having respective first through sixth values, where the first pattern precedes the second pattern in the data, the third pattern precedes the fourth pattern in the data, and the fifth pattern precedes the sixth pattern in the data, the instructions for causing one or more processing devices to:

provide first compressed data comprising a first code and the second value if the second value exceeds the first value by more than a predetermined amount;

provide second compressed data comprising a second code and a difference between the third and fourth values if the fourth value does not exceed the third value by more than the predetermined amount;

provide third compressed data comprising the fifth value and the sixth value if the sixth value exceeds the fifth value by a predefined number; and

store, in memory, at least one of the first compressed data, the second compressed data, and the third compressed data.

12. The one or more machine-readable media of claim 11, further comprising instructions that cause the one or more processing devices to:

scan the data for a pattern that repeats; and

replace the pattern that repeats with a run-length value.

13. The one or more machine-readable media of claim 11, wherein the data comprises a string comprised of the first through sixth patterns;

and

wherein the first and second patterns are adjacent in the string, the third and fourth patterns are adjacent in the string, and the fifth and sixth patterns are adjacent in the string.

14. The one or more machine-readable media of claim 11, wherein the data comprises date information that is part of a log file of a Web server.

15. The one or more machine-readable media of claim 11, further comprising instructions that cause the one or more processing devices to:

provide the second code and a difference between the first and second values if the second value does not exceed the first value by more than the predetermined amount; and

provide the first code and the third value if the fourth value exceeds the third value by more than the predetermined amount.

16. One or more machine-readable media for storing instructions to compress data comprised of a sequence of data strings, the instructions for causing one or more processing devices to:

provide first compressed data comprising a first code for a first data string that occurs more than once in the data;

provide second compressed data comprising a second code and a corresponding second string identifier for a second data string in the data, the second string identifier being predefined;

provide third compressed data comprising a third code, a corresponding third string length, and a corresponding third string identifier for a third data string in the data;

provide fourth compressed data comprising a fourth code and a corresponding fourth run length value for a fourth data string that occurs repeatedly in the data, the fourth run length value corresponding to a number of consecutive repetitions of the fourth data string; and

store, in memory, at least one of the first compressed data, the second compressed data, the third compressed data, and the fourth compressed data.

17. The one or more machine-readable media of claim 16, further comprising instructions that cause the one or more processing devices to:

provide, along with the first code, a corresponding first run length value for the first data string, the first run length value corresponding to a number of consecutive repetitions of the first data string.

18. The one or more machine-readable media of claim 16, further comprising instructions that cause the one or more processing devices to:

identify the first data string in the data; and

store the first code;

wherein providing the first compressed data comprises encountering the first data string and retrieving the first code for output.

19. The one or more machine-readable media of claim 16, wherein the first code is stored in a table that indexes the first code to the first data string.

20. One or more machine-readable media for storing instructions to compress data, the instructions for causing one or more processing devices to:

store compression rules in association with corresponding user request identifiers (URIs), wherein different URIs are associated with one or more arguments having different fixed structures, and each compression rule is associated with a URI and is for compressing at least one argument having a fixed structure that is associated with the URI;

receive an input argument, the input argument corresponding to a URI;

identify a stored compression rule by matching the URI of the input argument to the URI of the stored compression rule;

compress the input argument according to the stored compression rule to produce a compressed input argument; and

store the compressed input argument in memory.