05051745 is referenced by 158 patents and cites 3 patents.

Methods and apparatus for string searching and data compression. In the string search method and apparatus pointers to the string to be searched are indexed via a hashing function and organized according to the hashing values of the string elements pointed to. The hashing function is also run on the string desired to be found, and the resulting hashing value is used to access the index. If the resulting hashing value is not in the index, it is known that the target string does not appear in the string being searched. Otherwise the index is used to determine the pointers which correspond to the target hashing value, these pointers pointing to likely candidates for matching the target string. The pointers are then used to sequentially compare each of the locations in the string being searched to the target string, to determine whether each location contains a match to the target string. In the method and apparatus for compressing a stream of data symbols, a fixed length search window, comprising a predetermined contiguous portion of the symbol stream, is selected as the string to be searched by the string searcher. If a string to be compressed is found in the symbol stream, a code is output designating the location within the search window of the matching string and the length of the matching string.

String searcher, and compressor using same
Application Number
Publication Number
Application Date
August 21, 1990
Publication Date
September 24, 1991
Phillip W Katz
Fuller Ryan & Hohenfeldt
G06F 15/40
H03M 7/30
View Original Source