RECURSIVE HASHING FUNCTIONS FOR N-GRAMS

Many indexing, retrieval, and comparison methods are based on counting or cataloguing n-grams in streams of symbols. The fastest method of i mplementing such operations is through the use of hash tables. Rapid h ashing of consecutive n-grams is best done using a recursive hash func tion, in which the hash value of the current n-gram is derived from th e hash value of its predecessor. This article generalizes recursive ha sh functions found in the literature and proposes new methods offering superior performance. Experimental results demonstrate substantial sp eed improvement over conventional approaches, while retaining near-ide al hash value distribution.