一种面向在线查询的拼写纠错算法

摘要

搜索引擎中，在线拼写纠错根据用户查询输入补全用户查询，并给出正确的拼写建议。提出了一种面向查询补全的在线拼写纠错算法。基于真实查询的噪声信道转换方式，算法建立了用户查询输入的生成模型；利用拼写纠错对，算法采用期望最大化算法训练能捕获用户误拼行为的马尔科夫N语法转换模型；算法采用不同剪枝策略的启发式改进A*搜索算法以实现实时给出纠错补全建议。实验结果表明，提出的算法相比其他同类算法更有效。%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. Utiliz-ing 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 pro-posed 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.