Binary codes capable of correcting deletions, insertions, and reversals

By V. Levenshtein. 1965

Subfields: Information Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Theory

In Algorithms & Complexity

Citations in the corpus

Break-It-Fix-It: Unsupervised Learning for Program Repair (2021, background): “We define that the fixer’s repair is successful if the output code has no AST parse errors and has Levenshtein edit-distance (Levenshtein, 1966) less than 5 tokens from the input code.”
Polyjuice: Generating Counterfactuals for Explaining, Evaluating, and Improving Models (2021, methodology): “As shown in Table 2, Polyjuice generates counterfactuals that are close to the original instance, measured by syntactic tree (Zhang and Shasha, 1989) and Levenshtein edit distance (Levenshtein, 1966).”
Librispeech: An ASR corpus based on public domain audio books (2015, background): “This is like doing Levenshtein alignment [16] , except we do not require it to consume the whole reference or hypothe sis from the beginning to end, and it also has tunable rather than fixed weights for the different kinds of errors.”
BERTScore: Evaluating Text Generation with BERT (2019, methodology): “Several methods use word edit distance or word error rate (Levenshtein, 1966), which quantify similarity using the number of edit operations required to get from the candidate to the reference.”
Automatic Evaluation of Machine Translation Quality Using Longest Common Subsequence and Skip-Bigram Statistics (2004, methodology): “Su et al. (1992) proposed a method based on measuring edit distance (Levenshtein 1966) between candidate and reference translations.”
Unsupervised Construction of Large Paraphrase Corpora: Exploiting Massively Parallel News Sources (2004, methodology): “A simple edit distance metric (Levenshtein 1966) was used to identify pairs of sentences within a cluster that are similar at the string level.”
Benchmark and Survey of Automated Machine Learning Frameworks (2019, background): “The similarity between two pipelines is than expressed by the Levenshtein ratio (Levenshtein, 1966; Ratcliff and Metzener, 1988).”
Survey on Automated Machine Learning (2019, methodology): “ of the resulting ML pipelines, we transform each pipeline to a string by mapping each algorithm to a distinct letter. The similarity between two pipelines is than expressed by the Levenshtein ratio (Levenshtein, 1966; Ratcli and Metzener, 1988). Table 5 shows the averaged pair-wise Levenshtein rati”
Libriheavy: A 50,000 Hours ASR Corpus with Punctuation Casing and Context (2023, methodology): “At this stage, we use the Levenshtein alignment [17] to find the best single region of alignment between the recognized audio (query) and the text segment (obtained by the longest chain pairs).”
Learning to Ask: Neural Question Generation for Reading Comprehension (2017, methodology): “, BM-25 (Robertson and Walker, 1994) and edit distance (Levenshtein, 1966).”
Survey of the State of the Art in Natural Language Generation: Core tasks, applications and evaluation (2017, background): “S tr in g d is ta n ce Edit distance Number of insertions, deletions, substitutions and, possibly, transposition required to transform the candidate into the reference string (Levenshtein, 1966).”
Optimal Completion Distillation for Sequence Learning (2018, methodology): “Recall the Levenshtein algorithm (Levenshtein, 1966) for calculating the minimum number of edits (insertion, deletion and substitution) required to convert sequences ỹ and y∗ to each other based on,  Dedit(ỹ<−1, :) =∞ Dedit(:,y ∗ <−1) =∞ Dedit(ỹ<0,y ∗ <0) = 0 , Dedit(ỹ<i,y ∗ <j) = min  Dedit(ỹ<i”
Houdini: Fooling Deep Structured Prediction Models (2017, methodology): “These metrics were derived from the Levenshtein Distance [23], which is the number of substitutions, deletions, and insertions divided by the target length.”
MCScript: A Novel Dataset for Assessing Machine Comprehension Using Script Knowledge (2018, methodology): “We merged all answers that were string-identical, contained another answer, or had a Levenshtein distance (Levenshtein, 1966) of 3 or less to another answer.”
Levenshtein Transformer (2019, methodology): “It returns the optimal actions a ∗ (either oracle insertion p ∗ , t ∗ or oracle deletion d ∗ ) by: Here, we use the Levenshtein distance (Levenshtein, 1965) 2 as D considering it is possible to obtain the action suggestions efﬁciently by dynamic programming.”
Scene Text Visual Question Answering (2019, methodology): “Finally, we define a new evaluation metric to better discern the models’ answering ability, that employs the Levenshtein distance [34] to account both for reasoning errors as well as shortcomings of the text recognition subsystem [15].”
FBK-UPV-UEdin participation in the WMT14 Quality Estimation shared-task (2014, methodology): “We follow (Zens and Ney, 2006) and extract three different WPP features depending on the criteria chosen to compute S ( e i ) : ) ∧ e a i = e i } S ( e i ) contain those translations e 0 for which the word Levenshtein-aligned (Levenshtein, 1966) to position i in e is equal to e i .”