A Graph Approach to Spelling Correction in Domain-Centric Search

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 905–914, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics A Graph Approach to Spelling Correction in Domain-Centric Search Zhuowei Bao University of Pennsylvania Philadelphia, PA 19104, USA zhuowei@cis.upenn.edu Benny Kimelfeld IBM Research–Almaden San Jose, CA 95120, USA kimelfeld@us.ibm.com Yunyao Li IBM Research–Almaden San Jose, CA 95120, USA yunyaoli@us.ibm.com Abstract Spelling correction for keyword-search queries is challenging in restricted domains such as personal email (or desktop) search, due to the scarcity of query logs, and due to the specialized nature of the domain. For that task, this paper presents an algorithm that is based on statistics from the corpus data (rather than the query log). This algorithm, which employs a simple graph-based approach, can incorporate different types of data sources with different levels of reliability (e.g., email subject vs. email body), and can handle complex spelling errors like splitting and merging of words. An experimental study shows the superiority of the algorithm over existing alternatives in the email domain. 1 Introduction An abundance of applications require spelling cor- rection, which (at the high level) is the following task. The user intends to type a chunk q of text, but types instead the chunk s that contains spelling errors (which we discuss in detail later), due to un- careful typing or lack of knowledge of the exact spelling of q. The goal is to restore q, when given s. Spelling correction has been extensively studied in the literature, and we refer the reader to compre- hensive summaries of prior work (Peterson, 1980; Kukich, 1992; Jurafsky and Martin, 2000; Mitton, 2010). The focus of this paper is on the special case where q is a search query, and where s instead of q is submitted to a search engine (with the goal of re- trieving documents that match the search query q). Spelling correction for search queries is important, because a significant portion of posed queries may be misspelled (Cucerzan and Brill, 2004). Effective spelling correction has a major effect on the expe- rience and effort of the user, who is otherwise re- quired to ensure the exact spellings of her queries. Furthermore, it is critical when the exact spelling is unknown (e.g., person names like Schwarzenegger). 1.1 Spelling Errors The more common and studied type of spelling error is word-to-word error: a single word w is misspelled into another single word w′. The specific spelling er- rors involved include omission of a character (e.g., atachment), inclusion of a redundant character (e.g., attachement), and replacement of charac- ters (e.g., attachemnt). The fact that w′ is a mis- spelling of (and should be corrected to) w is denoted by w′ → w (e.g., atachment → attachment). Additional common spelling errors are splitting of a word, and merging two (or more) words: • attach ment → attachment • emailattachment → email attachment Part of our experiments, as well as most of our examples, are from the domain of (personal) email …

Content truncated to 500 words