String searcher, and compressor using same
US5051745A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Aug 21, 1990 |
| Grant date | Sep 24, 1991 |
| Priority date | — |
| Expiry date | Aug 21, 2010 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/3086
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
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…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.