LevenshteinDistance算法（编辑距离算法）

2019-11-14 13:44:28

字体：大中小

来源：转载

供稿：网友

编辑距离

编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

应用

最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中，详细如下：（特别的，对于中文自然语言处理，一般以词为基本处理单元）

DNA分析：基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变（mutation）。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。如果要更正式些，可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。

全局序列比对尝试找到两个完整的序列 S1和 S2之间的最佳比对。以下面两个 DNA 序列为例：
S1= GCCCTAGCG
S2= GCGCAATG
如果为每个匹配字符一分，一个空格扣两分，一个不匹配字符扣一分，那么下面的比对就是全局最优比对：
S1'= GCCCTAGCG
S2'= GCGC-AATG
连字符（-）代表空格。在 S2'中有五个匹配字符，一个空格（或者反过来说，在 S1'中有一个插入项），有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0，这是能够实现的最佳结果。
使用局部序列比对，不必对两个完整的序列进行比对，可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1和 S2，以及同样的得分方案，可以得到以下局部最优比对 S1''和 S2''：
S1 = GCCCTAGCG
S1''= GCG
S2''= GCG
S2 = GCGCAATG
这个局部比对的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。

拼写纠错（Spell Correction）：又拼写检查（Spell Checker），将每个词与词典中的词条比较，英文单词往往需要做词干提取等规范化处理，如果一个词在词典中不存在，就被认为是一个错误，然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。

这里肯定有人有疑问：对每个不在词典中的词（假如长度为len）都与词典中的词条计算最小编辑距离，时间复杂度是不是太高了？的确，所以一般需要加一些剪枝策略，如：

因为一般拼写检查应用只需要给出Top-N的纠正建议即可（N一般取10），那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len-3、...的词条比较；
限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值；
如果最小编辑距离为1的候选词条超过N后，终止处理；
缓存常见的拼写错误和建议，提高性能。

命名实体抽取（Named Entity Extraction）：由于实体的命名往往没有规律，如品牌名，且可能存在多种变形、拼写形式，如“IBM”和“IBM Inc.”，这样导致基于词典完全匹配的命名实体识别方法召回率较低，为此，我们可以使用编辑距离由完全匹配泛化到模糊匹配，先抽取实体名候选词。

具体的，可以将候选文本串与词典中的每个实体名进行编辑距离计算，当发现文本中的某一字符串的编辑距离值小于给定阈值时，将其作为实体名候选词；获取实体名候选词后，根据所处上下文使用启发式规则或者分类的方法判定候选词是否的确为实体名。

实体共指（Entity Coreference）：通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系？如“IBM”和“IBM Inc.”, "Stanford PResident John Hennessy "和"Stanford University President John Hennessy"。
机器翻译（Machine Translation）：

识别平行网页对：由于平行网页通常有相同或类似的界面结构，因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来，连接成一个字符串，然后用最小编辑距离考察两个字符串的近似度。实际中，此策略一般与文档长度比例、句对齐翻译模型等方法结合使用，以识别最终的平行网页对。
自动评测：首先存储机器翻译原文和不同质量级别的多个参考译文，评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上，间接估算自动译文的质量，如下图所示：
字符串核函数（String Kernel）：最小编辑距离作为字符串之间的相似度计算函数，用作核函数，集成在SVM中使用。

问题：找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符

解析：

首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

显然可以有如下动态规划公式：

if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

	0	f	a	i	l	i	n	g
0
s
a
i
l
n

	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1
a	2
i	3
l	4
n	5

计算edit(1, 1)，edit(0, 1) + 1 == 2，edit(1, 0) + 1 == 2，edit(0, 0) + f(1, 1) == 0 + 1 == 1，min(edit(0, 1)，edit(1, 0)，edit(0, 0) + f(1, 1))==1，因此edit(1, 1) == 1。依次类推：

	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2
i	3
l	4
n	5

edit(2, 1) + 1 == 3，edit(1, 2) + 1 == 3，edit(1, 1) + f(2, 2) == 1 + 0 == 1，其中s1[2] == 'a' 而 s2[1] == 'f'‘，两者不相同，所以交换相邻字符的操作不计入比较最小数中计算。以此计算，得出最后矩阵为：

	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2	1	2	3	4	5	6
i	3	3	2	1	2	3	4	5
l	4	4	3	2	1	2	3	4
n	5	5	4	3	2	2	2	3

应用：

（1）编辑距离是测量一个字符串转换成另外一个字符串需要操作（操作包括：插入    删除    置换）的最小次数。
          编辑距离可以用来计算两字符串的相似度，另外也可以通过余弦方法来计算两字符串的相似度
（2）算法实现采用动态规划算法，其求解过程类似于求两字符串的最长公共序列（LCS）
           下面是算法实现：

 1 public class Distance 2 { 3        public static int getDistance(String s1, String s2) 4        { 5            int len1 = s1.length(); 6            int len2 = s2.length(); 7             8            int[][] d = new int[len1+1][len2+1]; 9            int i=0, j=0;10            for(i=0; i<=len1; i++)11                d[i][0] = i;12            for(j=0; j<=len2; j++)13                d[0][j] = j;14             for (i = 1; i < len1+1; i++)15                 for (j = 1; j < len2+1; j++)16                 {17                     int cost = 1;18                     if(s1.charAt(i-1) == s2.charAt(j-1))19                     {20                         cost = 0;21                     }22                     int delete = d[i - 1][j] + 1;23                     int insert = d[i][j - 1] + 1;24                     int substitution = d[i - 1][j - 1] + cost;25                     d[i][j] = min(delete, insert, substitution);26                }27             return (d[len1][len2]);28        }29        30        public static int min(int d,int i,int s)31        {   32             int temp = 0;33             if(d>i)34                 temp = i;35             else36                 temp = d;37             return s<temp?s:temp;38         }39    40    public static void main(String args[])41    {42        String s1= "kitten";43        String s2 = "sitting";44        System.out.println(Distance.getDistance(s1, s2));45    }46 }

编辑距离（计算两个字符串的相似度）算法 .Net语言实例：

using System;using System.Collections.Generic;/* * 作者：熊仔其人 * 时间：2014年4月22日 */namespace DataTool{    /// <summary>    /// 相似度    /// 熊仔其人    /// 2014年4月22日    /// </summary>    public static class LevenshteinDistance    {        #region Levenshtein Distance算法（编辑距离算法）        /// <summary>        /// 三个数字中取最小的一个数字        /// </summary>        /// <param name="first"></param>        /// <param name="second"></param>        /// <param name="third"></param>        /// <returns></returns>        private static int LowerOfThree(int first, int second, int third)        {            int min = first;            if (second < min)                min = second;            if (third < min)                min = third;            return min;        }        /// <summary>        /// 根据Levenshtein Distance算法（编辑距离算法）计算两个字符串的相似度        /// </summary>        /// <param name="text1"></param>        /// <param name="text2"></param>        /// <returns></returns>        private static int Levenshtein_Distance(string text1, string text2)        {            int[,] Matrix;            int n = text1.Length;            int m = text2.Length;            int temp = 0;            char ch1;            char ch2;            int i = 0;            int j = 0;            if (n == 0)            {                return m;            }            if (m == 0)            {                return n;            }            Matrix = new int[n + 1, m + 1];            for (i = 0; i <= n; i++)            {                //初始化第一列                Matrix[i, 0] = i;            }            for (j = 0; j <= m; j++)            {                //初始化第一行                Matrix[0, j] = j;            }            for (i = 1; i <= n; i++)            {                ch1 = text1[i - 1];                for (j = 1; j <= m; j++)                {                    ch2 = text2[j - 1];                    if (ch1.Equals(ch2))                    {                        temp = 0;                    }                    else                    {                        temp = 1;                    }                    Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp);                }            }            //for (i = 0; i <= n; i++)            //{            //    for (j = 0; j <= m; j++)            //    {            //        Console.Write(" {0} ", Matrix[i, j]);            //    }            //    Console.WriteLine("");            //}            return Matrix[n, m];        }        /// <summary>        /// 根据Levenshtein Distance算法（编辑距离算法）计算两个字符串的相似度（百分比）        /// </summary>        /// <param name="text1">第一个字符串</param>        /// <param name="text2">第二个字符串</param>        /// <returns>相似度（百分比）</returns>        public static decimal LevenshteinDistancePercent(string text1, string text2)        {            if (string.IsNullOrEmpty(text1) && string.IsNullOrEmpty(text2))                return 1;            else if (string.IsNullOrEmpty(text1) || string.IsNullOrEmpty(text2))                return 0;            int maxLenth = text1.Length > text2.Length ? text1.Length : text2.Length;            int val = Levenshtein_Distance(text1, text2);            return 1 - (decimal)val / maxLenth;        }        #endregion        #region 计算两个字符串的相似度（百分比）        /// <summary>        /// 计算两个字符串的相似度（百分比），比较每一个字符组成，返回结果相似度与字符顺序有关，但是并不需要顺序完全一致        /// </summary>        /// <param name="text1">第一个字符串</param>        /// <param name="text2">第二个字符串</param>        /// <returns>相似度（百分比）</returns>        public static decimal SimilarByStringPercent(string text1, string text2)        {            if (string.IsNullOrEmpty(text1) && string.IsNullOrEmpty(text2))                return 1;            else if (string.IsNullOrEmpty(text1) || string.IsNullOrEmpty(text2))                return 0;            decimal returnValue = 0;            int maxLength;            int i, l;            List<string> tb1 = new List<string>();            List<string> tb2 = new List<string>();            i = 0;            l = 1;            maxLength = text1.Length;            if (text1.Length < text2.Length)                maxLength = text2.Length;            while (l <= text1.Length)            {                while (i < text1.Length - 1)                {                    if (i + l > text1.Length)                        break;                    tb1.Add(text1.Substring(i, l));                    i++;                }                i = 0;                l++;            }            i = 0;            l = 1;            while (l <= text2.Length)            {                while (i < text2.Length - 1)                {                    if (i + l > text2.Length)                        break;                    tb2.Add(text2.Substring(i, l));                    i++;                }                i = 0;                l++;            }            foreach (string subStr in tb1)            {                decimal tempRe = 0;                if (tb2.Contains(subStr))                {                    tempRe = (decimal)subStr.Length / maxLength;                    if (tempRe > returnValue)                        returnValue = tempRe;                    if (tempRe == 1)                        break;                }            }            return returnValue;        }        #endregion    }}