Knuth (1997) is a comprehensive source for information on search trees, including B-trees and their use in searching through dictionaries.
Garfield (1976) gives one of the first complete descriptions of the permuterm index. Ferragina and Venturini (2007) give an approach to addressing the space blowup in permuterm indexes.
One of the earliest formal treatments of spelling correction
was due to Damerau (1964). The notion of edit distance that
we have used is due to Levenshtein (1965) and the
algorithm in Figure 3.5 is due to Wagner and Fischer (1974). Peterson (1980)
and Kukich (1992) developed variants of methods based on
edit distances, culminating in a detailed empirical study of
several methods by Zobel and Dart (1995), which shows that
-gram indexing is very effective for finding candidate
mismatches, but should be combined with a more fine-grained
technique such as edit distance to determine the most likely
misspellings. Gusfield (1997) is a standard
reference on string algorithms such as edit distance.
Probabilistic models (``noisy channel'' models) for spelling correction were pioneered by Kernighan et al. (1990) and further developed by Brill and Moore (2000) and Toutanova and Moore (2002). In these models, the mis-spelled query is viewed as a probabilistic corruption of a correct query. They have a similar mathematical basis to the language model methods presented in Chapter 12 , and also provide ways of incorporating phonetic similarity, closeness on the keyboard, and data from the actual spelling mistakes of users. Many would regard them as the state-of-the-art approach. Cucerzan and Brill (2004) show how this work can be extended to learning spelling correction models based on query reformulations in search engine logs.
The soundex algorithm is attributed to Margaret K. Odell and Robert C. Russelli (from U.S. patents granted in 1918 and 1922); the version described here draws on Bourne and Ford (1961). Zobel and Dart (1996) evaluate various phonetic matching algorithms, finding that a variant of the soundex algorithm performs poorly for general spelling correction, but that other algorithms based on the phonetic similarity of term pronunciations perform well.