Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

article · Software Practice and Experience · 1998

An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams

Jonathan Cohen

Cited by 3Abstract and details only

Abstract

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 104 to 105 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.

Cite this paper

APA 7

Cohen, J. (1998). An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams. Software Practice and Experience, 28(15), 1605–1635. https://doi.org/10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.3.co;2-3

MLA 9

Cohen, Jonathan. “An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams.” Software Practice and Experience, vol. 28, no. 15, 1998, pp. 1605–35, https://doi.org/10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.3.co;2-3.

Chicago

Cohen, Jonathan. 1998. “An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams.” Software Practice and Experience 28 (15): 1605–35. https://doi.org/10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.3.co;2-3.

Harvard

Cohen, J. (1998) ‘An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams’, Software Practice and Experience, 28(15), pp. 1605–1635. Available at: https://doi.org/10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.3.co;2-3.

BibTeX
@article{cohen1998gram,
  title = {{An n-gram hash and skip algorithm for finding large numbers of keywords in continuous text streams}},
  author = {Cohen, Jonathan},
  journal = {Software Practice and Experience},
  volume = {28},
  number = {15},
  pages = {1605--1635},
  year = {1998},
  doi = {10.1002/(sici)1097-024x(19981225)28:15<1605::aid-spe217>3.3.co;2-3}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers