冉崇善+邵春霞

摘 要：隨著在線教育平臺(tái)的興起，為了解決大量試題帶來的存儲(chǔ)開支問題，試題查重技術(shù)應(yīng)運(yùn)而生。提出將改進(jìn)的Simhash算法應(yīng)用到試題查重中，首先根據(jù)結(jié)巴分詞技術(shù)將試題文本進(jìn)行切分，然后根據(jù)TF-IDF技術(shù)并結(jié)合詞語的詞性及詞長算出關(guān)鍵詞權(quán)重，以期達(dá)到對(duì)Simhash簽名值的精確計(jì)算，最后通過帶有索引功能的海明距離檢測出相似試題。實(shí)驗(yàn)結(jié)果驗(yàn)證了此方案的可行性。

關(guān)鍵詞：試題查重；Simhash算法；海明距離；簽名值

DOIDOI：10.11907/rjdk.172357

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0151-03

0 引言

隨著互聯(lián)網(wǎng)的普及，信息化技術(shù)已經(jīng)與人類的日常生活息息相關(guān)，它不僅影響了人類的生活方式，還能引起教育變革。我國《義務(wù)教育課程標(biāo)準(zhǔn)》明確指出：“為了給學(xué)生創(chuàng)設(shè)良好的學(xué)習(xí)條件，促進(jìn)學(xué)生主動(dòng)學(xué)習(xí)，更好地理解和掌握學(xué)習(xí)內(nèi)容，提高學(xué)習(xí)效率，教育工作者應(yīng)積極開發(fā)和利用各種課程資源”[1]。因此，在線教育產(chǎn)品成為全球化發(fā)展的趨勢(shì)和必然。在各在線教育平臺(tái)興起的同時(shí)，由于提供給學(xué)生的試題知識(shí)點(diǎn)不斷增長，這無疑會(huì)造成在線教育平臺(tái)的存儲(chǔ)開支問題。研究發(fā)現(xiàn)，在試題庫中有大量相似或相同試題，也即是說，有相當(dāng)一部分試題的核心內(nèi)容相同，試題庫中只存儲(chǔ)一道此類型的題目即可。否則，隨著時(shí)間推移，這種相似試題造成的存儲(chǔ)成本問題將變得越來越嚴(yán)重。因此，試題查重技術(shù)的研究將發(fā)揮重要作用。通過該查重技術(shù)希望可以達(dá)到識(shí)別冗余數(shù)據(jù)的目的，從而大大降低存儲(chǔ)成本，縮減不必要的存儲(chǔ)開支。

Simhash算法是一種用于識(shí)別試題題目信息是否相似的算法，可以粗粒度地識(shí)別試題庫中的冗余部分。通過Simhash算法識(shí)別試題庫中存在的重復(fù)數(shù)據(jù)，并使用python語言刪除重復(fù)試題信息，可實(shí)現(xiàn)相同試題只被存儲(chǔ)一次的理想狀態(tài)。一般情況下，單個(gè)試題的簽名值可以通過哈希函數(shù)算出，但是不同程度的碰撞問題也隨之出現(xiàn)，即使試題不同也有可能出現(xiàn)簽名值相同的情況。

針對(duì)該問題，本文研究了一種改進(jìn)的Simhash算法，由于目前Simhash算法的關(guān)鍵詞權(quán)重計(jì)算是基于單詞出現(xiàn)的頻率，并未考慮到詞性及詞長，本文通過引入TF-IDF技術(shù)以及考慮到關(guān)鍵詞的詞性與詞長等因素，計(jì)算出關(guān)鍵詞權(quán)重，從而增加Simhash簽名值計(jì)算的準(zhǔn)確性，然后通過使用帶有索引功能的海明距離檢測試題之間的相似程度。最后通過實(shí)驗(yàn)，驗(yàn)證了該方案的可行性。

1 相關(guān)技術(shù)

1.1 結(jié)巴分詞技術(shù)

結(jié)巴分詞是一個(gè)使用python語言進(jìn)行中文分詞的模塊，可以使用其進(jìn)行關(guān)鍵詞抽取。本文使用結(jié)巴分詞對(duì)輸入的試題進(jìn)行切分，它主要具有三大特性：

（1）結(jié)巴分詞是使用Trie樹結(jié)構(gòu)實(shí)現(xiàn)高效的字詞掃描，生成試題中漢字所有可能組成詞語情況構(gòu)成的有向無環(huán)圖（DAG）。根據(jù)Trie樹結(jié)構(gòu)的詞圖掃描，將結(jié)巴分詞自帶的2萬多條詞語放到一個(gè)Trie樹中，而Trie樹是指前綴樹，即一個(gè)詞語前幾個(gè)字一樣則表示它們具有相同前綴，具有相同前綴字則可使用Trie樹存儲(chǔ)。Trie樹具有查找速度快的優(yōu)勢(shì)[2]。

（2）結(jié)巴分詞采用動(dòng)態(tài)規(guī)劃查找最大概率路徑，從而找出基于詞頻的最大切分組合[5]。動(dòng)態(tài)規(guī)劃中，先查找待分詞句子中已切分好的詞語出現(xiàn)的頻率，如果沒有該詞，則把詞典中出現(xiàn)頻率最小詞語的頻率作為該詞的頻率，然后根據(jù)動(dòng)態(tài)規(guī)劃查找最大概率路徑的方法，對(duì)句子從右往左反向計(jì)算最大概率，從而得到最大概率的切分組合。

（4）結(jié)巴分詞對(duì)于未登錄詞，采用基于漢字成詞能力的HMM模型，并使用Viterbi算法。中文詞匯按照BEMS 4個(gè)狀態(tài)標(biāo)記，B表示開始位置，E表示結(jié)束位置，M表示中間位置，S表示單獨(dú)成詞的位置。

根據(jù)結(jié)巴分詞的特性，可以得到其工作的一個(gè)大體流程。首先，結(jié)巴分詞需要加載字典，生成Trie樹；然后，給待分詞的試題文本使用正則表達(dá)式獲取連續(xù)的中文字符和英文字符切分成的短語列表，對(duì)每個(gè)短語使用動(dòng)態(tài)規(guī)劃得到最大概率路徑，對(duì)DAG中沒有在字典中查到的字組成一個(gè)新短語，并對(duì)于這些新生成的詞語使用HMM模型進(jìn)行分詞，即識(shí)別字典外的新詞；最后，使用python的yield語法生成一個(gè)詞語生成器，逐個(gè)返回所需的關(guān)鍵詞。

1.2 Simhash算法介紹

Simhash算法是通過將文本轉(zhuǎn)化為n位簽名，然后通過比較文本簽名值的海明距離計(jì)算文本相似度的算法[3]。本文提出將Simhash算法應(yīng)用于相似試題信息的檢測識(shí)別中，相似試題信息的檢測通?？梢苑譃閮蓚€(gè)階段：單個(gè)試題Simhash簽名值的計(jì)算階段和試題之間Simhash簽名值的匹配階段。在簽名值計(jì)算的分詞階段，本文使用結(jié)巴分詞技術(shù)，選出具有代表性的關(guān)鍵詞為Simhash簽名值的精確計(jì)算作鋪墊。在關(guān)鍵詞的權(quán)重計(jì)算過程中，不僅要考慮該關(guān)鍵詞出現(xiàn)的頻率，還要綜合考慮名詞、動(dòng)詞、形容詞等重要詞性及詞長，同時(shí)把經(jīng)典的TF-IDF計(jì)算方式應(yīng)用于Simhash算法當(dāng)中，通過對(duì)關(guān)鍵詞權(quán)重的考慮改進(jìn)Simhash算法以達(dá)到試題精確檢測的目的[4]。Simhash算法工作流程如圖1所示。

1.2.1 Simhash簽名值計(jì)算

本文采用TF-IDF權(quán)值計(jì)算技術(shù)，同時(shí)考慮詞性、詞長等因素計(jì)算關(guān)鍵詞權(quán)重，代替?zhèn)鹘y(tǒng)Simhash算法以分詞識(shí)別出來的關(guān)鍵詞作為特征值，以及以關(guān)鍵詞出現(xiàn)頻率作為權(quán)重的計(jì)算方法[5]。TF-IDF是一種用于評(píng)估一個(gè)關(guān)鍵詞對(duì)于一個(gè)文件重要程度的統(tǒng)計(jì)方法，關(guān)鍵詞的重要性與其在文件中出現(xiàn)的次數(shù)成正比，與在語料庫中出現(xiàn)的次數(shù)成反比[6]。本文是研究對(duì)某一試題庫中相似試題的檢測，試題題目相當(dāng)于一個(gè)短文本，所以可以將TF-IDF權(quán)值技術(shù)應(yīng)用于試題查重中。TF-IDF計(jì)算過程如下：在一份給定的試題中，詞頻是指某一個(gè)給定詞語在該試題中出現(xiàn)的頻率。對(duì)于在某一特定試題題目信息中的關(guān)鍵詞而言，它對(duì)于整個(gè)試題的重要程度可表示為：endprint

其中，ni，j是該詞在試題中的出現(xiàn)次數(shù)，而∑knk，j則是在試題庫中所有字詞的出現(xiàn)次數(shù)之和。逆向文件頻率是一個(gè)關(guān)鍵詞重要程度的度量。對(duì)于某一特定的IDF，可以由總試題數(shù)目除以包含該詞語的文件數(shù)目，再將得到的商取對(duì)數(shù)得到：

其中，|D|是語料庫中的文件總數(shù)，{j：ti∈dj}表示包含詞語的文件數(shù)目（即ti的文件數(shù)目），如果該詞語不在語料庫中，則會(huì)導(dǎo)致被除數(shù)為零。因此，一般情況下使用1+{ti∈dj}。最后試題信息的權(quán)重可表示如下：

詞頻雖然可以作為研究試題題目特征的一個(gè)重要指標(biāo)，但是僅以頻率作為權(quán)重，而沒有考慮詞性及詞長，還是不能全面表示出試題特征，造成Simhash簽名值計(jì)算結(jié)果不精確[7]。因?yàn)樵囶}題目的特征往往與詞語的詞性與詞長有著不可分割的關(guān)系，所以在引入TF-IDF技術(shù)的同時(shí)，本文也通過考慮關(guān)鍵詞的詞性與詞長，精確計(jì)算試題的Simhash簽名值。根據(jù)經(jīng)驗(yàn)判斷，名詞表征著文檔更多特征，動(dòng)詞次之，形容詞再次之，其余最低。結(jié)合場景，并運(yùn)用專家意見法即德爾菲法（Delphi Method）得出權(quán)重系數(shù)[8]，如表1所示。

另外，在詞長方面，根據(jù)對(duì)2008年度CSSCI關(guān)鍵詞庫中的關(guān)鍵詞長進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)4～6個(gè)字組成的詞成為關(guān)鍵詞的概率較高[9]。因此，試題文本中的權(quán)重計(jì)算公式則變?yōu)椋?/p>

其中，λ為參數(shù)，取值與試題文本的長度有關(guān)，Len（ωi）定義如下：

因此，綜合試題信息各個(gè)關(guān)鍵詞的詞頻、詞性以及詞長，能夠更加準(zhǔn)確地計(jì)算出試題關(guān)鍵詞的權(quán)重，全面表示出試題特征，使計(jì)算出的Simhash簽名值更加精確。

1.2.2 Simhash簽名值匹配階段

試題信息相似性的判斷是通過計(jì)算試題之間Simhash簽名值的海明距離進(jìn)行判斷的[10]。簽名值使用二進(jìn)制數(shù)表示，海明距離是指兩個(gè)碼字的對(duì)應(yīng)比特取值不同的比特?cái)?shù)，也即是說，兩個(gè)二進(jìn)制數(shù)異或之后，1的個(gè)數(shù)即為海明距離。對(duì)試題查重而言，則變成根據(jù)Simhash算出單個(gè)試題的簽名值后，再計(jì)算兩個(gè)試題簽名的海明距離即可。根據(jù)經(jīng)驗(yàn)，對(duì)64位的Simhash而言，海明距離在3以內(nèi)的兩個(gè)試題可以認(rèn)為其相似。假設(shè)對(duì)64位的Simhash，要尋找海明距離在3以內(nèi)的所有簽名，可以把64位的二進(jìn)制簽名均分成4塊，每塊16位。根據(jù)鴿巢原理可知，如果兩個(gè)簽名值的海明距離在3以內(nèi)，那么它們必有一塊是相同。由上可知，海明距離的計(jì)算十分簡單，但是當(dāng)數(shù)據(jù)量特別大時(shí)，逐個(gè)進(jìn)行異或的方式是不現(xiàn)實(shí)的。例如，對(duì)于64位的Simhash值，所有3位之內(nèi)的組合要進(jìn)行C（63，3）=41 664次查詢，或者需要分配41 664倍的存儲(chǔ)空間。為了解決該問題，本文引入索引歸類的方法[11]，算法大致流程如下：①將每個(gè)m bit的簽名值劃分為n份；②利用排列簽名值建立n！（n-k）！*k個(gè)表；③精確匹配m*（1-k/n）位的簽名值；④在存有2d個(gè)簽名值的數(shù)據(jù)庫中，每個(gè)指針產(chǎn)生2d-m*（1-k/n）個(gè)指紋值。

由此可見，在海明距離的計(jì)算過程中引入索引歸類的方法，可以減少簽名值的比對(duì)過程，使之具有更高的查找效率。

2 實(shí)驗(yàn)結(jié)果及分析

本文采用的數(shù)據(jù)為100道選擇題、100道填空題、100道主觀題，試題庫為在線教育平臺(tái)的數(shù)據(jù)庫，算法語言采用Python語言，分詞系統(tǒng)采用結(jié)巴分詞技術(shù)。在采用Simhash算法計(jì)算試題題目的簽名值之前，采用結(jié)巴分詞技術(shù)去掉重用詞及無關(guān)詞，然后結(jié)合TF-IDF以及詞性、詞頻計(jì)算出關(guān)鍵詞權(quán)重，然后進(jìn)行Simhash簽名值計(jì)算，最后進(jìn)行各試題信息的海明距離計(jì)算。根據(jù)經(jīng)驗(yàn)認(rèn)為，海明距離小于等于3的兩個(gè)試題即為重復(fù)，然后將試題保留一道，刪除其余冗余試題。

在進(jìn)行實(shí)驗(yàn)前，首先需要安裝實(shí)驗(yàn)環(huán)境Linux虛擬機(jī)，本次實(shí)驗(yàn)是在Ubuntu14.04環(huán)境中運(yùn)行的。然后根據(jù)需要安裝好結(jié)巴分詞，準(zhǔn)備好實(shí)驗(yàn)所需環(huán)境之后開始實(shí)驗(yàn)。

2.1 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用傳統(tǒng)的準(zhǔn)確率、召回率兩個(gè)關(guān)鍵指標(biāo)評(píng)價(jià)本文提出的將改進(jìn)的Simhash算法應(yīng)用到相似試題檢測中的可行性分析。本文采用的試題查重可以分為以下幾個(gè)主要步驟：試題語句劃分及結(jié)巴分詞處理、采用TF-IDF技術(shù)及綜合考慮詞性詞頻與詞長確定關(guān)鍵詞權(quán)重、根據(jù)Simhash算法生成簽名值、試題簽名值對(duì)比計(jì)算等4個(gè)過程。9次實(shí)驗(yàn)所得數(shù)據(jù)如表2所示。

繪制9次實(shí)驗(yàn)數(shù)據(jù)的正確率與召回率折線圖，如圖2所示。則其各參數(shù)表示的意義為：

正確率：指測試正確的相似數(shù)據(jù)量與測試后找出來的相似數(shù)據(jù)量之比。

召回率：指測試正確的相似數(shù)據(jù)量與測試之前已知的相似數(shù)據(jù)量之比。

2.2 實(shí)驗(yàn)分析與總結(jié)

如圖2所示，本文將改進(jìn)的Simhash算法應(yīng)用于相似試題檢測當(dāng)中，文本的準(zhǔn)確率和召回率都達(dá)到95%以上，算法誤判率小于0.01。同時(shí)，由于本文使用TF-IDF技術(shù)結(jié)合詞性以及詞長計(jì)算，經(jīng)過結(jié)巴分詞所得關(guān)鍵詞的權(quán)重簡化了傳統(tǒng)的Simhash算法，且使用帶有索引功能的海明距離計(jì)算方式，極大地減少了試題之間的比較次數(shù)。因此，將改進(jìn)的Simhash算法應(yīng)用到試題查重中，在時(shí)間和性能方面都得到了極大提升，且根據(jù)實(shí)驗(yàn)結(jié)果顯示完全符合本文主題。

3 結(jié)語

針對(duì)在線教育平臺(tái)試題庫中大量試題重復(fù)的現(xiàn)象，本文提出將改進(jìn)的Simhash算法應(yīng)用到相似試題檢測中。通過上述實(shí)驗(yàn)，可以發(fā)現(xiàn)結(jié)果完全符合要求。通過使用結(jié)巴分詞技術(shù)進(jìn)行試題文本的高效切詞，對(duì)于關(guān)鍵詞權(quán)重計(jì)算，引入了TF-IDF經(jīng)典的權(quán)值計(jì)算技術(shù)，同時(shí)考慮詞性與詞長，使計(jì)算的Simhash簽名值更加精確。使用帶有索引功能的海明距離計(jì)算方式，可大大減少二進(jìn)制數(shù)值的比較次數(shù)，使計(jì)算過程更加高效可靠，查找速率更快。在今后的研究中，因?yàn)槟壳皩?shí)驗(yàn)有時(shí)會(huì)出現(xiàn)錯(cuò)誤刪除的情況，希望找到更優(yōu)的方法減少錯(cuò)誤刪除率，使查找精確性更高。

參考文獻(xiàn)：

[1] 潘雪峰，張宇晴，毛敏，等.在線教育產(chǎn)業(yè)發(fā)展現(xiàn)狀及產(chǎn)品設(shè)計(jì)研究[J].科技和產(chǎn)業(yè)，2013（8）：13-16.

[2] 王思力，張華平，王斌.雙數(shù)組Trie樹算法優(yōu)化及其應(yīng)用研究[J].中文信息學(xué)報(bào)，2006（5）：24-30.

[3] 馬成前，毛許光.網(wǎng)頁查重算法Shingling和Simhash研究[J].計(jì)算機(jī)與數(shù)字工程，2009（1）：15-17，108.

[4] 吳平博，陳群秀，馬亮.基于特征串的大規(guī)模中文網(wǎng)頁快速去重算法研究[J].中文信息學(xué)報(bào)，2003（2）：28-35.

[5] 王衛(wèi)玲.web文本分類中特征向量優(yōu)化技術(shù)研究[D].濟(jì)南：山東師范大學(xué)，2007.

[6] 李彬.基于Hadoop框架的TF-IDF算法改進(jìn)[J].微型機(jī)與應(yīng)用，2012（7）：14-16.

[7] 陸玉昌，魯明羽，李凡，等.向量空間法中單詞權(quán)重函數(shù)的分析和構(gòu)造[J].計(jì)算機(jī)研究與發(fā)展，2002（10）：1205-1210.

[8] 蔣昌金，彭宏，陳建超，等.基于主題詞權(quán)重和句子特征的自動(dòng)文摘[J].華南理工大學(xué)學(xué)報(bào)，2010（7）：50-55.

[9] 付印金，肖儂，劉芳.重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2012（1）：12-20.

[10] 余意，張玉柱，胡自健.基于Simhash算法的大規(guī)模文檔去重技術(shù)研究[J].信息通信，2015（2）：28-29.

[11] LI HENGXIN，HAN JIANHUA. Efficient duplicate detection for data in relation databases[J].Journal of South ChinaNormal University （Natural Science Edition），2015，47（1）：121-126.endprint