Effective Spell Checking Methods Using Clustering Algorithms

Proceedings of Recent Advances in Natural Language Processing, pages 172–178, Hissar, Bulgaria, 7-13 September 2013. Effective Spell Checking Methods Using Clustering Algorithms Renato Cordeiro de Amorim Glynd ˆwr University, UK r.amorim@glyndwr.ac.uk Marcos Zampieri University of Cologne, Germany mzampier@uni-koeln.de Abstract This paper presents a novel approach to spell checking using dictionary cluster- ing. The main goal is to reduce the num- ber of times distances have to be calcu- lated when finding target words for mis- spellings. The method is unsupervised and combines the application of anomalous pattern initialization and partition around medoids (PAM). To evaluate the method, we used an English misspelling list com- piled using real examples extracted from the Birkbeck spelling error corpus. 1 Introduction Spell checking is a well-known task in computa- tional linguistics, dating back to the 1960s, most notably to the work of Damerau (1964). Nowa- days, spell checkers are an important component of a number of computer software such as web browsers, text processors and others. In recent years, spell checking has become a very important application to search engines (Mar- tins and Silva, 2004). Companies like Google or Yahoo! use log files of all users’ queries to map the relation between misspellings and the intended spelling reaching very high accuracy. The lan- guage of queries, however, is typically shorter than naturally occurring text, making this application of spell checking very specific (Whitelaw et al., 2009). Spell checking methods have two main func- tions. The first one is to identify possible mis- spellings that a user may commit. As described by Mitton (1996), misspellings can be related to the writer’s (poor) writing and spelling compe- tence, to learning disabilities such as dyslexia, and also to simple performance errors, known as ty- pos. The written production of non-native speak- ers also plays an important role in spell check- ing as they are, on average, more prone to errors than native speakers. These phenomena generate a wide range of different spelling possibilities that a spell checker should be trained to recognize. The second function of spell checkers is to sug- gest the users’ intended spelling of a misspelled word or at least to suggest a list of candidates in which the target word appears. This is often done by calculating the distance between the misspelled word and a set of potential candidates. As will be discussed in this paper, this is by no means triv- ial and several methods have been proposed to ad- dress this task. This paper presents a novel unsupervised spell checking method combining anomalous pattern initialization and partition around medoids (PAM). To the best of our knowledge this is the first at- tempt to apply these methods for spell checking. The approach described here aims to improve spell checking’ speed and performance. 2 Related Work Spell checking techniques have been substantially studied over the years. Mitton (2010) points out that the first attempt to solve the problem can be traced back to the work of Blair (1960) and later more attention was …

Content truncated to 500 words