Data compression for communication between two or more components in a system
View Patent ↗Briefly, within a computer or digital data processing system, embodiments describe a method, article and apparatus for compressing data is described, which may be used for communicating between two or more components connected to an interconnection medium (e.g., a bus) within a single computer or digital data processing system, and/or for communicating between two or more computers or digital data processing systems via an interconnection medium such as a network.
1. A method comprising:
generating a first symbol string code indicative of one or more first positions of a first symbol string within data to be compressed;
generating a second symbol string code indicative of one or more second positions of a second symbol string within the data, wherein a first position of the second symbol string is determined based at least in part upon a length of the data and the first symbol string code; and
combining the first symbol string code and the second symbol string code into a compressed data code.
2. The method of claim 1 , wherein the first position of the second symbol string is determined by subtracting the length of the data from an end position indicated by the first symbol string code.
3. The method of claim 1 , wherein the second symbol string is identified by repeatedly subtracting the length of the data from an end position indicated by the first symbol string code until a current position is within the length of the data.
4. The method of claim 1 , wherein the length of the data comprises a total length of a data grouping that includes the data.
5. The method of claim 1 , wherein the length of the data comprises a number of positions in the data which are not yet coded.
6. The method of claim 1 , further comprising using run length coding to code the one or more second positions of the second symbol string.
7. The method of claim 6 , wherein the run length coding comprises adaptive coding.
8. The method of claim 1 , wherein the first symbol string and the second symbol string are coded in a predetermined order.
9. The method of claim 1 , wherein the first symbol string code and the second symbol string code are stored or transmitted across a communications channel.
10. The method of claim 1 , wherein the first symbol string includes repetitions of a symbol or a string, and further wherein the first symbol string code identifies a run of occurrences of said symbol or said string.
11. The method of claim 10 , further comprising determining distances between occurrences of the first symbol string, wherein the first symbol string code identifies the one or more first positions of the first symbol string based at least in part on the determined distances.
12. The method of claim 1 , wherein, in addition to the one or more first positions, the first symbol string code includes additional information corresponding to the first symbol string.
13. The method of claim 1 , wherein the first symbol string data code includes the length of the data.
14. The method of claim 1 , wherein the first symbol string code identifies one or more third positions where the first symbol string does not occur within the data.
15. The method of claim 1 , wherein the length of the data to be compressed is predetermined and prefixed to the first symbol string code.
16. The method of claim 1 , wherein the one or more positions of the first symbol string within the compressed data code are determined without transmission or storage of additional information corresponding to the first symbol string.
17. A computer-readable medium having stored thereon computer-readable instructions that, if executed, cause a computing device to:
generate a first symbol string code indicative of one or more first positions of a first symbol string within data to be compressed;
generate a second symbol string code indicative of one or more second positions of a second symbol string within the data, wherein a first position of the second symbol string is determined based at least in part upon a length of the data and the first symbol string code; and
combine the first symbol string code and the second symbol string code into a compressed data code.
18. The computer-readable medium of claim 17 , wherein said computer-readable instructions, if executed, further cause the computing device to subtract the length of the data from an end position of the first symbol string code to identify the first position of the second symbol string.
19. The computer-readable medium of claim 17 , wherein said computer-readable instructions, if executed, further cause the computing device to repeatedly subtract the length of the data from an end position of the first symbol string code to determine at least a portion of the second symbol string code.
20. The computer-readable medium of claim 17 , wherein the length of the data comprises a total length of a grouping in which the data is included.
21. The computer-readable medium of claim 17 , wherein the length of the data comprises a number of positions in the data which are not yet coded.
22. The computer-readable medium of claim 17 , wherein the one or more first positions of the first symbol string are run length coded.
23. The computer-readable medium of claim 17 , wherein said computer-readable instructions, if executed, further cause the computing device to transmit the compressed data code across a communications channel.
24. The computer-readable medium of claim 17 , wherein said computer-readable instructions, if executed, further cause the computing device to determine distances between occurrences of the first symbol string, wherein the first symbol string code is based at least in part on the distances.
25. An apparatus comprising:
means for generating a first symbol string code indicative of one or more first positions of a first symbol string within data to be compressed;
means for generating a second symbol string code indicative of one or more second positions of a second symbol string within the data, wherein a first position of the second symbol string is determined based at least in part upon a length of the data and the first symbol string code; and
means for combining the first symbol string code and the second symbol string code into a compressed data code.
26. The apparatus of claim 25 , wherein the first position of the second symbol string is determined by subtracting the length of the data from an end position of the first symbol string code.
27. The apparatus of claim 25 , wherein the first position of the second symbol string is determined by repeatedly subtracting the length of the data from an end position of the first symbol string code until a current position is brought back within the length of the data.
28. The apparatus of claim 25 , wherein the length of the data comprises a total length of a data grouping that includes the data.
29. The apparatus of claim 25 , wherein the length of the data comprises a number of positions in the data which are not yet coded.
30. An apparatus comprising:
a computing platform, said computing platform being configured to generate a first symbol string code indicative of one or more first positions of a first symbol string within data to be compressed;
generate a second symbol string code indicative of one or more second positions of a second symbol string within the data, wherein a first position of the second symbol string is determined based at least in part upon a length of the data and an end position of the first symbol string code; and
combine the first symbol string code and the second symbol string code into a compressed data code.
31. The apparatus of claim 30 , wherein said computing platform is further configured to run length code the one or more second positions of the second symbol string.
32. The apparatus of claim 30 , wherein the first position of the second symbol string is determined by subtracting the length of the data from the end position of the first symbol string code to bring a current position back within the length of the data.
33. The apparatus of claim 30 , wherein the first position of the second symbol string is determined by subtracting the length of the data from the end position repeatedly until a current position is brought back within the length of the data.
34. The apparatus of claim 30 , wherein the length of the data comprises a total length of a grouping which includes the data.
35. The apparatus of claim 30 , wherein the length of the data comprises a number of positions in the data which are not yet coded.
36. A method comprising:
generating a first symbol string code indicative of one or more first positions of a first symbol string within data to be compressed;
generating a second symbol string code if an end position of the first symbol string code is beyond a length of the data, wherein a first position of the second symbol string code is based at least in part on a number of positions of the end position beyond the length of the data; and
combining the first symbol string code and the second symbol string code into a compressed data code.
37. An apparatus comprising:
a computing platform, said computing platform being configured to read data that has been compressed by a method comprising
generating a first symbol string code indicative of one or more first positions of a first symbol string within the data to be compressed;
generating a second symbol string code indicative of one or more second positions of a second symbol string within the data, wherein a first position of the second symbol string is based at least in part on a length of the data and the first symbol string code; and
combining the first symbol string code and the second symbol string code into a compressed data code.