document: Online spelling correction for query completion In this paper , we study the problem of online spelling correction for query completions . Misspelling is a common phenomenon among search engines queries . In order to help users effectively express their information needs , mechanisms for automatically correcting misspelled queries are required . Online spelling correction aims to provide spell corrected completion suggestions as a query is incrementally entered . As latency is crucial to the utility of the suggestions , such an algorithm needs to be not only accurate , but also efficient . To tackle this problem , we propose and study a generative model for input queries , based on a noisy channel transformation of the intended queries . Utilizing spelling correction pairs , we train a Markov n-gram transformation model that captures user spelling behavior in an unsupervised fashion . To find the top spell-corrected completion suggestions in real-time , we adapt the 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 .
doc_bio_tags: O B I O B I O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O