基于Simhash 算法的題庫查重系統(tǒng)的設計與實現(xiàn)

熊良鈺，鄧倫丹*

（南昌大學科學技術學院，江西共青城）

引言

隨著互聯(lián)網(wǎng)技術的發(fā)展和普及，在線教育和在線學習已經(jīng)成為一種必然趨勢。利用數(shù)據(jù)算法進行智能化計算來滿足一些教育應用場景也越來越普遍。國內(nèi)各種線上教學平臺也在不斷滿足新的個性化的線上學習和教學的需求[12]。

在這些平臺上，題庫是重要學習資源之一。然而隨著題庫規(guī)模的不斷擴大，題目的重復或相似問題日益突出。這些重復或相似的題目不僅會浪費存儲空間，還會給教師帶來教學困擾；給學生的練習帶來誤導，影響做題效率。尤其是在線教育平臺和考試機構需要保證題目的獨特性和原創(chuàng)性的情況下，開發(fā)基于文本相似度的理論研究的一種高效準確的題庫查重系統(tǒng)對于題庫管理和優(yōu)化具有重要意義。

目前已經(jīng)有一些題庫查重方法被提出，比如基于文本相似度計算[4]、基于詞向量的方法[4]等。但是基于文本相似度計算的方法需要對文本進行較復雜的處理和計算，耗時較長；基于詞向量的方法對于長文本的處理效果不佳。為此，本研究提出了一種基于Simhash 算法的查重系統(tǒng)[1-3]設計。

Simhash 算法通過哈希函數(shù)和位運算提高了處理大規(guī)模題庫的效率。它能迅速生成題目的哈希值并進行比較，不僅能檢測完全相同的題目，還能識別相似或近似語義的題目。通過設定閾值將相似度高于此閾值的題目判定為重復。

綜上所述，本系統(tǒng)將極大地提升用戶在查找相似題目時的效率。系統(tǒng)設計與實施將涉及分詞處理、哈希加權、數(shù)據(jù)合并、降維處理，以及文本相似度評估等多個技術步驟的細致開發(fā)。同時，將利用jieba 分詞工具[9]、sklearn 庫[9]、Flask 后端框架[4]、streamlit 框架以及html 等技術構建一個題庫系統(tǒng)。

1 系統(tǒng)設計

1.1 算法設計

相對于MD5[10]和SHA-1 哈希算法，Simhash 算法[11]的哈希值碰撞概率極低，同時比Minhash 算法具有更低的哈希沖突率和更好的性能，而且還具有局部敏感性。具體來說，相似的文本在Simhash 值中具有較高的相似比特位，這使得Simhash 算法對于處理文本中的局部變化[13]具有一定的容忍能力。因此，它是本項目的最優(yōu)選擇。Simhash 算法的基本原理包括分詞和文本特征[13]提取、特征加權、哈希、指紋生成以及相似度計算這五個步驟[9]。

首先，我們使用jieba 分詞工具對輸入的題目進行分詞處理。在實際操作中我們還能根據(jù)不同科目的需求手動添加專業(yè)領域的詞匯以提高分詞準確性。將語句分詞完成后我們需要去除一些對文本特征基本沒有意義的停用詞[8]。對分詞結(jié)果用我們先使用Python 中的NLTK[9]去除停用詞。之后再采用TF-IDF方法[11]來提取文本特征。

TF（詞頻）指的是一個詞在文本中出現(xiàn)的頻率。計算某個詞的TF 值[5]可以使用以下公式：

式中：Vt為詞t 在文本中出現(xiàn)的次數(shù)；D 為文本中的總詞數(shù)。

IDF（逆文檔頻率）指的是一個詞在整個文本集合中的重要程度。計算某個詞的IDF 值[5]可以使用以下公式：

式中：O 為文本集合的總文檔數(shù)；Ot為包含詞t 的文檔數(shù)；在計算IDF 時，分母中加1 是為了避免當某個詞在所有文檔中都出現(xiàn)時，分母為0 導致的除零錯誤。加1 的作用是平滑處理，確保即使某個詞在所有文檔中都出現(xiàn)，它的IDF 值也不會變?yōu)闊o窮大。

TF-IDF 用于衡量一個詞在文本中的重要性。計算某個詞的TF-IDF 值可以使用以下公式：

式（3）是將式（1）和式（2）的TF 和IDF 進行相乘運算。

TF-IDF 的思想是，如果一個詞在某篇文本中出現(xiàn)的頻率較高（TF 較大），同時在整個文本集合中出現(xiàn)的頻率較低（IDF 較大），那么這個詞對于該篇文本的區(qū)分度較高，被認為是重要的詞?；赥F-IDF 方法我們對TF-IDF 值進行歸一化處理，將TF-IDF 值映射到[0，1]內(nèi)。最大- 最小歸一化的計算公式如下：

式中：X 為原始值；Y 是歸一化后的值；Xmin和Xmax分別為原始數(shù)據(jù)的最小值和最大值。

對于題庫查重文本生成hash 值這一步我們應當選取適合的哈希函數(shù)。這個哈希函數(shù)應該滿足生成的哈希值應該有較低的碰撞率，即不同的文本應該生成不同的哈希值以確保查重的準確性。還要能夠在短時間內(nèi)對文本進行哈希計算，尤其是針對大規(guī)模的題庫，需要保證計算效率。哈希值還應該具有均勻的分布特性，以便在哈希表等數(shù)據(jù)結(jié)構中減少沖突，提高查重的效率。

基于這些需要，開源的MurmurHash 系列哈希函數(shù)是一個很好的選擇。其中MurmurHash3 相對于前兩個版本在設計上考慮了更好的碰撞率，減少了哈希沖突的可能性，提高了哈希算法的穩(wěn)定性并且還進行了一些安全性方面的改進。它在處理大規(guī)模數(shù)據(jù)時具有更好的性能，適合于我們的數(shù)據(jù)處理需求。其生成哈希值時具有更均勻的分布特性，有助于減少哈希表等數(shù)據(jù)結(jié)構中的沖突。并且支持幾種不同的輸出位長度，如32 位或128 位。所以我們選擇它作為算法中生成哈希值的哈希函數(shù)。

接著，對于每個哈希值的每個位（比特），根據(jù)高位或低位的位置來分配不同的權重，然后將每個位的哈希值乘以相應的權重。最后將所有位的加權哈希值相加，得到最終的Simhash 值。為了降低維度方便計算比對，要對其進行降維處理。我們對Simhash 值的每個位進行特征選擇，只選擇對相似性判斷有重要影響的位作為降維后的特征。在具體過程中對哈希值的每個位計算其對相似性判斷的信息增益。信息增益通過熵和條件熵的計算來得到，用于衡量每個位對于相似性判斷的重要性。根據(jù)計算得到的信息增益，選擇信息增益高的位作為降維后的特征。這些位對于相似性判斷有重要影響，因此可以作為降維后的特征進行保留。根據(jù)選擇的信息增益高的位，構建降維后的Simhash 值。

其中信息熵的計算公式如下：

式中：D 為總樣本數(shù)；Pi是樣本屬于第i 個類別的概率。

條件熵的計算公式如下：

式中：Pi是樣本屬于第i 個類別的概率；Ci是集合中第i 個類別的樣本個數(shù)。

條件熵的計算公式如下：

式中：v 為屬性A 的取值個數(shù)；Dv為選出屬性A 取值為v 樣本集合。

信息增益的計算公式如下：

式中：Gain（D，A）為信息增益；H（D）為信息熵；H（D|A）為條件熵。

最終我們選取前128 位的Simhash 值[5]為題目文本的固定指紋。如果題目文本的hash 值無法達到128位就不斷在后位補0 直至達到128 位。最后，對比不同文本的Simhash 指紋[8]，通過計算漢明距離[12]來衡量它們之間的相似度。

對于兩個等長的字符串A 和B，其中每個字符串的長度為n，漢明距離[6]可以通過以下公式計算：

式中：D 表示漢明距離最終數(shù)值；A[i]表示字符串A 中的第i 個字符；B[i]表示字符串B 中的第i 個字符；∑表示求和運算。公式中，當A[i]和B[i]不相等時，計數(shù)器加1，最終得到的計數(shù)器值即為D 漢明距離。漢明距離越大，表示兩個字符串之間的差異越大。

1.2 數(shù)據(jù)庫設計

根據(jù)本項目需求我們創(chuàng)建了students、teachers、subjects、questions、answers 五張數(shù)據(jù)表[7]。其中用戶數(shù)據(jù)表包括學生和教師表，題庫信息表包括了科目表、題目表和答案表。E-R 如圖1 所示。

圖1 系統(tǒng)E-R

2 系統(tǒng)展示與測試

2.1 功能展示

2.1.1 題目導入

用戶可以通過系統(tǒng)提供的題目導入功能，將題目文本文件上傳至系統(tǒng)。系統(tǒng)支持常見的文本文件格式上傳，如.txt、.csv 還有word、excel 文檔。用戶可以選擇單個文件或批量文件導入進行查重分析。

2.1.2 個性化配置

系統(tǒng)支持用戶自定義的配置，包括相似度閾值設置添加科目和刪除題目等。用戶可以根據(jù)實際需求對系統(tǒng)自行設置以滿足不同場景下的查重需求[7]。

2.2 系統(tǒng)界面

登錄界面可供學生和老師進行注冊的登錄，使用html 結(jié)構和css 樣式并且使用JavaScript 實現(xiàn)交互。

使用界面使用streamlit 實現(xiàn)。以教師使用界面為例用戶可以增加和刪除科目，并對科目進行上傳題目文檔操作。輸入題目文本并選擇科目可以進行查重并且顯示查重結(jié)果。發(fā)現(xiàn)題目相似性較高時還能輸入題目ID 進行刪除操作。在題庫查重時還能根據(jù)需要調(diào)整相似度閾值。

2.3 系統(tǒng)測試

為了驗證基于Simhash 算法的題庫查重系統(tǒng)的準確性，我們采用了人工構造測試數(shù)據(jù)和真實場景測試的方法。

我們構造了一批具有不同相似度的題目樣本，包括完全相同的題目、部分相似的題目和完全不同的題目用于測試系統(tǒng)對不同相似度情況的識別和判斷能力。我們根據(jù)測試的結(jié)果不斷修改保證了系統(tǒng)算法在90%以上的正確率。此外還從校內(nèi)的真實的題庫中提取了一部分題目作為測試樣本，用于測試系統(tǒng)在實際應用場景下的查重效果和性能表現(xiàn)。在測試中題庫基本可以查詢到類似題目并且顯示結(jié)果。

3 項目評估與展望

本項目還能繼續(xù)在算法設計的各個環(huán)節(jié)使用不同的方法技術并且結(jié)合其它的算法根據(jù)新的應用場景進行更加全面或者個性化的處理。在數(shù)據(jù)庫設置上還能加上新的結(jié)果表將查詢結(jié)果保存以便后續(xù)回顧查詢記錄。還可以進一步完善系統(tǒng)的查重報告展示，引入數(shù)據(jù)可視化技術，提供更直觀、易懂的查重結(jié)果展示方式。能將系統(tǒng)應用拓展至更多領域，如學術領域的論文查重、知識產(chǎn)權領域的文本相似度分析等，為更多領域提供可靠的相似度分析解決方案。

結(jié)束語

基于Simhash 算法的題庫查重系統(tǒng)是一種高效、準確的題目查重解決方案。通過Simhash 算法的相似度計算，系統(tǒng)能夠快速、準確地識別題目之間的相似度，為用戶提供可靠的查重結(jié)果。系統(tǒng)具有用戶友好的界面設計和靈活的配置選項，為用戶提供了便捷、高效的使用體驗，為教育、考試等領域提供了有力的支持。