Method and apparatus for locating longest prior target string matching current string in buffer

摘要

An apparatus and method are disclosed for finding a target string in a history buffer, where the found target string matches a given current string to a maximum practical length. A presorted array of array entries (SP) is defined where each entry uniquely identifies a value and a location of a respective string-start byte pair in the history buffer. The array entries are sorted primarily upon their string-start byte-pair values and secondarily upon their pointed-to locations. A direct lookup table (DLT) is further provided, indexable by each possible string-start byte pair that may appear in the history buffer. The DLT is used to locate a first array entry for a given string-start byte pair. To find a longest matching target string, the first two bytes of the current string are used as an index into the direct lookup table, and the given table entry is then used as an index into the pre-sorted SP array. The corresponding array entry is used as an index to a first target string in the buffer. Each subsequent array entry having the same string-start byte pair value is used to locate a next target string. A longest matching string is determined from among the target strings pointed to by the SP array. The location and length of the longest matching string are returned as a result.