A Fast and Accurate Method for Approximate String Search

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 52–61, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics A Fast and Accurate Method for Approximate String Search Ziqi Wang∗ School of EECS Peking University Beijing 100871, China wangziqi@pku.edu.cn Gu Xu Microsoft Research Asia Building 2, No.5 Danling Street, Beijing 100080, China guxu@microsoft.com Hang Li Microsoft Research Asia Building 2, No.5 Danling Street, Beijing 100080, China hangli@microsoft.com Ming Zhang School of EECS Peking University Beijing 100871, China mzhang@net.pku.edu.cn Abstract This paper proposes a new method for ap- proximate string search, specifically candidate generation in spelling error correction, which is a task as follows. Given a misspelled word, the system finds words in a dictionary, which are most “similar” to the misspelled word. The paper proposes a probabilistic approach to the task, which is both accurate and efficient. The approach includes the use of a log linear model, a method for training the model, and an algorithm for finding the top k candidates. The log linear model is defined as a condi- tional probability distribution of a corrected word and a rule set for the correction con- ditioned on the misspelled word. The learn- ing method employs the criterion in candidate generation as loss function. The retrieval al- gorithm is efficient and is guaranteed to find the optimal k candidates. Experimental re- sults on large scale data show that the pro- posed approach improves upon existing meth- ods in terms of accuracy in different settings. 1 Introduction This paper addresses the following problem, re- ferred to as approximate string search. Given a query string, a dictionary of strings (vocabulary), and a set of operators, the system returns the top k strings in the dictionary that can be transformed from the query string by applying several operators in the operator set. Here each operator is a rule that can replace a substring in the query string with another substring. The top k results are defined in ∗ Contribution during internship at Microsoft Research Asia. terms of an evaluation measure employed in a spe- cific application. The requirement is that the task must be conducted very efficiently. Approximate string search is useful in many ap- plications including spelling error correction, sim- ilar terminology retrieval, duplicate detection, etc. Although certain progress has been made for ad- dressing the problem, further investigation on the task is still necessary, particularly from the view- point of enhancing both accuracy and efficiency. Without loss of generality, in this paper we ad- dress candidate generation in spelling error correc- tion. Candidate generation is to find the most pos- sible corrections of a misspelled word. In such a problem, strings are words, and the operators rep- resent insertion, deletion, and substitution of char- acters with or without surrounding characters, for example, “a”→“e” and “lly”→“ly”. Note that can- didate generation is concerned with a single word; after candidate generation, the words surrounding it in the text can be further leveraged to make the final candidate selection, …

Content truncated to 500 words