COMPRESSION RATIO FOR A COMPRESSION ENGINE

摘要

An output sequence of data elements is processed. The output sequence of data elements represents a sequence of input data elements in a compressed format. An output data element comprises a backward reference for each string in the input data elements that occurs again in an input data element that is used to produce the output data element. A backward reference identified in a selected output data element is used for selecting the string to which it refers in the stored input data elements. The selected string is combined with strings of one or more subsequent output data elements. A matching sequence in the stored input data elements matching at least part of one or more combined strings is found. A combined string of the one or more combined strings having the longest matching sequence is selected. The backward reference is redefined to indicate the longest matching sequence.

主权项

1. A method of processing an output sequence of data elements in a data processing system, the output sequence of data elements representing a sequence of input data elements in a compressed format, wherein an output data element comprises a backward reference for each string in the input data elements that occurs again in an input data element that is used to produce the output data element, wherein the input data elements are stored in a history buffer, the method comprising:
a. identifying by an extended matcher of the data processing system the backward reference in a selected output data element; b. using by the extended matcher the identified backward reference for selecting a string to which it refers in the stored input data elements; c. combining by the extended matcher the selected string with strings of one or more subsequent output data elements to the selected output data element for forming one or more combined strings; d. finding by the extended matcher a matching sequence in the stored input data elements matching at least part of the one or more combined strings, and selecting a combined string of the one or more combined strings having a longest matching sequence; and e. redefining by the extended matcher the backward reference to indicate the longest matching sequence, thereby generating a redefined output data element.