Efficient Large-Scale Clustering of Spelling Variants, with Applications to Error-Tolerant Text Search
Marjan Celikik, Gerhard Weikum, Holger Bast · Max Planck Digital Library · 2007
In this thesis, the following spelling variants clustering problem is considered: Given a list of distinct words, called lexicon, compute (possibly overlapping) clusters of words which are spelling variants of each other. We are looking for algorithms that are both efficient and accurate. Accuracy is measured with respect to human judgment, e.g., a cluster is 100 accurate if it contains all true spelling variants of the unique correct word it contains and no other words, as judged by a human. We have sifted the large body of literature on approximate string searching and spelling correction problem for its applicability to our problem. We have combined various ideas from previous approaches to two new algorithms, with two distinctly different trade-offs between efficiency and accuracy. We have analyzed both algorithms and tested them experimentally on a variety of test collections, which were chosen to exhibit the whole spectrum of spelling errors as they occur in practice (human-made, OCR-induced, garbage). Our largest lexicon, containing roughly 25 million words, can be processed in half an hour on a single machine. The accuracies we obtain range from 88 - 95. We show that previous approaches, if directly applied to our problem, are either significantly slower or significantly less accurate or both. Our spelling variants clustering problem arises naturally in the context of search engine spelling correction of the following kind: For a given query, return not only documents matching the query words exactly but also those matching their spelling variants. This is inverse to the well-known �did you mean: ...� web search engine feature, where the error tolerance is on the side of the query, and not on the side of the documents. We have integrated our algorithms with the CompleteSearch engine, and show that this feature can be achieved without significant blowup in either index size or query processing time.