Simhash算法在試題查重中的應用

冉崇善+邵春霞

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

關鍵詞：試題查重；Simhash算法；海明距離；簽名值

DOIDOI：10.11907/rjdk.172357

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2018）002-0151-03

0 引言

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

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

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

1 相關技術

1.1 結巴分詞技術

結巴分詞是一個使用python語言進行中文分詞的模塊，可以使用其進行關鍵詞抽取。本文使用結巴分詞對輸入的試題進行切分，它主要具有三大特性：

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

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

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

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

1.2 Simhash算法介紹

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

1.2.1 Simhash簽名值計算

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

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

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

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

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

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

因此，綜合試題信息各個關鍵詞的詞頻、詞性以及詞長，能夠更加準確地計算出試題關鍵詞的權重，全面表示出試題特征，使計算出的Simhash簽名值更加精確。

1.2.2 Simhash簽名值匹配階段

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

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

2 實驗結果及分析

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

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

2.1 評價標準

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

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

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

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

2.2 實驗分析與總結

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

3 結語

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

參考文獻：

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

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

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

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

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

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

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

[8] 蔣昌金，彭宏，陳建超，等.基于主題詞權重和句子特征的自動文摘[J].華南理工大學學報，2010（7）：50-55.

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

[10] 余意，張玉柱，胡自健.基于Simhash算法的大規(guī)模文檔去重技術研究[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