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

Novel spelling correction algorithm for online query

作　　者：王秀珍[1] 丛瑞[1] 王飞[1] 

机构地区：[1]中国人民解放军陆军军官学院十一系计算机教研室,合肥230031

出　　处：《计算机工程与应用》2015年第14期113-119,共7页Computer Engineering and Applications

摘　　要：搜索引擎中,在线拼写纠错根据用户查询输入补全用户查询,并给出正确的拼写建议。提出了一种面向查询补全的在线拼写纠错算法。基于真实查询的噪声信道转换方式,算法建立了用户查询输入的生成模型;利用拼写纠错对,算法采用期望最大化算法训练能捕获用户误拼行为的马尔科夫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. 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.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]