论文标题
使用Levenshtein距离算法得出最短的编辑脚本算法
Algorithm to derive shortest edit script using Levenshtein distance algorithm
论文作者
论文摘要
字符串相似性，最长的常见子序列和最短的编辑脚本是彼此相关的问题的三联。存在不同的算法来通过解决最长的常见子序列问题来生成编辑脚本。本文提出了一种使用字符串相似性问题来生成最短编辑脚本的算法。为此，我们使用著名的Levenshtein距离算法，该算法计算一个数值，代表字符串从0到N之间的相似性，其中N是最长输入字符串的长度，并产生包含插入，删除和替换的最短编辑脚本。
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.
