Lempel-Ziv data compression with shortened hash chains based on repetitive patterns
View Patent ↗Methods and apparatus are provided for Lempel-Ziv data compression with shortened hash chains based on repetitive multi-byte runs. Data is compressed by processing a sequence of data to identify a repetitive pattern, such as a multi-byte run; and providing indicators associated with the sequence of data of a start position and an end position of the repetitive pattern. The indicators of the start and end positions of the repetitive pattern may comprise, for example, flags associated with the positions. The indicators of the start and end positions of the repetitive pattern are processed to determine a sequence length of the repetitive pattern. In addition, a match can be identified in the sequence of data having a length that is greater than or equal to an offset of s bytes to identify a run comprised of an s-byte sequence.
1. A method for compressing data, comprising the steps of:
processing a sequence of data to identify a repetitive patternin said sequence of: data; and
providing indicators associated with said sequence of data of a start position and an end position of said repetitive pattern.
2. The method of claim 1 , wherein said indicators of said start and end positions of said repetitive pattern comprise flags associated with said positions.
3. The method of claim 2 , wherein said flags comprise two bit values.
4. The method of claim 1 , further comprising the step of processing said indicators of said start and end positions of said repetitive pattern to determine a sequence length of said repetitive pattern.
5. The method of claim 1 , wherein said repetitive pattern comprises a multi-byte run.
6. The method of claim 1 , further comprising the step of identifying a match in said sequence of data having a length that is greater than or equal to an offset of s bytes to identify a run comprised of an s-byte sequence.
7. The method of claim 1 , further comprising the step of identifying a position in said sequence of data having an indicator indicating said end position of said repetitive pattern and skipping positions in said sequence of data until a position in said sequence of data is identified having an indicator indicating said start position of said repetitive pattern.
8. The method of claim 1 , further comprising the step of finishing a matching on a whole run when the match length exceeds a minimum and the match reaches out of the run.
9. The method of claim 1 , further comprising the steps of updating an offset so the matching end falls on a position with an indicator of an end position of said repetitive pattern and extending the match outside the run, when the match length exceeds a minimum and the match does not reach out of the run.
10. A tangible machine-readable recordable storage medium for compressing, data, wherein one or more software programs when executed by one or more processing devices implement the steps of the method of claim 1 .
11. A system for compressing data, comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to:
process a sequence of data to identify a repetitive pattern in said sequence of data; and
provide indicators associated with said sequence of data of a start position and an end position of said repetitive patterns.
12. The system of claim 11 , wherein said indicators of said start and end positions of said repetitive pattern comprise flags associated with said positions.
13. The system of claim 12 , wherein said flags comprise two bit values.
14. The system of claim 11 , wherein said at least one hardware device is further configured to process said indicators of said start and end positions of said repetitive pattern to determine a sequence length of said repetitive pattern.
15. The system of claim 11 , wherein said repetitive pattern comprises a multi-byte run.
16. The system of claim 11 , wherein said at least one hardware device is further configured to identify a match in said sequence of data having a length that is greater than or equal to an offset of s bytes to identify a run comprised of an s-byte sequence.
17. The system of claim 11 , wherein said at least one hardware device is further configured to identify a position in said sequence of data having an indicator indicating said end position of said repetitive pattern and skip positions in said sequence of data until a position in said sequence of data is identified having an indicator indicating said start position of said repetitive pattern.
18. The system of claim 11 , wherein said at least one hardware device is further configured to finish a matching on a whole run when the match length exceeds a minimum and the match reaches out of the run.
19. The system of claim 11 , wherein said at least one hardware device is further configured to update an offset so the matching end falls on a position with an indicator of an end position of said repetitive pattern and extend the match outside the run, when the match length exceeds a minimum and the match does not reach out of the run.
20. The system of claim 11 , wherein said compression comprises a Lempel-Ziv compression.