关键词: 拼写纠错, 查询补全, 期望最大化算法, N语法语言模型

Abstract: In search engines, online spelling correction aims to provide spell corrected completion suggestions as a query is incrementally entered. In this paper, a novel online spelling correction algorithm for query completion is proposed. Based on a noisy channel transformation of the intended queries, a generative model for input queries is presented. Utilizing spelling correction pairs, a Markov n-gram transformation model that captures user spelling behavior is trained by the Expectation-Maximization （EM） algorithm. To find the top spell-corrected completion suggestions in real-time, the proposed algorithm adopts an improved A* search algorithm with various pruning heuristics to dynamically expand the search space efficiently. Evaluation of the proposed methods demonstrates a substantial increase in the effectiveness of online spelling correction over existing techniques.

Key words: spelling correction, query completion, expectation-maximization, N-gram language model