Typographical Nearest-Neighbor Search in a Finite-State Lexicon and Its Application to Spelling Correction
Lecture notes in computer sciencePublished 1 January 2002
Agata Savary
Citations20
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A method of error-tolerant lookup in a finite-state lexicon is described, as well as its application to automatic spelling correction, to retain only the most similar corrections (nearest neighbours) and to reach the first correction as soon as possible.
Abstract
A method of error-tolerant lookup in a finite-state lexicon is described, as well as its application to automatic spelling correction. We compare our method to the algorithm by K. Oflazer [14]. While Oflazer's algorithm searches for all possible corrections of a misspelled word that are within a given similarity threshold, our approach is to retain only the most similar corrections (nearest neighbours), reducing dynamically the search space in the lexicon, and to reach the first correction as soon as possible.
Keywords
Computer Science
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Communications of the ACMA technique for computer detection and correction of spelling errors
1,573 Citations1964Fred J. Damerau
The method described assumes that a word which cannot be found in a dictionary has at most one error, which might be a wrong, missing or extra letter or a single transposition.
ACM Computing SurveysTechniques for automatically correcting words in text
1,256 Citations1992Karen Kukich
Research aimed at correcting words in text has focused on three progressively more difficult problems: nonword error detection; (2) isolated-word error correction; and (3) context-dependent work correction, which surveys documented findings on spelling error patterns.
Wiley Encyclopedia of Electrical and Electronics EngineeringComputational Linguistics
834 Citations1999Fred Popowich
Computational LinguisticsRegular models of phonological rule systems
816 Citations1994Ronald M. Kaplan, Martin Kay
This paper shows in detail how this framework applies to ordered sets of context-sensitive rewriting rules and also to grammars in Koskenniemi's two-level formalism.
ACM Computing SurveysApproximate String Matching
586 Citations1980Patrick A. V. Hall, Geoff R. Dowling
Language<b>Finite-state language processing.</b> Ed. by Emmanuel Roche and Yves Schabes. Cambridge, MA: MIT Press, 1997. Pp. xvii, 464.
355 Citations1999Michael A. Covington
Topics include finite-state morphology, approximation of phrase-structure grammars, deterministic part-of-speech tagging, application of a finite- state intersection grammar, a infinite-state transducer for extracting information from text, and speech recognition using weighted finite automata.
Journal of the ACMAn Extension of the String-to-String Correction Problem
318 Citations1975Robert A. Wagner, Roy Lowrance
The set of allowable edit operations is extended to include the operation of interchanging the positions of two adjacent characters under certain restrictions on edit-operation costs, and it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.
Computational LinguisticsIncremental Construction of Minimal Acyclic Finite-State Automata
181 Citations2000Jan Daciuk, Stoyan Mihov +2 more
A new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings by adding new strings one by one and minimizing the resulting automaton on-the-fly.
arXiv (Cornell University)Error-tolerant Finite State Recognition with Applications to Morphological Analysis and Spelling Correction
174 Citations1995Kemal Oflazer
IEEE Transactions on CommunicationsDevelopment of a Spelling List
134 Citations1982Marie McIlroy
How the spelling checker works, how the words were chosen, how it was used to improve itself, and how the (reduced) list of 30000 English words was squeezed into 26000 16-bit machine words are told.
Combining Trigram-based and feature-based methods for context-sensitive spelling correction
126 Citations1996Andrew R. Golding, Yves Schabes
This paper addresses the problem of correcting spelling errors that result in valid, though unintended words and also the problem of correcting particular word usage errors, and introduces a method called Trigrams that uses part-of-speech trigrams to encode the context.
Extended finite state models of language
53 Citations1999András Kornai
arXiv (Cornell University)Incremental construction of minimal acyclic finite-state automata
51 Citations2000Jan Daciuk, Stoyan Mihov +2 more
Lecture notes in computer scienceMinimization of sequential transducers
48 Citations1994Mehryar Mohri
An algorithm for minimizing sequential transducers is presented, which is shown to be efficient, since in the case of acyclic transducers it operates in O(¦E¦+¦V¦ +¦F¦)+¦P max steps.
Acta InformaticaA model and a fast algorithm for multiple errors spelling correction
28 Citations1992Mingzhe Du, Siyuan Chang
A cut-off criterion has been discovered, which can detect whether the error distance between two character strings is greater than a prespecified value during the calculation, and a fast algorithm has been developed to find the nearest neighbors of a given character string in a dictionary.
Morphosyntactic correction in natural language interfaces
25 Citations1988Jean Véronis
This work describes here an efficient means of handling quite complex combinations of typographical, phonographic and agreement errors in French, which are typical of C.I.A. users.
The typology of unknown words
9 Citations1992Xiaobo Ren, François Perrault
Most current state-of-the-art natural language processing systems, when presented with real-life texts, have problems recognizing each and every word present in the input.