Fast and Accurate Misspelling Correction in Large Corpora

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1634–1642, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Fast and Accurate Misspelling Correction in Large Corpora Octavian Popescu Fondazione Bruno Kessler Trento, Italy popescu@fbk.eu Ngoc Phuoc An Vo University of Trento Fondazione Bruno Kessler Trento, Italy ngoc@fbk.eu Abstract There are several NLP systems whose ac- curacy depends crucially on finding mis- spellings fast. However, the classical ap- proach is based on a quadratic time algo- rithm with 80% coverage. We present a novel algorithm for misspelling detection, which runs in constant time and improves the coverage to more than 96%. We use this algorithm together with a cross docu- ment coreference system in order to find proper name misspellings. The experi- ments confirmed significant improvement over the state of the art. 1 Introduction The problem of finding the misspelled words in a corpus is an important issue for many NLP sys- tems which have to process large collections of text documents, like news or tweets corpora, dig- italized libraries etc. Any accurate systems, such as the ones developed for cross document corefer- ence, text similarity, semantic search or digital hu- manities, should be able to handle the misspellings in corpora. However, the issue is not easy and the required processing time, memory or the de- pendence on external resources grow fast with the size of the analyzed corpus; consequently, most of the existing algorithms are inefficient. In this pa- per, we present a novel algorithm for misspelling detection which overcomes the drawbacks of the previous approaches and we show that this algo- rithm is instrumental in improving the state of the art of a cross document coreference system. Many spelling errors in a corpus are acciden- tal and usually just one or two letters in a word are affected, like existnece vs. the dictionary form existence. Such misspellings are rather a unique phenomenon occurring randomly in a text. For an automatic speller which has access to a dictionary, finding and compiling a list of correct candidates for the misspelled words like the one above is not very difficult. However, not all misspellings are in this category. To begin with, proper nouns, espe- cially foreign proper names, are not present in the dictionary and their misspelling may affect more than one or two characters. Moreover, the mis- spelling of proper names may not be random, for example there might be different spellings of the same Chinese or Russian name in English, the in- correct ones occurring with some frequency. Also, especially if the corpus contains documents writ- ten by non native speakers, the number of char- acters varying between the correct and the actual written form may be more than two. In this case, finding and compiling the list of correct candidates is computationally challenging for traditional al- gorithms, as the distance between the source string and the words in the candidates list is high. The Levenshtein distance has been used to com- pile …

Content truncated to 500 words