编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。
在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词 之间，由其中一个单词 转换为另一个单词 所需要的最少 单字符编辑操作 次数。
在这里定义的单字符编辑操作有且仅有三种：
譬如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有：
→ sitten (substitution of "s" for "k") → sittin (substitution of "i" for "e") → sitting (insertion of "g" at the end)
因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。
我们将两个字符串 的 Levenshtein Distance 表示为 ，其中 和 分别对应 的长度。那么，在这里两个字符串 的 Levenshtein Distance，即 可用如下的数学语言描述：
以 和 为例，建立一个矩阵，通过矩阵记录计算好的距离：
当 时， ，根据此初始化矩阵的第一行和第一列:
依据上面的公式可以继续推导出第二行：
第二行（index = 1）推导
继续迭代，第三行（index = 2）推导
直至推导出最终结果：
1 递归方式
2 动态规划 递归是从后向前分解，那与之相对的就是从前向后计算，逐渐推导出最终结果，此法被称之为动态规划，动态规划很适用于具有重叠计算性质的问题，但这个过程中会存储大量的中间计算的结果，一个好的动态规划算法会尽量减少空间复杂度。
编辑距离是NLP基本的度量文本相似度的算法，可以作为文本相似任务的重要特征之一，其可应用于诸如拼写检查、论文查重、基因序列分析等多个方面。但是其缺点也很明显，算法基于文本自身的结构去计算，并没有办法获取到语义层面的信息。
由于需要利用矩阵，故空间复杂度为O(MN)。这个在两个字符串都比较短小的情况下，能获得不错的性能。不过，如果字符串比较长的情况下，就需要极大的空间存放矩阵。例如：两个字符串都是20000字符，则 LD 矩阵的大小为：20000 * 20000 * 2=800000000 Byte=800MB。
[1] [2] [3] [4]
蓉儿…点滴缘
