基于局部最大相似设想的串匹配算法

刘 鹰

（西安文理学院 陕西 西安 710065 ）

在机考自动判卷系统中，如何判断考生输入答案与范文的相似程度是一个核心问题，这可以归结为文本比较算法的设计。

比较两个文本的相似程度，常用的算法有模糊哈希（Fuzzy Hashing）算法、列文斯顿距离（Levenshtein Distance）算法等。

模糊哈希算法主要用于文件的相似性比较，又称基于内容分割的分片哈希算法（Context Triggered Piecewise Hashing，CTPH）。

2006年，Jesse Kornblum[1]提出了模糊哈希算法并给出了一个算法实例。随后，Jason Sherman又开发了一个名为ssdeep的工具软件以实现这一算法。该算法最初用于计算机取证，后来又被用于恶意代码检测，最近又有用于开源软件漏洞挖掘等。

模糊哈希算法的主要原理是使用一个弱哈希函数计算文件局部内容，在特定条件下对文件进行分片，然后使用一个强哈希函数对文件的每个片段计算哈希值，取这些值的一部分并连接起来，与分片条件一起构成一个模糊哈希结果。使用一个字符串相似性对比算法判断两个模糊哈希值的相似度有多少，从而判断两个文件的相似程度。

对文件的部分变化（包括在多处修改、增加、删除部分内容），使用模糊哈希均能发现其与源文件的相似关系，是目前判断相似性较好的一种方法。

列文斯顿距离（Levenshtein Distance）算法[2]用来计算从原串（s）转换到目标串（t）所需要的最少的插入、删除和替换数目。列文斯顿距离亦称编辑距离（Phrase Edit Distance），最早由俄国数学家列文斯顿（Vladimir Levenshtein）提出，在自然语言处理（Natural Language Processing，NLP）中应用比较广泛。

列文斯顿距离算法可以看作一个动态规划，其思路是从两个字符串的左边开始比较，记录已经比较过的子串相似度（即距离），然后进一步得到下一个字符位置时的相似度。

其他文本比较算法还有KMP算法（Knuth-Morris-Pratt)[3]和BM（Boyer-Moore）[4]算法。这两个算法主要用于精确查找。

国内也有一些对文本或字符串比较算法的研究，如北京交通大学的王艳清等[5]和武汉大学信息资源研究中心的李刚等[6]，分别讨论了具体应用环境下的文本或字符串比较算法。

虽然上述算法都是成熟的文本比较算法，也都有广泛的应用，但就盲打机考机考系统的具体问题，都还存在各种具体问题，如模糊哈希算法主要用于文件比较，列文斯顿距离算法用于盲打机考判分时结果不够直观等，对于盲打机考评判这一任务，尚无特别有效的算法可供选择。

因此，在本文引入了最大相似程度的概念，其出发点是认为考生在做打字测试时总是力图犯最少的错误，从而争取更高的分数。据此我们设计了基于局部最大相似设想的串匹配算法。

1 匹配错误产生的原因及其判定算法

在逐字比较范文字符串s和拷贝字符串a的匹配过程中，如果发现拷贝中的某字符ai与范文中的对应字符sj不符，则其原因不外是:

1）复制时误发字符，即本应为sj字符而错发为ai字符。验证方法为跳过ai和sj，比较ai+1和sj+1。若有ai+1= sj+1，则可确认为误发字符(假定错发字符后的复制正确，下同)。

2）复制时多发一字符，即在正确字符前误发某字符。验证方法为跳过ai，比较ai+1和sj。若有ai+1= sj，则可确认为多发字符。

3）复制时漏发一字符，即本该发某字符而未发。验证方法为跳过sj，比较ai和sj+1，若有ai= sj+1，则可确认为漏发字符。

考虑到上述误发、多发和漏发字符均可能连续发生，因此需修正上述验证方法。为此提出下列验证算法。

算法1 求误发字符个数。

errnum1 := 0;

while (ai≠ sj且 i＜alen 且 j＜slen)

{ errnum1 := errnum1+1;

i := i+1; j := j+1;

}

其中slen和alen分别为范文字符串和拷贝字符串的长度。算法结束后，errnum1中存放有误发字符个数。

算法2 求多发字符个数。

errnum2 := 0;

while (ai≠ sj且 i＜alen)

{ errnum2 := errnum2+1;

i := i+1;

}

算法结束后，errnum2中存放有多发字符个数。

算法3 求漏发字符个数。

errnum3 := 0;

while (ai≠ sj且 j＜slen)

{ errnum3 := errnum3+1;

j := j+1;

}

算法结束后，errnum3中存放有漏发字符个数。

上述3个比较算法结束后，都应有ai= sj，此时可以继续进行匹配；或者已经达到了范文字符串或拷贝字符串的尾部，此时匹配结束。

2 最大相似设想及其算法

在实际的复制过程中，上述3种错误可能单独出现，也可能连续发生，还可能以各种方式结合出现。在这种情况下，要确定采用哪个算法来确定实际的错误数并不容易。因此，我们以最大相似设想来指导匹配算法的设计。即在匹配过程中，任何时候如果发现不匹配字符（即 ai≠ sj），则分别按误发、多发和漏发情况进行统计，分别得出假设错误为误发字符时，误发字符个数errnum1，假设错误为多发字符时，多发字符个数errnum2， 已经假设错误为漏发字符时的漏发字符个数errnum3。然后，选择errnum1，errnum2，和errnum3中最小的那一个确定实际的错误类型，并跳过发生错误的部位，继续进行匹配。也就是说，总是假定复制过程中复制操作是尽量准确的，在错误出现时，要按最好情况（错误最少）考虑。

算法4 基于最大相似设想的串匹配算法

i := 0; j := 0; k := 0; err := 0; r = 0;

while(i＜alen 且 j＜slen)

{ if (ai = sj)

{ i := i + 1; j := j + 1; k := k + 1;

}

else

{ 分别求出误发字符数err1，多发字符数err2和漏发字符数err3;

if(误发字符数err1最小)

{ err := err + err1;

i := i + err1; j = j + err1;

}

else if(多发字符数err2最小)

{ err := err + err2;

i := i + err2;

}

else if(漏发字符数err3最小)

{ err := err + err3;

j := j + err3;

}

}

}

r := 100 * (slen – err) / slen;

算法的结果r是复制的保真度。

考虑一个特例，即拷贝字符串的长度为零（相当于交白卷）。因为不会在拷贝字符串中找到错误，上述算法会给出100分！为了防止这种情况，在匹配开始前，如果拷贝字符串a长度小于范文字符串s，则用范文串中没有出现过的字符（如特殊字符“#”等）添加到拷贝字符串后面，直到其长度与范文字符串s相同。

算法1、算法2和算法3在判断错误是否结束时，仅检查一个字符（ ai≠ sj）。实际上这并不可靠，在错误片断中有个别字符和范文中相应位置的字符相同的概率还是很大的，容易造成误判。解决的方法是将检查单个字符换成检查一个连续的小片断，即有：

算法5 片断比较

same := true;

for (k := 0; k ＜ size 且 i ＜ slen 且 j ＜ alen; k++)

{

if (ai≠ sj)

{ same := false;

跳出循环结束比较;

}

i := i+1; j := j+1;

}

其中same是返回值，为真则表示比较成功。size 是预先给定的比较长度。

用上述算法替换算法1、算法2和算法3中的检测条件ai≠ sj。经试验，就打字测试而言，将片断长度size设置为3或4就可取得很好的结果。

3 算法效率

该算法无回溯，在发生错误时向前搜索。因此最坏情况的耗时时间为O(n2)，n为范文字符串长度。实际上，由于常用字符集有限，该算法效率非常高。经实际测试，一般情况下比较运算次数远小于范文字符串长度，即算法实际耗时接近O(n)。该算法无需额外存储空间，即空间效率为O(n)。

4 结 论

对于给定两个文本的相似程度比较，不同的算法会给出不同的结果。本文提出的基于最大相似设想的文本比较算法，对于在文本复制过程中出现的错误，总是选取最优分数作为输出结果。这是由研制开发自动改卷系统提出的问题，主要用于考生盲打试卷的自动评判。经实验，该算法的准确度很高，速度也很快。相信经过适当改进，也可用于数据传输质量判断等其他场合。采用本算法的自动判卷系统在 .NET 环境下用C#编程实现。

[1] Jesse Kornblum. Identifying almost identical files using context triggered piecewise hashing[J]. Digital Investigation，2006:91-97.

[2] Wagner，Robert A,Fischer，Michael J. The String-to-String Correction Problem[J]. Journal of the ACM 21,1974(1): 168-173.

[3] Knuth,Donald.The Art of Computer Programming，Volume 3:Sorting and Searching[M]. Second Edition.Reading,Massachusetts: Addison-Wesley, 1998.

[4] Robert S,Moore, Strother J .A Fast String Searching Algorithm[J]. Comm. ACM :New York, NY, USA: Association for Computing Machinery,1977,20 (10): 762-772.

[5] 王艳清，王云维.监控文本文件内容变化的文本比较算法[J].计算机应用, 2010，30（S1）: 133-135.WANG Yan-qing, WANG Yun-wei. Text comparison algorithm for detecting content change in text files[J]. Journal of Computer Applications, 2010, 30(S1):133-135.

[6] 李纲，夏晨曦，郑重.局部文本特征选取算法的比较和改进研究[J].情报学报，2008,27（4）: 506-511.LI Gang, XIA Chen-xi, ZHENG Zhong. A comparative and improving study of local feature selection algorithms in Text Categorization[J]. Journal of the China Society for Scientific and Technical Information, 2008, 27(4): 506-511.