DATA COMPRESSION UTILIZING LONGEST COMMON SUBSEQUENCE TEMPLATE

• US 20140049413A1
• Filed: 02/28/2013
• Published: 02/20/2014
• Est. Priority Date: 08/16/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: AGARWAL, KANAK B., JAMSEK, DAMIR A., PAOLINI, MICHAEL A., TREMAINE, ROBERT B.
• Granted Patent: US 9,106,251 B2
• Time in Patent Office: Days
• US Class Current: 341/87
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/607 Selection between different types of compressors

Abstract

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.

Claims

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.