A Fast Correction Method for Erroneous Sentences Using the LR Parsing

Masami SHISHIBORI  Kazuaki ANDO  Yuuichirou KASHIWAGI  Jun-ichi AOE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.9   pp.1797-1804
Publication Date: 2000/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Natural Language Processing
Keyword: 
error correction,  error recovery,  LR parsing,  natural language processing,  descendant set table,  

Full Text: PDF(309.8KB)>>
Buy this Article




Summary: 
Natural language interface systems can accept more unrestricted queries from users than other systems, however it is impossible to understand erroneous sentences which include the syntax errors, unknown words and misspelling. In order to realize the superior natural language interface, the automatic error correction for erroneous sentences is one of problems to be solved. The method to apply the LR parsing strategies is one of the famous approaches as the robust error recovery scheme. This method is able to obtain a high correction accuracy, however it takes a great deal of time to parse the sentence, such that it becomes a very important task to improve the time-cost. In this paper, we propose the method to improve the time efficiency, keeping the correction accuracy of the traditional method. This method makes use of a new parsing table that denotes the states to be transited after accepting each symbol. By using this table, the symbol which is allocated just after the error position can be utilized for selecting correction symbols, as a result, the number of candidates produced on the correction process is reduced, and fast system can be realized. The experiment results, using 1,050 sentences including error characters, show that this method can correct error points 69 times faster than the traditional method, also keep the same correction accuracy as the traditional method.