基于Levenshtein算法的題庫相似度檢測算法的設(shè)計與改進

胡玉琦

（職工教育培訓(xùn)中心 太原鋼鐵（集團）公司，太原 030003）

基于Levenshtein算法的題庫相似度檢測算法的設(shè)計與改進

胡玉琦

（職工教育培訓(xùn)中心 太原鋼鐵（集團）公司，太原 030003）

為快速找到題庫中題干重復(fù)題或相似度很高的試題，利用java Excel ARI類配合Levenshtein Distance算法實現(xiàn)直接訪問excel題庫，設(shè)計了題庫重復(fù)題檢測算法。在實際使用過程中發(fā)現(xiàn)Levenshtein算法存在內(nèi)存超限，檢測結(jié)果輸出越界等問題，采用字符串分割法及增加控制語句的方式進行改進，獲得了良好的實際使用效果。

Levenshtein算法；重復(fù)題；字符串分割

隨著在線考試的普及，越來越多的企業(yè)把線下考試轉(zhuǎn)移到線上，為實現(xiàn)在線考試，需要開發(fā)大量各種類型，各種專業(yè)的試題庫。大量的題庫題干內(nèi)容不可避免存在相似度很高的重復(fù)題，目前已有很多種檢測重復(fù)題的算法，文獻［1］利用空間向量模型，通過TF-IDF公式得到試題的文本權(quán)重向量，通過余弦理論計算試題相似度。文獻［2］利用同義詞庫將詞標(biāo)準化及分層比較得出相似度。文獻［3-4］基于Levenshtein算法對兩個句子進行檢測，Levenshtein算法在DNA分析，拼字檢查，語音辨識，抄襲偵測等領(lǐng)域有著廣泛的應(yīng)用，文獻［5-6］結(jié)合了編輯距離和詞性、語義含義進行相似度檢測，有一定應(yīng)用價值。本文應(yīng)用Levenshtein算法重復(fù)題檢測，設(shè)計了檢測算法，使用過程中，發(fā)現(xiàn)了該算法存在的弊端，并提出可行的解決辦法。

1 Levenshtein算法概述

Levenshtein算法［7］，即編輯距離算法，是首先由俄國科學(xué)家Vladimir Levenshtein在1965年提出的，所以該算法也叫Levenshtein Distance，它是指由一個字符串轉(zhuǎn)換為另一個字符串，使兩個字符串完全一樣時，需要的編輯操作次數(shù)為最少，算法允許的編輯操作可以是一個字符被替換成另一個字符、在第二個字符串里插入一個字符或在第二個字符串中刪除一個字符。

算法定義是給出字符串1用str 1表示，字符串2用str 2表示，2個字符串的長度分別是s和t，構(gòu)造一個矩陣distance，（s+1）×（t+1），其中第一行寫上0～s，第一列寫上0～t。給矩陣的每個元素賦值，賦值規(guī)則如下，如果矩陣當(dāng)前元素指向的str1和str2中的元素相同，那么設(shè)price為0否則為1。比較矩陣當(dāng)前賦值元素（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］就是兩個字符串的編輯距離。

這里假設(shè)str 1=“ABC”，str 2=“ABD”，長度本別為3。

則str 1與str 2的距離矩陣如表1所示。

從矩陣中可以獲得計算相似度的距離值，設(shè)兩個字符串長度的最大值為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 題庫訪問與檢測結(jié)果輸出

2.1 題庫結(jié)構(gòu)設(shè)計

目前題庫建設(shè)大多使用excel編輯，內(nèi)容涵蓋了題干、題型、答案選項，正確答案等信息。每道題占用excel一行，題庫安照excel行的方式進行組織排列如表2所示。

2.2 Excel API概述

2.2.1 Excel AP介紹

本文采用的技術(shù)是使用jxl.jar類實現(xiàn)JAVA程序中訪問excel題庫內(nèi)容［8］。Java Excel是一個開放源碼項目［8］，通過它Java使用者可以利用其提供的類、對象、方法讀取Excel工作簿及工作表的內(nèi)容、生成新的Excel工作簿和工作表、對已有的Excel工作簿和工作表進行更新操作。由于java是跨平臺開發(fā)工具，所以使用該ARI創(chuàng)建的程序也可以部署在web應(yīng)用中，可以通過JSR或Servlet來調(diào)用該ARI實現(xiàn)對Excel工作簿和工作表的操作。即使web應(yīng)用是在linux環(huán)境下部署的，該程序也能夠正常處理excel工作簿和工作表。該ARI訪問支持Excel 95-2000的所有版本，創(chuàng)建生成Excel的版本為2000標(biāo)準格式。該ARI支持工作表中的字符、數(shù)字、字體、日期等操作與設(shè)置；可以修飾單元格屬性；支持圖像和圖表的訪問，但格式限于png格式；所以該ARI能夠滿足我們對excel工作簿和工作表操作、訪問、跟新的基本需要。

2.2.2 Excel API的安裝

該ARI包含JXL.JAR文件，將JXL.JAR復(fù)制到%JAVA-HOME%jreext文件夾下面，在CLASSRATH變量里面添加“%JAVA-HOME%jreext”，然后就可以調(diào)用JExcelARI了。如果出現(xiàn)編譯報錯“找不到j(luò)ava.jxl包”，則可能是沒有設(shè)置成功。這時，如果有Eclipse開發(fā)工具，可以在“Build Rath”中添加“External Library”，找到j(luò)xl.jar的路徑，然后就能編譯成功了。

2.3 題干訪問與輸出

2.3.1 題干訪問

通過jxl.jar類中的Workbook對象類的getWorkbook方法進行訪問［8］。Workbook book=Workbook. getWorkbook（new File（″test.xls″））；這里的“test.xls”為需要進行相似度檢測的題庫所在的文件；book為需要訪問的新創(chuàng)建的實例。Sheet sheet=book.get Sheet（0）；創(chuàng)建book實例中需訪問的工作表sheet。int h=sheet.getRows（）；這里定義h，讀取sheet（第一個表的sheet1里面的行數(shù)）的行數(shù)賦值給h。

2.3.2 檢測結(jié)果輸出

通過jxl.jar類中的WritableWorkbook對象類的createWorkbook方法進行訪問。WritableWorkbookbook 1=Workbook.createWorkbook（new File（″檢測結(jié)果.xls″））；這里的“檢測結(jié)果.xls”為需要進行相似度檢測的題庫所在的文件；book 1為需要訪問的新創(chuàng)建的實例，該實例為允許寫入。WritableSheet sheet1=book 1.createSheet（″檢測結(jié)果″，0）； 定義了具體輸出寫入的工作表并確定工作表名稱為“檢測結(jié)果”。

3 檢測算法設(shè)計與改進

3.1 算法設(shè)計

假設(shè)題干有n條記錄，即excel題干的行數(shù)為n，則題干相互進行比較檢測，每次比較檢測均使用Levenshtein算法，需要檢測次數(shù)

算法中采用3個變量進行循環(huán)控制，題干所在excel文件中，用x表示字符串str1所在行號，范圍為1～n；y表示str 2所在行號，范圍為n～x；str1與str 2進行相似度比較的結(jié)果xsd=Levenshtein（str 1，str 2）輸出到另一個excel文件中，命名為“檢測結(jié)果.xls”，通過f控制輸出位置。

3.2 存在問題及改進方法

3.2.1 Levenshtein算法存在的問題及改進。

Levenshtein算法在執(zhí)行時，系統(tǒng)會根據(jù)字符串str 1與str 2長度開辟內(nèi)存空間，內(nèi)存空間大小為字符串str 1的長度與字符串str 2的長度乘積，即Memory-space=len（str 1）×len（str 2）。由于字符串1個字符占1個字節(jié)空間，所以如果字符串str 1與字符串str 2長度都是1 000個字符，那么生成的這個矩陣占內(nèi)存空間會是1 M；如果2個字符串都是10 000個字符，那么矩陣占用內(nèi)存空間就是100 M。實際檢測過程中如遇題干內(nèi)容過長，則內(nèi)存占用明顯增加，有時出現(xiàn)死鎖現(xiàn)象。

為解決該問題，我們將準備檢測的字符串str 1和str 2分別進行分割，分割為系統(tǒng)允許的長度，該長度的確定則根據(jù)我們允許為該算法分配的內(nèi)存空間確定。根據(jù)執(zhí)行主機剩余內(nèi)存大小，確定執(zhí)行該算法最大空間。如計劃給該算法分配最大5M內(nèi)存空間，則分割的長度應(yīng)該為72，按照該長度對準備檢測的字符串進行分割，分割后的子串用str 1n和str 2n表示，這里n的值為字符串分割后的子串的數(shù)量。分別對str 1n和str 2n進行檢測，得到xsdn=Levenshtein（str 1n，str 2n），然后對xsdn進行加權(quán)平均，得到

假設(shè)str A=”abcdfrgghyds”；str B=”abdcsrgrhuds”；設(shè)定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（分割前）。

經(jīng)過實際檢測，雖然分割檢測結(jié)果與未分割檢測結(jié)果存在一定微小誤差，但分割后進行檢測與分割前檢測進行比較，占用內(nèi)存空間明顯減少，運行效率有明顯質(zhì)的提升，在實際題庫重復(fù)題檢測工作中，微小誤差在允許范圍內(nèi)，不影響實際檢測結(jié)果。

3.2.2 檢測過程存在的問題及改進

由于題庫數(shù)量不確定，當(dāng)題庫題干數(shù)量增加時，檢測次數(shù)會非常大，由于輸出excel行最大值為65 536，則根據(jù)檢測次數(shù)公式（n-1）×（n-2）/2計算得出n的值最大值越為362，所以題庫數(shù)量不能超過362，否則檢測結(jié)果無法正常輸出即超出excel最大行數(shù)。如算法中當(dāng)變量t的值超出65 536時，停止檢測，這樣會造成停止檢測后題庫得不到檢測結(jié)果。另一種辦法是，將相似的小于設(shè)定值的檢測結(jié)果丟棄，這樣可以很大程度上降低輸出數(shù)量，在實際題庫檢測過程中我們規(guī)定相似度超過0.8的試題，我們認定為重復(fù)題，所以我們將相似度小于0.8的結(jié)果丟棄，只將相似度超過0.8的結(jié)果輸出，這樣檢測結(jié)果輸出超限的概率降到最低，提升了檢測效率，的到良好的效果。算法中實現(xiàn)方法為增加一個控制語句if（xsd＞=0.8）則進行輸出操作，否則不執(zhí)行輸出操作。

4 結(jié)語

本文就Levenshtein Distance算法進行了簡要介紹，在該算法基礎(chǔ)上設(shè)計了題庫相似度檢測算法，實際應(yīng)用過程中發(fā)現(xiàn)了算法在特定條件下存在的問題，通過分割的方法及增加控制語句加以改進，取得了良好的效果。

［1］ 汪忠國，吳敏.基于向量空間模型的題庫相似度檢查算法［J］.計算機系統(tǒng)應(yīng)用，2010，19（3）：213-217.

［2］ 黃玲莉，吳國新.中文文檔相似度檢測技術(shù)的研究與應(yīng)用［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］.電腦知識與技術(shù)，2009，5（9）：2177-2178.

［4］ 趙作鵬，尹志民，王潛平，等.一種改進的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用［J］.計算機應(yīng)用，2009，29（2）：424.

［5］ 梅莜，劉海鵬.基于編輯距離結(jié)合詞性的詞相似度算法［J/OL］.中國科技論文在線//百度文庫.（2010-05-03）［2014-4-1］.http：//wenku.baidu.com/view/30e34b0df78a6529647d531b.html

［6］ 車萬祥，劉挺，秦兵，等.基于改進編輯距離的中文相似句子檢索［J］.高技術(shù)通信，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—），男，山西平定人，工程師，實驗師，碩士，主要從事數(shù)據(jù)挖掘研究。