Data compression utilizing longest common subsequence template
In response to receipt of an input string, an attempt is made to identify, in a template store, a closely matching template for use as a compression template. In response to identification of a closely matching template that can be used as a compression template, the input string is compressed into a compressed string by reference to a longest common subsequence compression template. Compressing the input string includes encoding, in a compressed string, an identifier of the compression template, encoding substrings of the input string not having commonality with the compression template of at least a predetermined length as literals, and encoding substrings of the input string having commonality with the compression template of at least the predetermined length as a jump distance without reference to a base location in the compression template. The compressed string is then output.
1. A method of data processing system in a data processing system, comprising:
in response to receipt of an input string, an integrated circuit attempting to identify, in a template store, a closely matching template for use as a compression template;
in response to identification of the closely matching template as the compression template, the integrated circuit compressing the input string into a compressed string by reference to a compression template, wherein the compressing includes:
encoding, in a compressed string, an identifier of the compression template;
encoding, in the compressed string, first substrings of the input string not having commonality with the compression template of at least a predetermined length as literals;
in response to identifying first substrings, encoding, in the compressed string, jump lengths in the compression template until a next match between the input string and the compression template;
encoding, in the compressed string, second substrings of the input string having commonality with the compression template of at least the predetermined length as a template reference without reference to a base location in the compression template; and
outputting the compressed string.
2. The method of claim 1 , and further comprising building the compression template from a longest common subsequence of a plurality of sample messages.
3. The method of claim 1 , and further comprising:
in response to a failure to identify a closely matching template in the template store, outputting the string uncompressed.
4. The method of claim 3 , and further comprising:
in response to a failure to identify a closely matching template in the template store, adding a new template generated from the input string to the template store.
5. The method of claim 1 , wherein the input string comprises a text message.
6. The method of claim 1 , and further comprising:
in parallel with the compressing, applying a plurality of diverse lossless compression techniques to the input string to obtain a plurality of compressed strings including the compressed string, wherein the plurality of diverse lossless compression techniques include a non-template-based compression technique;
selecting a most compressed string among the plurality of compressed strings;
determining whether or not the most compressed string was obtained by template-based compression; and
in response to determining that the most compressed string was obtained by template-based compression, recompressing the most compressed string utilizing the non-template-based compression technique to obtain an output string and outputting the output string.
7. The method of claim 1 , and further comprising receiving and decoding the output string, wherein the decoding includes:
accessing the compression template identified in the compressed string; and
until an end of the compressed string is reached, repeatedly performing:
determining whether a next code in the compressed string is a literal, a jump code or a reference code; and
in response to determining the next code is a literal, inserting the code in a decompressed string;
in response to determining the next code is a jump code, advancing in the compression template a length specified by the jump code; and
in response to determining the next code is a reference code, inserting in the decompressed string a next consecutive substring from the compression template of a length specified by the reference code; and
outputting the decompressed string.
8. A method of data processing, the method comprising:
in response to receiving a compressed string, an integrated circuit decoding the compressed string, wherein the decoding includes:
accessing a compression template identified in the compressed string; and
until an end of the compressed string is reached, repeatedly performing:
determining whether a next code in the compressed string is a literal, a jump code or a reference code; and
in response to determining the next code is a literal, inserting the code in a decompressed string;
in response to determining the next code is a jump code, advancing in the compression template a length specified by the jump code; and
in response to determining the next code is a reference code, inserting in the decompressed string a next consecutive substring from the compression template of a length specified by the reference code; and
outputting the decompressed string.