Symbol based data compression
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:
identifying, with a processor of an encoding device, a first symbol string that occurs within data to be compressed;
generating a first symbol string code indicative of one or more positions of the first symbol string within the data;
generating a symbol configured to indicate that there are no more occurrences of the first symbol string, wherein the symbol identifies at least one of a number of symbol strings to skip in an ordered list of symbol strings before generating a second symbol string code or the symbol identifies a position beyond a length of the data that corresponds to a first position of a second symbol string within the data; and
combining the first symbol string code with one or more additional symbol string codes to generate a compressed data code corresponding to the data.
2. The method of claim 1 , wherein the symbol strings to skip follow the first symbol string.
3. The method of claim 1 , wherein the symbol strings to skip precede the first symbol string.
4. The method of claim 1 , further comprising:
identifying a second symbol string to encode by skipping over the number of symbol strings to skip; and
generating a second symbol code indicative of one or more positions of the second symbol string, wherein the compressed data code includes a combination of at least the first symbol string code and the second symbol string code.
5. The method of claim 1 , further comprising determining one or more distances between one or more occurrences of the first symbol string, wherein the first symbol string code is based at least in part on the one or more distances.
6. The method of claim 1 , wherein the first symbol string code identifies one or more positions in the data where the first symbol string does not occur.
7. The method of claim 1 , wherein the compressed data code does not include one or more positions of a final symbol string.
8. The method of claim 1 , wherein the first symbol string comprises an initial symbol string of the data.
9. The method of claim 1 , wherein the first symbol string is identified based on a predetermined ordered list of symbol strings.
10. The method of claim 1 , wherein the symbol is part of the first symbol string.
11. The method of claim 1 , wherein the symbol comprises a second symbol string.
12. An apparatus comprising:
a memory; and
a processor operatively coupled to the memory and configured to:
identify a first symbol string that occurs within data to be compressed;
generate a first symbol string code indicative of one or more positions of the first symbol string within the data, wherein the first symbol string code includes a symbol configured to indicate that there are no more occurrences of the first symbol string, and wherein the symbol identifies at least one of a number of symbol strings to skip in an ordered list of symbol strings before generating a second symbol string code or the symbol identifies a position beyond a length of the data that corresponds to a first position of a second symbol string within the data; and
combine the first symbol string code with one or more additional symbol string codes to generate a compressed data code corresponding to the data.
13. The apparatus of claim 12 , wherein the ordered list of symbol strings is known to the apparatus and to a decoder in communication with the apparatus.
14. The apparatus of claim 12 , wherein the position beyond the length of the data wraps around the data one or more times to skip one or more symbol strings.
15. The apparatus of claim 12 , wherein the processor is further configured to determine one or more distances between one or more occurrences of the first symbol string, wherein the first symbol string code is based at least in part on the one or more distances.
16. The apparatus of claim 12 , further comprising a transmitter operatively coupled to the processor and configured to transmit the compressed data code to a decoder.
17. The apparatus of claim 12 , wherein the processor is further configured to identify the first symbol string based at least in part on a frequency of occurrence of the first symbol string.
18. The apparatus of claim 17 , wherein the frequency of occurrence is relative to the data.
19. The apparatus of claim 17 , wherein the frequency of occurrence is relative to usage of the first symbol string in a language.
20. An apparatus comprising:
means for identifying a first symbol string that occurs within data to be compressed;
means for generating a first symbol string code indicative of one or more positions of the first symbol string within the data;
means for generating a symbol configured to indicate that there are no more occurrences of the first symbol string in the data, wherein the symbol identifies at least one of a number of symbol strings to skin in an ordered list of symbol strings before generating a second symbol string code or the symbol identifies a position beyond a length of the data that corresponds to a first position of a second symbol string within the data; and
means for combining the first symbol string code with one or more additional symbol string codes to generate a compressed data code corresponding to the data.
21. The apparatus of claim 20 , further comprising means for transmitting the compressed data code to a decoder.
22. The apparatus of claim 20 , wherein the symbol indicates that a second symbol string is to be coded, and wherein the second symbol string is a subsequent symbol string in an ordered list of symbol strings.
23. The apparatus of claim 20 , further comprising means for determining one or more distances between one or more occurrences of the first symbol string, wherein the first symbol string code is based at least in part on the one or more distances.
24. A tangible computer-readable medium having stored thereon, computer-executable instructions that, if executed by a computing device, cause the computing device to perform a method comprising:
identifying a first symbol string that occurs within data to be compressed;
generating a first symbol string code indicative of one or more positions of the first symbol string within the data, wherein the first symbol string code includes a symbol configured to indicate that there are no more occurrences of the first symbol string, and wherein the symbol identifies at least one of a number of symbol strings to skip in an ordered list of symbol strings before generating a second symbol string code or the symbol identifies a position beyond a length of the data that corresponds to a first position of a second symbol string within the data: and
combining the first symbol string code with one or more additional symbol string codes to generate a compressed data code corresponding to the data.
25. The tangible computer-readable medium of claim 24 , further comprising identifying a second symbol string to encode by skipping over the number of symbol strings to skip.
26. The tangible computer-readable medium of claim 24 , wherein the symbol indicates that a second symbol string is to be coded, and wherein the second symbol string is a subsequent symbol string in an ordered list of symbol strings.
27. The tangible computer-readable medium of claim 24 , wherein the position beyond the length of the data wraps around the data one or more times to skip one or more symbol strings.
28. A method comprising:
receiving, at a decoding device having a processor, a compressed data code corresponding to data, wherein the compressed data code includes a plurality of symbol string codes corresponding to a plurality of symbol strings;
identifying, based on a first symbol string code of the plurality of symbol string codes, one or more positions of a first symbol string in the data; and
identifying a second symbol string to decode based at least in part on a symbol in the compressed data code, wherein the symbol is configured to indicate that there are no more occurrences of the first symbol string.
29. The method of claim 28 , wherein the symbol identifies a number of symbol strings to skip in an ordered list of symbol strings.
30. The method of claim 28 , wherein the symbol is part of the first symbol string code.
31. The method of claim 28 , further comprising identifying one or more positions of the second symbol string in the data based at least in part on a second symbol string code of the plurality of symbol string codes.
32. The method of claim 28 , wherein the symbol identifies a position beyond a length of the data, and wherein the position corresponds to a first position of the second symbol string within the data.
33. The method of claim 28 , wherein the first symbol string code is based at least in part on one or more distances between occurrences of the first symbol string within the data.
34. An apparatus comprising:
a receiver configured to receive a compressed data code corresponding to data, wherein the compressed data code includes a plurality of symbol string codes corresponding to a plurality of symbol strings; and
a processor operatively coupled to the receiver and configured to:
identify, based on a first symbol string code of the plurality of symbol string codes, one or more positions of a first symbol string in the data; and
identify a second symbol string to decode based at least in part on a symbol in the compressed data code, wherein the symbol is configured to at least indicate that there are no more occurrences of the first symbol string.
35. The apparatus of claim 34 , wherein the processor is further configured to identify one or more positions of the second symbol string in the data based at least in part on a second symbol string code of the plurality of symbol string codes.
36. The apparatus of claim 34 , wherein the symbol identifies a number of symbol strings to skip in an ordered list of symbol strings.
37. The apparatus of claim 36 , wherein the receiver is further configured to receive the ordered list of symbol strings.
38. The apparatus of claim 34 , wherein the symbol identifies a position beyond a length of the data, wherein the position corresponds to a first position of the second symbol string within the data.