An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams
✍ Scribed by Jonathan D. Cohen
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 407 KB
- Volume
- 28
- Category
- Article
- ISSN
- 0038-0644
No coin nor oath required. For personal study only.
✦ Synopsis
A method of full-text scanning for matches in a large dictionary of keywords is described, suitable for Selective Dissemination of Information (SDI). The method is applicable to large dictionaries (say 10 4 to 10 5 entries), and to arbitrary byte streams for both patterns and data samples. The approach involves a sequence of tests, beginning with Boyer-Moore-Horspool skipping on digrams, followed by a succession of hash tests, and completed by trie searching, the combination of which is quite fast. Background information is provided, the algorithm and its implementation are described in detail, and experimental results are presented. In particular, tests suggest that the proposed method outperforms the algorithms of Aho-Corasick and Commentz-Walter when implementing large dictionaries.