Novel algorithm to generate shortest edit script using Levenshtein distance algorithm
String similarity, longest common subsequence and shortest edit scripts are the triplets of problem that related to each other. There are different algorithms exist to generate edit script by solving longest common subsequence problem. This paper proposes an algorithm that uses string similarity problem to generate shortest edit script. For this we use the famous Levenshtein distance algorithm, which computes a numerical value that represents similarity between the strings from 0 to n, where n is the length of longest input string, and produce the shortest edit script which contains instructions of Insert, Delete and Substitute.
Code (1)
Tasks
Edit script generationFile differenceSimilar Papers 제목 키워드 기반
A New String Edit Distance and Applications
String edit distances have been used for decades in applications ranging from spelling correction and web search suggestions to DNA analysis. Most string edit distances are variations of the Levenshtein distance and cons…
DNA analysisSpelling CorrectionEDITOR: an Edit-Based Transformer with Repositioning for Neural Machine Translation with Soft Lexical Constraints
We introduce an Edit-Based Transformer with Repositioning (EDITOR), which makes sequence generation flexible by seamlessly allowing users to specify preferences in output lexical choice. Building on recent models for non…
Imitation LearningMachine TranslationTranslationLevenshtein Transformer
Modern neural sequence generation models are built to either generate tokens step-by-step from scratch or (iteratively) modify a sequence of tokens bounded by a fixed length. In this work, we develop Levenshtein Transfor…
Automatic Post-EditingMachine TranslationText SummarizationTranslationImagined-Trailing-Whitespace-Agnostic Levenshtein Distance For Plaintext Table Detection
The standard algorithm for Levenshtein distance, treats trailing whitespace the same as any other letter or symbol. However, when humans compare 2 strings, we implicitly assume that both strings are padded by infinite tr…
Table DetectionLevenshtein Training for Word-level Quality Estimation
We propose a novel scheme to use the Levenshtein Transformer to perform the task of word-level quality estimation. A Levenshtein Transformer is a natural fit for this task: trained to perform decoding in an iterative man…
Transfer LearningTranslation