基于Levenshtein算法的题库相似度检测算法的设计与改进

胡玉琦

（职工教育培训中心 太原钢铁（集团）公司，太原 030003）

基于Levenshtein算法的题库相似度检测算法的设计与改进

胡玉琦

（职工教育培训中心 太原钢铁（集团）公司，太原 030003）

为快速找到题库中题干重复题或相似度很高的试题，利用java Excel ARI类配合Levenshtein Distance算法实现直接访问excel题库，设计了题库重复题检测算法。在实际使用过程中发现Levenshtein算法存在内存超限，检测结果输出越界等问题，采用字符串分割法及增加控制语句的方式进行改进，获得了良好的实际使用效果。

Levenshtein算法；重复题；字符串分割

随着在线考试的普及，越来越多的企业把线下考试转移到线上，为实现在线考试，需要开发大量各种类型，各种专业的试题库。大量的题库题干内容不可避免存在相似度很高的重复题，目前已有很多种检测重复题的算法，文献［1］利用空间向量模型，通过TF-IDF公式得到试题的文本权重向量，通过余弦理论计算试题相似度。文献［2］利用同义词库将词标准化及分层比较得出相似度。文献［3-4］基于Levenshtein算法对两个句子进行检测，Levenshtein算法在DNA分析，拼字检查，语音辨识，抄袭侦测等领域有着广泛的应用，文献［5-6］结合了编辑距离和词性、语义含义进行相似度检测，有一定应用价值。本文应用Levenshtein算法重复题检测，设计了检测算法，使用过程中，发现了该算法存在的弊端，并提出可行的解决办法。

1 Levenshtein算法概述

Levenshtein算法［7］，即编辑距离算法，是首先由俄国科学家Vladimir Levenshtein在1965年提出的，所以该算法也叫Levenshtein Distance，它是指由一个字符串转换为另一个字符串，使两个字符串完全一样时，需要的编辑操作次数为最少，算法允许的编辑操作可以是一个字符被替换成另一个字符、在第二个字符串里插入一个字符或在第二个字符串中删除一个字符。

算法定义是给出字符串1用str 1表示，字符串2用str 2表示，2个字符串的长度分别是s和t，构造一个矩阵distance，（s+1）×（t+1），其中第一行写上0～s，第一列写上0～t。给矩阵的每个元素赋值，赋值规则如下，如果矩阵当前元素指向的str1和str2中的元素相同，那么设price为0否则为1。比较矩阵当前赋值元素（current）的左边的值（left-value），上面的值（top-value），左上角的值（top-left-corner-value），比较3个值计算出最小值min-value。如果min-value是top-value或left -value中的一个，那么current=min-value+1.否则current=min-value+price。

按顺序给矩阵每个元素赋值，distance［s］［t］就是两个字符串的编辑距离。

这里假设str 1=“ABC”，str 2=“ABD”，长度本别为3。

则str 1与str 2的距离矩阵如表1所示。

从矩阵中可以获得计算相似度的距离值，设两个字符串长度的最大值为max（s，t），

则相似度=1-（distance［s］［t］/max（s，t））。

Str 1与str 2的相似度为：相似度（str 2，str 2）=1-（1/3）=1-0.333=0.667

2 题库访问与检测结果输出

2.1 题库结构设计

目前题库建设大多使用excel编辑，内容涵盖了题干、题型、答案选项，正确答案等信息。每道题占用excel一行，题库安照excel行的方式进行组织排列如表2所示。

2.2 Excel API概述

2.2.1 Excel AP介绍

本文采用的技术是使用jxl.jar类实现JAVA程序中访问excel题库内容［8］。Java Excel是一个开放源码项目［8］，通过它Java使用者可以利用其提供的类、对象、方法读取Excel工作簿及工作表的内容、生成新的Excel工作簿和工作表、对已有的Excel工作簿和工作表进行更新操作。由于java是跨平台开发工具，所以使用该ARI创建的程序也可以部署在web应用中，可以通过JSR或Servlet来调用该ARI实现对Excel工作簿和工作表的操作。即使web应用是在linux环境下部署的，该程序也能够正常处理excel工作簿和工作表。该ARI访问支持Excel 95-2000的所有版本，创建生成Excel的版本为2000标准格式。该ARI支持工作表中的字符、数字、字体、日期等操作与设置；可以修饰单元格属性；支持图像和图表的访问，但格式限于png格式；所以该ARI能够满足我们对excel工作簿和工作表操作、访问、跟新的基本需要。

2.2.2 Excel API的安装

该ARI包含JXL.JAR文件，将JXL.JAR复制到%JAVA-HOME%jreext文件夹下面，在CLASSRATH变量里面添加“%JAVA-HOME%jreext”，然后就可以调用JExcelARI了。如果出现编译报错“找不到java.jxl包”，则可能是没有设置成功。这时，如果有Eclipse开发工具，可以在“Build Rath”中添加“External Library”，找到jxl.jar的路径，然后就能编译成功了。

2.3 题干访问与输出

2.3.1 题干访问

通过jxl.jar类中的Workbook对象类的getWorkbook方法进行访问［8］。Workbook book=Workbook. getWorkbook（new File（″test.xls″））；这里的“test.xls”为需要进行相似度检测的题库所在的文件；book为需要访问的新创建的实例。Sheet sheet=book.get Sheet（0）；创建book实例中需访问的工作表sheet。int h=sheet.getRows（）；这里定义h，读取sheet（第一个表的sheet1里面的行数）的行数赋值给h。

2.3.2 检测结果输出

通过jxl.jar类中的WritableWorkbook对象类的createWorkbook方法进行访问。WritableWorkbookbook 1=Workbook.createWorkbook（new File（″检测结果.xls″））；这里的“检测结果.xls”为需要进行相似度检测的题库所在的文件；book 1为需要访问的新创建的实例，该实例为允许写入。WritableSheet sheet1=book 1.createSheet（″检测结果″，0）； 定义了具体输出写入的工作表并确定工作表名称为“检测结果”。

3 检测算法设计与改进

3.1 算法设计

假设题干有n条记录，即excel题干的行数为n，则题干相互进行比较检测，每次比较检测均使用Levenshtein算法，需要检测次数

算法中采用3个变量进行循环控制，题干所在excel文件中，用x表示字符串str1所在行号，范围为1～n；y表示str 2所在行号，范围为n～x；str1与str 2进行相似度比较的结果xsd=Levenshtein（str 1，str 2）输出到另一个excel文件中，命名为“检测结果.xls”，通过f控制输出位置。

3.2 存在问题及改进方法

3.2.1 Levenshtein算法存在的问题及改进。

Levenshtein算法在执行时，系统会根据字符串str 1与str 2长度开辟内存空间，内存空间大小为字符串str 1的长度与字符串str 2的长度乘积，即Memory-space=len（str 1）×len（str 2）。由于字符串1个字符占1个字节空间，所以如果字符串str 1与字符串str 2长度都是1 000个字符，那么生成的这个矩阵占内存空间会是1 M；如果2个字符串都是10 000个字符，那么矩阵占用内存空间就是100 M。实际检测过程中如遇题干内容过长，则内存占用明显增加，有时出现死锁现象。

为解决该问题，我们将准备检测的字符串str 1和str 2分别进行分割，分割为系统允许的长度，该长度的确定则根据我们允许为该算法分配的内存空间确定。根据执行主机剩余内存大小，确定执行该算法最大空间。如计划给该算法分配最大5M内存空间，则分割的长度应该为72，按照该长度对准备检测的字符串进行分割，分割后的子串用str 1n和str 2n表示，这里n的值为字符串分割后的子串的数量。分别对str 1n和str 2n进行检测，得到xsdn=Levenshtein（str 1n，str 2n），然后对xsdn进行加权平均，得到

假设str A=”abcdfrgghyds”；str B=”abdcsrgrhuds”；设定n=3，则分别对str A和str B进行分割处理，得到如下字串，str A1=”abcd”，str A2=”frgg”，str A3=”hyds”；str B1=”abdc”，str B2=”srgr”，str B3=”huds”。

分别对原str A与str B进行检测，得到xsd（str A，str B）=Levenshtein（str A，str B）=0.583 34。

对str A1与str B1进行检测，得到xsd（str A1，str B1）=Levenshtein（str A1，str B1）=0.5。

对str A2与str B2进行检测，得到xsd（str A2，str B2）=Levenshtein（str A2，str B2）=0.5。

对str A3与str B3进行检测，得到xsd（str A3，str B3）=Levenshtein（str A3，str B3）=0.75。

Xsd（分割后）=（0.5+0.5+0.75）/3=0.583 33。

Xsd（分割后）≈Xsd（分割前）。

经过实际检测，虽然分割检测结果与未分割检测结果存在一定微小误差，但分割后进行检测与分割前检测进行比较，占用内存空间明显减少，运行效率有明显质的提升，在实际题库重复题检测工作中，微小误差在允许范围内，不影响实际检测结果。

3.2.2 检测过程存在的问题及改进

由于题库数量不确定，当题库题干数量增加时，检测次数会非常大，由于输出excel行最大值为65 536，则根据检测次数公式（n-1）×（n-2）/2计算得出n的值最大值越为362，所以题库数量不能超过362，否则检测结果无法正常输出即超出excel最大行数。如算法中当变量t的值超出65 536时，停止检测，这样会造成停止检测后题库得不到检测结果。另一种办法是，将相似的小于设定值的检测结果丢弃，这样可以很大程度上降低输出数量，在实际题库检测过程中我们规定相似度超过0.8的试题，我们认定为重复题，所以我们将相似度小于0.8的结果丢弃，只将相似度超过0.8的结果输出，这样检测结果输出超限的概率降到最低，提升了检测效率，的到良好的效果。算法中实现方法为增加一个控制语句if（xsd＞=0.8）则进行输出操作，否则不执行输出操作。

4 结语

本文就Levenshtein Distance算法进行了简要介绍，在该算法基础上设计了题库相似度检测算法，实际应用过程中发现了算法在特定条件下存在的问题，通过分割的方法及增加控制语句加以改进，取得了良好的效果。

［1］ 汪忠国，吴敏.基于向量空间模型的题库相似度检查算法［J］.计算机系统应用，2010，19（3）：213-217.

［2］ 黄玲莉，吴国新.中文文档相似度检测技术的研究与应用［J/OL］.中国科技论文在线//百度文库.（2010-12-12）［2014-4-1］.http：//wenku.baidu.com/link?url=w6t-fd8zBiqk IojGhgIeoAqyJKXHwxLxonhNuQ76rc3EUgEdG6CtK94-A19 fgF5xntVjfvZhZGb-QUYndd99ZMe-w35TXObdCzB3-fL-sD-.

［3］ 吉胜军.基于Levenshtein distance算法的句子相似度计算［J］.电脑知识与技术，2009，5（9）：2177-2178.

［4］ 赵作鹏，尹志民，王潜平，等.一种改进的编辑距离算法及其在数据处理中的应用［J］.计算机应用，2009，29（2）：424.

［5］ 梅莜，刘海鹏.基于编辑距离结合词性的词相似度算法［J/OL］.中国科技论文在线//百度文库.（2010-05-03）［2014-4-1］.http：//wenku.baidu.com/view/30e34b0df78a6529647d531b.html

［6］ 车万祥，刘挺，秦兵，等.基于改进编辑距离的中文相似句子检索［J］.高技术通信，2004，1639（14）：15-19.

［7］ 佚名.计算字符串相似度算法—Levenshtein［EB/OL］.（2012-01-13）［2014-4-1］.http：//wdhdmx.iteye.com/blog/1343856.

［8］ 百度文库.Java-Excel-ARI简易教程［EB/OL］.（2011-03-04）［2014-4-1］.http：//wenku.baidu.com/link?url=rjh-kWFfutFfuhdJT7411mfvsg1Zkm1ii7AWRRbtQvpE5h5qIOM3Ld24IEgRIjDb8QiWp9pub4Mf-2RT-D7e5hZH36tcV8r4fFd9vAn4RgW.

Design and Improvement of Detection Algorithm for Similarity of Questions Bank Based on Levenshtein Algorithm

HU Yu-qi
（Employee Training and Education Center，Taiyuan Iron&Steel（Group）Co.，LTD，Taiyuan 030003，China）

To find High similarity of question Bank quickly，Detection algorithm is designed with java Excel ARI.But there is possible phenomenon，such asmemory limit，outputbounds of test results，etc.in the actual use of the process.In order to solve these problems，we use String segmentationmethod and increase Control statement to get good effect.

Levenshtein Algorithm；Repetitive question；String segmentation method

TR311

A

：1009-0312（2014）05-0057-04

2014-04-01

胡玉琦（1976—），男，山西平定人，工程师，实验师，硕士，主要从事数据挖掘研究。