Premium
An n‐gram hash and skip algorithm for finding large numbers of keywords in continuous text streams
Author(s) -
Cohen Jonathan D.
Publication year - 1998
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.0.co;2-c
Subject(s) - byte , hash function , computer science , trie , n gram , sequence (biology) , hash table , algorithm , data stream , theoretical computer science , data mining , data structure , artificial intelligence , programming language , language model , biology , genetics , telecommunications
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. © 1998 John Wiley & Sons, Ltd.