文本比较算法分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇文本比较算法分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘要】基于文本比较算法，以算法的比较为切入点，通过比较算法的时间复杂度，找出适应文本的算法。实验结果表明，Nakatsu算法在长文本和相似度高的文本中效率更高，更易使用。
【关键词】文本比较算法;相似度;文本
1.引言
随着Internet的快速发展，文本比较作为基础被运用到许多方面，如：电脑自动阅卷已经成为当今教育界考试批卷的主流，基因突变序列的快速找出也让我们习以为常，利用相似度[1]对网页文本信息的抽取，论文等等，基于文本比较的技术在我们的生活中随处可见，所以本文开始着手研究文本比较算法的实质，针对不同的算法找出其最适应的条件，通过比较它们各自的优缺点，再结合实际进行分析，从而得出各自最具有代表性的文本特征。
2.算法概述
2.1 基于编距的LD算法
该算法是基于编辑距离的，所谓的编辑距离就是从文本A到文本B的变化步骤数，用LD（A，B）表示，很显然如果LD（A，B）=0表示文本A和B完全相同。这里需要定义Len（A）=M，Len（B）=N分别表示文本的长度。
建立M+2行N+2列的矩阵，初始化第二行和第二列的数值（令LD（2，2=0），行和列依次递增），遵循规则如下：
对于1≤i≤M，1≤j≤N，有公式
若ai=bj，则LD（i，j）=LD（i-1，j-1）
若ai≠bj，则LD（i，j）=Min（LD（i-1，j-1），LD（i-1，j），LD（i，j-1））+1主要代码如下：
for（int i=0;i<n-1;i++）{
for（int j=0;j<m-1;j++）{
int temp=0;
if（s1[i]！= s2[j]）
temp=1;
else
temp=0; table[j+1][i+1]=Min （table [j][i]+temp，table[j+1][i]+1， table[j][i+1]+1）;
}
}
private static int Min（int i，int j， int k） { int[] tempSequence={i，j，k};
int min=i;
for（int n=0;n<3;n++）{
if（tempSequence[n]<min）{
min=tempSequence[n];
}
}
return min;
}
2.2 LCS（最长公共子串）算法
该算法是基于求文本最长公共子串长度的，用LCS（A，B）表示，很显然如果LD（A，B）=0表示文本A和B完全不相同。
建立M+2行N+2列的矩阵，初始化第二行和第二列的数值（全为0），遵循规则如下：
对于1≤i≤M，1≤j≤N，有公式
若ai=bj，则LCS（i，j）=LCS（i-1，j-1）+1
若ai≠bj，则LCS（i，j）=Max（LCS（i-1，j-1），LCS（i-1，j），LCS（i，j-1））。
2.3 Nakatsu算法
该算法是利用线性空间求出最长公共子序列，用L（A，B）表示。既然是求最长公共子序列，很显然需要构造一个k行m列的LCS（A，B）矩阵，但是矩阵满足条件当i
for（int i=0;i<n-1;i++）{
for（int j=0;j<n-1;j++）{
T=GetP（i+j-1，L（j_1），L（j））
If T！=Integer.MaxValue
L（j） = T;
If P（j） = Integer.MaxValue && L（j）！=Integer.MaxValue
P（j） = L（j）;
If L（j） = Integer.MaxValue
Exit;
If L（_A.Length - i）！=Integer.MaxValue
for（int j=0;j<n-1;j++）{
tS.Append（_B（P（j）））
}
}
3.算法比较
基于本文设计的三个算法，本文主要文本长度、文本相似度[3]两方面对文本进行比较，结果如表1所示。
LD算法的核心需要两个for循环，其时间复杂度就是O（MN），该算法中利用的矩阵占用空间，所以空间复杂度也是O（MN），不过如果不需要计算出具体的匹配字符串其空间复杂度可以优化到O（M），若两个字符串都是50000字符，则LD矩阵的大小为50000*50000*≈25G。可见该算法不适合比较文本字符串较长的情况。
LCS算法和LD思想上是一致的，两者的区别在于出发点有些不同。
表1 算法比较结果图
算法 文本特征 时间 空间
LD 短文本 18ms O（mn）
LCS 20ms O（mn）
Nakatsu 22ms O（m（n-p+1））
LD 长文本 50ms O（mn）
LCS 49ms O（mn）
Nakatsu 46ms O（m（n-p+1））
LD 相似度高 56ms O（mn）
LCS 55ms O（mn）
Nakatsu 49ms O（m（n-p+1））
LD 相似度低 47ms O（mn）
LCS 49ms O（mn）
Nakatsu 45ms O（m（n-p+1））
Nakatsu算法定义了一个最长公共子序列P，在我们构造的K*M矩阵中需要算出的对角线个数是M-P+1个，每个对角线上数值的计算次数都接近N，故该算法的时间复杂度是O（（N-P+1）M），在矩阵中下三角均不需要计算，在上三角的计算中只要某个对角线有个值是不存在的下面的值就不需要计算，故其空间复杂度是O（P（m-P）），相比较前两种算法该算法确实在空间和时间上有很大的改善。但是其只能求解部分的最长公共子串，不能够求出所有最佳匹配，如果单纯是计算最长公共子串的话，该算法就不能满足要求。
4.结论
经过系列的分析和比较，LD算法和LCS算法比较适合文本字符串短的文本的比较，Nakatsu算法比较合适文本字符串长的文本比较，对于要求出最长匹配子串的文本比较Nakatsu算法仍然是最适合的，但是对于要求出所有的最佳子串匹配，只能用LD和LCS算法，显然这时候的时间和空间上都不占用优势，所以文本比较算法还有待进一步的改善和优化。
参考文献
[1]邓爱萍.程序代码相似度度量算法研究[J].计算机工程与设计，2008，29（17）：4636-4638.
[2]H.M.Deitel，P.J.Deitel JAVA程序设计教程[M].施平安，译.北京：清华大学出版社，2008.
[3]吉胜军.基于Levenshtein distance算法的句子相似度计算[J].电脑知识与技术，2009，5（9）：2177-2178.
[4]王芳芳.基于遗传算法的序列比对方法[J].吉林大学学报（信息科学版），2006，24（4）：423-429.