Novel spelling correction algorithm for online query
Xiuzhe Wang · Computer Engineering and Applications Journal · 2015
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.