A Method for the Correction of Garbled Words Based on the Levenshtein Metric
IEEE Transactions on ComputersPublished 1 February 1976
Teruo Okuda, Eiichi Tanaka, Tamotsu Kasai
Citations203
SJR quartileQ1
SJR score1.16
SNIP1.61
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
According to the results of simulation on nearly 1000 high occurrence English words, higher error correcting rates can be achieved by this method than any other method tried to date.
Abstract
In this paper we propose a new method for correcting garbled words based on Levenshtein distance and weighted Levenshtein distance. We can correct not only substitution errors, but also insertion errors and deletion errors by this method. According to the results of simulation on nearly 1000 high occurrence English words, higher error correcting rates can be achieved by this method than any other method tried to date. Hardware realization of the method is possible, though it is rather complicated.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of Molecular BiologyA general method applicable to the search for similarities in the amino acid sequence of two proteins
11,464 Citations1970Saul B. Needleman, Christian D. Wunsch
A computer adaptable method for finding similarities in the amino acid sequences of two proteins has been developed and it is possible to determine whether significant homology exists between the proteins to trace their possible evolutionary development.
Princeton University Press eBooksApplied Dynamic Programming
1,956 Citations1962Richard Bellman, Stuart E. Dreyfus
Proceedings of the National Academy of SciencesMatching Sequences under Deletion/Insertion Constraints
302 Citations1972David Sankoff
An economical algorithm is elaborated for finding subsequences satisfying deletion/insertion constraints and is useful in the study of genetic homology based on nucleotide or amino-acid sequences.
IEEE Transactions on ComputersA Contextual Postprocessing System for Error Correction Using Binary n-Grams
112 Citations1974Edward M. Riseman, Allen R. Hanson
Various algorithms utilizing context are considered, from a dictionary algorithm which has available the maximum amount of information, to a set of contextual algorithms utilizing positional binary n-gram statistics.
Information and ControlA program for correcting spelling errors
83 Citations1960Charles R. Blair
A program using a simple, heuristic procedure for associating “similar” spellings is able to correct misspelled words using only a vocabulary of properly spelled words.
IEEE Transactions on Information TheorySynchronization and substitution error-correcting codes for the Levenshtein metric
58 Citations1976Eiichi Tanaka, T. Kasai
Block codes are constructed that are capable of simultaneously correcting synchronization errors in t consecutive words, for any t \geq 2e + 1 , and s or fewer substitution errors in each of t - 1 or fewer of these words under the condition that there exists at least one ungarbled word among the t consecutive Words.
IEEE Transactions on ComputersContextual Word Recognition Using Binary Digrams
52 Citations1971Edward M. Riseman, Roger W. Ehrich
The concept of binary digrams is introduced which overcomes some of the problems of past approaches and can be used to extract offectively the "syntax" of the dictionary while requiring very modest amounts of storage.
The use of context for correcting garbled English text
26 Citations1964Charles Vossler, Neil M. Branston
Two different methods for using context to correct garbled English text using a dictionary of English words containing their probability of occurrence and letter digram frequencies to roughly approximate English word probabilities are described.
Information and ControlThe degarbler—A program for correcting machine-read morse code
24 Citations1962Constance K. McElwain, Martha B. Evens
An IBM 7090 program automatically corrects garbled samples of English text to resemble those caused by Morse Code transmissions, showing apparent improvement in intelligibility.
The Journal of the Acoustical Society of AmericaArticulation Testing Methods
23 Citations1930Harvey Fletcher, John C. Steinberg
Techniques for replacing characters that are garbled on input
19 Citations1966Gary Carlson
This study reports the results of a computer technique to reduce errors of input data, requiring increasingly large volumes of data conversion to machine language.