Hardware-assisted algorithm for full-text large-dictionary string matching using n-gram hashing

摘要

A method of full-text scanning for matches in a large dictionary is described. The method is suitable for SDI (selective dissemination of information) systems, accommodating large dictionaries (104–105 entries) and typical digital data rates (tens of megabytes per second or more). It can be implemented on a single commercially-available board hosted by a personal computer or entirely in software. The preferred approach employs a hardware primary test, followed by a software secondary test. The algorithm is described in detail, the implementation is sketched, and simulation results are presented.