编辑距离算法的优化与实现.docx
《编辑距离算法的优化与实现.docx》由会员分享，可在线阅读，更多相关《编辑距离算法的优化与实现.docx（27页珍藏版）》请在冰点文库上搜索。
编辑距离算法的优化与实现
编辑距离算法的优化与实现
摘要：
在分析基于动态规划的编辑距离算法对文本相似度计算的不足的基础上，利用数据结构在空间效率和时间效率上优化该算法、采用中文分词的思想优化和改善该算法的时间效率和准确率，克服了原有的基于动态规划的计算方法所具有的效率低、准确率低、耗内存高的缺点。
通过多种优化方案的实验测试和分析，结果表明优化后的算法取得了很好的准确率和时空效率，更好的用于文本相似度计算。
关键词：
编辑距离算法；文本相似度计算；算法优化；动态规划
1引言
文本相似度的计算在信息检索、文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，长期以来一直是研究的热点和难点。
人们在文本相似度计算中使用编辑距离算法，但该方法单纯以字为单位计算各个字符之间的编辑距离，插入删除替换三种基本操作的代价值的方法不够明确合理，从而使计算结果存在一定的偏差。
故对传统的文本相似度检测编辑距离算法进行优化和改善，提出了一种基于改进编辑距离和中文分词相融合的计算文本相似度的方法，使优化改善后的算法具有较高的准确率和效率、较低的存储空间，更符合文本相似度计算的要求，有效提高文本相似度算法的效率和准确性，使文本相似度计算的性能进一步改善。
2编辑距离算法
4.3.1编辑距离定义
编辑距离又称Levenshtein距离（也叫做EditDistance），是由俄国科学家VladimirLevenshtein于1965年在文献[1]中提出的，是一种常用的距离函数度量方法，在多个领域特别是文本相似度检测得到了广泛的应用。
编辑距离是指两系列字符串之间只能通过插入、删除和替换三种基本操作把源字符串（S）转换成目标字符串（T）所需的最少基本操作次数。
编辑距离值越大，则相似度越小。
4.3.2编辑距离算法原理
对于求两个字符串之间的编辑距离实际上可以转化为一个求最优解的问题，可以利用动态规划的思想[2]来计算，计算原理的步骤如下表2-1所示：
表2-1编辑距离算法原理的计算步骤
步骤
描述
1
设置n为源字符串s的长度。
设置m为目标字符串t的长度。
如果n等于0，返回m并退出。
如果m等于0，返回n并退出。
构造一个矩阵d[m+1,n+1]含有0..m行和0..n列。
2
初始化矩阵第一行0..ñ。
初始化矩阵第一列0..m。
3
检查s（ifrom1ton）中的每个字符。
4
检查t（jfrom1tom）中的每个字符。
5
如果s[i]等于t[j]，则编辑代价cost为0；
如果s[i]不等于t[j]，则编辑代价cost为1。
6
设置矩阵单元格d[i,j]的值为下面的最小值:
a.正上方单元格的值1:
d[i-1,j]+1.
b.左边单元格的值加1:
d[i,j-1]+1.
c.对角线单元格的值加上编辑代价cost的值:
d[i-1,j-1]+cost.
7
在完成迭代（3,4,5,6）之后，d[m,n]便是编辑距离的值。
本小节将演示如何计算源字符串"GUMBO"和目标字符串"GAMBOL"两个字符串之间的Levenshtein距离，计算步骤如下：
步骤1、2步骤3、6，当i=1步骤3、6，当i=2
G
U
M
B
O
0
1
2
3
4
5
G
1
A
2
M
3
B
4
O
5
L
6
G
U
M
B
O
0
1
2
3
4
5
G
1
0
A
2
1
M
3
2
B
4
3
O
5
4
L
6
5
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
A
2
1
1
M
3
2
2
B
4
3
3
O
5
4
4
L
6
5
5
步骤3、6，当i=3步骤3、6，当i=4步骤3、6，当i=5
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
A
2
1
1
2
M
3
2
2
1
B
4
3
3
2
O
5
4
4
3
L
6
5
5
4
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
A
2
1
1
2
3
M
3
2
2
1
2
B
4
3
3
2
1
O
5
4
4
3
2
L
6
5
5
4
3
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
4
A
2
1
1
2
3
4
M
3
2
2
1
2
3
B
4
3
3
2
1
2
O
5
4
4
3
2
1
L
6
5
5
4
3
2
步骤7，编辑距离是矩阵右下角的值，d[m,n]=2；
源字符串"GUMBO"变换为目标字符串"GAMBOL"的过程，直观可看出的，即通过将"A"替换为"U"，并在末尾追加"L"字符，这跟计算的结果一致。
4.3.3编辑距离以及文本相似度计算
编辑距离D（S,T）的计算方法如下所述。
首先假设Dij=D（s1…si,,t1…tj），0≤i≤m,0≤j≤n,Dij表示从s1…si到t1…tj的编辑距离，那么（m+1）×（n+1）阶矩阵Dij可通过下面的
（1）式计算得到：
0i=0且j=0;
Di-1j-1+（ifsi=tjthen0else1）;
Dij=MinDi-1,j+1;i>0或j>0；
（1）式
Di,j-1+1;
（1）式包含删除、插入、替换三种操作，该算法是从两字符串的左边开始比较，记录已经比较过的编辑距离，然后进一步得到下一个字符位置时的编辑距离。
矩阵Dij能够通过从D00逐步逐列计算获取，最终Dmn表示D（S，T）的值，即S和T的编辑距离。
文本相似度计算[3]：
编辑距离越大，相似度越小。
假设源字符串S与目标字符串T长度的最大值为Lmax，编辑距离为LD，相似度为SI，则相似度SI的计算如
（2）式所示。
SI=1-LD/Lmax
（2）式
4.3.4编辑距离算法核心代码
publicintLevenshteinDistance（stringstrs1,stringstrs2）
{
char[]str1=strs1.ToCharArray（）;
char[]str2=strs2.ToCharArray（）;
inti,j,temp;
if（str1.Length==0）
{
temp=str2.Length;
}
if（str2.Length==0）
{
temp=str1.Length;
}
int[,]dist=newint[str1.Length+1,str2.Length+1];
for（i=0;i<=str1.Length;i++）dist[i,0]=i;
for（i=0;i<=str2.Length;i++）dist[0,i]=i;
for（i=1;i<=str1.Length;i++）
{
for（j=1;j<=str2.Length;j++）
{
if（str1[i-1]==str2[j-1]）
{
dist[i,j]=dist[i-1,j-1];
}
else
{
dist[i,j]=LowerOfThree（dist[i,j-1],dist[i-1,j-1],dist[i-1,j]）+1;
}
}
}
temp=dist[str1.Length,str2.Length];
returntemp;
}
4.3.5编辑距离算法分析
假设m,n分别表示源字符串S和目标字符串T的长度，则上述的基于动态规划的编辑距离算法，其算法的空间复杂度为O（mn），时间复杂度为O（mn）。
尽管编辑距离算法在文本相似度检测方面具有一定的优势，具有简单易于计算，并有一定的正确率，但仍然存在一些问题。
（1）此编辑距离算法忽略了序列长度对编辑距离产生的影响，没有考虑到算法所需的内存，因而造成所耗内存较大。
（2）单纯以字为单位计算各个字符之间的编辑距离，计算出来的距离只是文字表面的距离，并没有充分考虑词语的概念，使得计算结果的语义准确率不高，特别是对中文的检测时常常得不到满意的结果。
针对以上两个问题，下文提出了几种优化方案，分别是基于算法结构的内部调整优化以及基于词语相似度的文本计算，通过大量的实验测试证明了可降低计算所耗的存储空间，提高了算法的效率和准确率。
3改进编辑距离算法
3.1空间复杂度优化
经过对上面的传统编辑距离算法计算过程的分析，发现算法中作为存储的二维矩阵，在每一个循环中，其实只有一行的数据参与了计算，之前的数据行都不再参与计算了。
因此，从这个出发点入手，对算法结构进行调整，将二维数组改为两个一维数组。
经测试，计算结果和速度没有太大的差异。
但空间复杂度减少了很多，改进后空间复杂度降为：
O（min（m,n））。
设置n为源字符串s的长度，m为目标字符串t的长度。
我们不妨设n表3-1空间复杂度优化的编辑距离算法步骤
步骤
描述
1
设置n为源字符串s的长度。
设置m为目标字符串t的长度。
如果n等于0，返回m并退出。
如果m等于0，返回n并退出。
构造两个一维数组v0[n+1]和v1[n+1]，串联0..n之间所有的元素。
2
初始化v0to0..n。
3
检查t（jfrom1tom）中的每个字符。
4
检查s（ifrom1ton）中的每个字符。
5
如果s[i]等于t[j]，则编辑代价cost为0；
如果s[i]不等于t[j]，则编辑代价cost为1。
6
设置一维数组单元格v1[i]的值为下面的最小值:
a.正上方单元格的值1:
v0[i]+1.
b.左边单元格的值加1:
v1[i-1]+1.
c.对角线单元格的值加上编辑代价cost的值:
v0[i-1]+cost.
7
在完成迭代（3,4,5,6）之后，v1[n]便是编辑距离的值。
本小节仍以源字符串"GUMBO"和目标字符串"GAMBOL"来演示如何计算这两个字符串之间的Levenshtein距离，计算步骤如下：
步骤1、2步骤3、6，当i=1步骤3、6，当i=2
G
U
M
B
O
V0
0
1
2
3
4
5
V1
G
A
M
B
O
L
G
U
M
B
O
v0
0
1
2
3
4
5
V1
G
1
0
1
2
3
4
A
M
B
O
L
G
U
M
B
O
0
1
2
3
4
5
v0
G
1
0
1
2
3
4
V1
A
2
1
1
2
3
4
M
B
O
L
步骤3、6，当i=3步骤3、6，当i=4步骤3、6，当i=5
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
4
V0
A
2
1
1
2
3
4
V1
M
3
2
2
1
2
3
B
O
L
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
4
A
2
1
1
2
3
4
V0
M
3
2
2
1
2
3
V1
B
4
3
3
2
1
2
O
L
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
4
A
2
1
1
2
3
4
M
3
2
2
1
2
3
V0
B
4
3
3
2
1
2
V1
O
5
4
4
3
2
1
L
步骤3、6，当i=6
G
U
M
B
O
0
1
2
3
4
5
G
1
0
1
2
3
4
A
2
1
1
2
3
4
M
3
2
2
1
2
3
B
4
3
3
2
1
2
V0
O
5
4
4
3
2
1
V1
L
6
5
5
4
3
2
步骤7，右下角的值便是编辑距离的值，v1[n]=2；
传统的编辑距离算法会创建一个矩阵d[m+1,n+1],但此经过优化的算法将会创建两个一维数组v0[n+1]和v1[n+1]，其计算结果没有发生变化，但内存占用更少，其空间复杂度可为两个字符串长度的最小值O（min（m，n））。
在经过空间复杂度优化的编辑距离算法，其编辑步数一样，因而相应的文本相似度计算的结果也一样。
编辑距离算法的空间复杂度优化核心代码如下：
publicintLevenshteinDistance（stringstrs1,stringstrs2）
{
char[]str1=strs1.ToCharArray（）;
char[]str2=strs2.ToCharArray（）;
inti,j,temp;
if（str1.Length==0）
{
temp=str2.Length;
}
if（str2.Length==0）
{
temp=str1.Length;
}
int[,]dist=newint[2,str2.Length+1];
for（i=0;i<=str2.Length;i++）dist[0,i]=i;
for（i=1;i<=str1.Length;i++）
{
dist[1,0]=i;
for（j=1;j<=str2.Length;j++）
{
if（str1[i-1]==str2[j-1]）
{
dist[1,j]=dist[0,j-1];
}
else
{
dist[1,j]=LowerOfThree（dist[0,j-1],dist[0,j],dist[1,j-1]）+1;
}
}
for（j=0;j<=str2.Length;j++）
{
dist[0,j]=dist[1,j];
}
temp=dist[1,str2.Length];
returntemp;
}
3.2时间效率优化
4.3.1编辑距离算法的时间效率优化思想
在对上面的传统编辑距离算法仔细分析后，发现两个字符串相对应位置上的字符相同时，把这两个相对应的相同的字符删除掉后，对计算结果没有任何影响。
删除这些相对应位置相同的字符后将会减少编辑计算的字符，即参与计算的两字符的长度变短，从而使得计算的时间效率加快，达到提高算法时间效率的效果。
再者，针对于纯中文的文本，我们考虑到文本中的标点符号也会被当成一个独立的字符参与计算，但是这些标点符号对于我们所要计算的文本相似度来说毫无意义。
因此可采取的做法就是把这些标点符号全部删除，只保留文字，用纯文字的字符来参与计算，这样将会使得参与计算的字符长度变短，加快计算的速率，减少计算所占用的内存空间，而且使得计算的结果更加地符合实际，获得更高的准确率。
4.3.2编辑距离算法的时间效率优化原理
步骤一：
把源字符串S里含有的标点符号用空格替换掉。
步骤二：
把源字符串S中所含的空格全部清除。
步骤三：
把目标字符串T里含有的标点符号用空格替换掉。
步骤四：
把目标字符串T中所含的空格全部清除。
步骤五：
把去除标点符号的源字符串S转换成一维字符数组S1。
步骤六：
把去除标点符号的目标字符串T转换成一维字符数组T1。
步骤七：
从两数组的起始位置开始，比较S1和T1中相对应位置的字符是否相等，若相等，则S1和T1中相对应位置的字符将用空格代替。
步骤八：
从两数组的末尾位置开始，比较S1和T1中相对应位置的字符是否相等，若相等，则S1和T1中相对应位置的字符将用空格代替。
步骤九：
把经过步骤五、六后的数组S1转换成字符串S2，并把里面所含的空格全部清除。
步骤十：
把经过步骤五、六后的数组T1转换成字符串T2，并把里面所含的空格全部清除。
步骤十一:
再把所得到的字符串S2和字符串T2进行计算它们之间的编辑距离。
本小节以源字符串S“计算机,不怕你!
”和目标字符串T“物理机电,谁怕谁?
”来演示如何计算这两个字符串之间的Levenshtein距离。
计算机，不怕你！
源字符串S:
物理机电，谁怕谁？
目标字符串T:
计算机不怕你
步骤一：
源字符串S:
计算机不怕你
步骤二：
源字符串S:
物理机电谁怕谁
步骤三：
目标字符串T:
物理机电谁怕谁
步骤四：
目标字符串T:
计
算
机
不
怕
你
步骤五：
字符数组S1:
物
理
机
电
谁
怕
谁
步骤六：
字符数组T1:
步骤七：
计
算
不
怕
你
物
理
电
谁
怕
谁
字符数组S1:
字符数组T1:
步骤八:
字符数组S1:
字符数组T1:
计算不你
步骤九：
源字符串S2:
物理电谁谁
步骤十：
目标字符串T2:
步骤十一：
计算字符串S2和字符串T2之间的编辑距离，如表3-2所示。
表3-2字符串S2和字符串T2之间的编辑距离计算
计
算
不
你
0
1
2
3
4
物
1
1
2
3
4
理
2
2
2
3
4
电
3
3
3
3
4
谁
4
4
4
4
4
谁
5
5
5
5
5
步骤十一右下角的值便是源字符串S“计算机,不怕你!
”和目标字符串T“物理机电,谁怕谁?
”的编辑距离的值，编辑步数为5。
4.3.3编辑距离算法的时间效率优化比较和分析
源字符串S“计算机,不怕你!
”和目标字符串T“物理机电,谁怕谁?
”在没有经过时间效率优化的编辑距离算法，其算法步骤如表3-3所示：
表3-3源字符串S和目标字符串T之间的编辑距离计算
计
算
机
，
不
怕
你
！
0
1
2
3
4
5
6
7
8
物
1
1
2
3
4
5
6
7
8
理
2
2
2
3
4
5
6
7
8
机
3
3
3
2
3
4
5
6
7
电
4
4
4
3
3
4
5
6
7
，
5
5
5
4
3
4
5
6
7
谁
6
6
6
5
4
4
5
6
7
怕
7
7
7
6
5
5
4
5
6
谁
8
8
8
7
6
6
5
5
6
？
9
9
9
8
7
7
6
6
6
右下角的值为源字符串S“计算机,不怕你!
”和目标字符串T“物理机电,谁怕谁?
”的编辑距离的值，编辑步数为6，则它们所对应的文本相似度计算为：
因为Lmax=Max（S.Length,T.Length）=9；
所以SI=1-LD/Lmax=1-6/9≈33.33%
经过时间效率优化后的编辑距离算法，它们的编辑步数为5，则它们所对应的文本相似度的计算为：
因为Lmax=Max（S1.Length,T1.Length）=7；（即为两个字符串删除标点符号后的字符串长度的最大值。
）
所以SI=1-LD/Lmax=1-5/7≈%
对这两个文本相似度计算的结果分析，容易发现经过时间效率优化后的编辑距离算法更符合实际情况，更加实用。
删除了字符串中标点符号和相对应位置的相同的字符后，使得计算量减少，所占内存减少，并加快了计算的效率，提高了准确率。
4.3.4编辑距离算法的时间效率优化核心代码
strings1=Regex.Replace（string1,@"[^\u4e00-\u9fa5\s]",""）;
stringss1=Regex.Replace（s1,@"\s",""）;
strings2=Regex.Replace（string2,@"[^\u4e00-\u9fa5\s]",""）;
stringss2=Regex.Replace（s2,@"\s",""）;
if（
升级会员 