1 Simhash 算法原理

Simhash 算法的原理是將一個在超大集合內查找數據的問題利用哈希函數轉換映射的方法轉化為一個在較小集合內查找數據的問題，這樣能大大減少計算量。
Simhash 算法流程
Simhash[3-5]生成指紋可以分為分詞、hash 值計算、加權、合并、降維等 5 個步驟。其算法流程圖如下所示：

2 Simhash 算法原理改進方法

2．1 文檔相似度的改進

傳統的兩篇文檔相似度定義為，兩篇文檔內容對應 Simhash 簽名值之間的海明距離。不過單一考慮文檔內容比較片面，存在誤差。為了減少誤差，文中將兩篇文檔的相似度定義為文檔內容的相似度和文檔其他信息的相似度權重加。文檔內容的相似度使用改進 Simhash算法計算，文檔其他信息的相似度使用最小哈希算法計算。下面給出文檔其他信息相似度的計算方法。
文檔其他信息包括文檔關鍵字、文檔標簽、文檔引 用文獻等，用集合的形式表示。現假設文檔中所有其他信息集合為{ a，b，c，d，e } ，文檔 s1含有其他信息集合為{ a，
b } ，文檔s2含有的其他信息集合為{ b，c，d}，文檔s3的集合為{ a，d，e} ，文檔s4 的集合為{ d，e} ，將這一系列集合組成特征矩陣，如圖1所示。
圖1表示的特征矩陣的行表示文檔其他信息組成的集合，列表示文檔集合。計算文檔其他信息的相似度，就是計算特征矩陣對應列之間的 jaccard相似度。因為特征矩陣十分稀疏，使用最小哈希的方法來計算。先對矩陣進行隨機打亂，文檔其他信息(即為矩陣中的對應列) 的最小哈希值，為矩陣對應列第一個值為1的行號。最小哈希函數設為h，最小哈希函數用于模擬對矩陣所進行的隨機打亂，特征矩陣兩列之間的 jaccard 相似度為對應列打亂后最小哈希值相同的概率。
當特征矩陣規模很大時，對其進行隨機打亂是非常耗時的，而且還要進行多次。為此使用多個哈希函數來模擬隨機打亂，具體做法為:假設要進行n次隨機打亂，選用n個隨機函數h1，h2，…，hn來模擬這一效果，步驟如下:
SIG( i，c) 表示簽名矩陣第 i 個哈希函數在第 c 列上的值。SIG( i，c) 初始化為 Inf( 無窮大) ，再對 r 行進行以下步驟:
( 1) 計算 h1( r) ，h2( r) ，…，hn( r) ;
2) 對特征矩陣的每一列c。如果c所在的第r行為 0，不做任何操作; 如果c所在的第r行為1，則對于每個 i =1，2，…，n，SIG( i，c)和hi( r)中的較小值設為SIG( i，c) 。
計算圖1特征矩陣，a，b，c，d，e 對應 0，1，2，3，4，5 行，選用哈希函數 h1( x) = ( x + 1) mod5，h2( x) = ( 2 × x +1) mod5，函數中的 x 表示行號，遍歷完所有行，最
終的簽名矩陣如圖 2 所示。

計算圖 2 最終簽名矩陣對應列之間的 jaccard 相似度，s1和 s2 兩列完全不同，所以 sim( s1，s2 ) = 0。查看圖 1 特征矩陣，得到 s1 和 s2 的真實 jaccard 相似度為 1/5
，比較接近。
文檔其他信息組成的特征矩陣轉化為簽名矩陣，通過簽名矩陣來估計特征矩陣對應列之間的 jaccard相似度，也就是估計文檔其他信息的相似度。最終通過文檔內容的相似度和文檔其他信息的相似度計算文檔的相似度，將A，B兩篇文檔間的相似度定義為:

其中，Haming( A，B) 表示A，B兩篇文檔內容的海明距離，通過改進的 Simhash 計算得到，加一是為了保證當A，B兩篇文檔內容的海明距離為0時，分數不會為無窮大; minHash( A，B) 表示 A，B 兩篇文檔其他信息的相似度，通過最小哈希算法計算得到; μ 的取值一般為 0.8～ 0.9，兩篇文檔的相似度還是以內容的相似度為主。

2．2 文檔特征權值的改進

傳統 Simhash 算法以文檔分詞識別出的關鍵詞為 特征值，權重為該關鍵詞出現的次數。由于權重僅由單詞出現的次數來決定，部分重要信息會丟失，導致最終計算出的 Simhash簽名值的準確性降低。為解決這一問題，綜合使用 TF－IDF［12］技術和單詞的主題相關性計算關鍵詞權重。TF－IDF 技術用于計算一個關鍵詞在一個文檔集中的一篇文檔的重要性，TF 表示關鍵詞在這篇文檔出現的頻率，關鍵詞 ti 的 TF 定義為:
其中，ni，j表示關鍵詞ti在文檔j中出現的次數;表示文檔j中所有關鍵詞出現次數的總和。關鍵詞在文檔中出現的次數越多，TF越高。逆向文檔頻率IDF，表示關鍵詞所在文檔在文檔集所有文檔中的比重，定義為:
其中，D表示ti文檔集中的文檔總數; | { j: ti ∈ dj} | 表示含有關鍵詞的文檔的數量( ni，j 不為 0 的文檔) 。
關鍵詞 i 在文檔 j 的TD－IDF 定義為: tf － idfi，j = tfi，j × idfi 。TD－IDF的局限是在文檔集出現次數越多，重要性就一定越小，這對于部分文檔來說存在誤差，有些重要單詞在文檔集中的出現次數也很大，需要給這些單詞更大的權重。
文中使用單詞的主題相關性作為附加權重，將專業術語詞匯的長度作為判斷單詞主題相關性的依據。選用 CSSCI 關鍵詞庫中的關鍵詞作為數據集，統計數據集中10 000 個中文術語的長度，并進行正態擬合，
如圖 3 所示。

擬合得到的正態分布函數均值 μ = 4．51，標準差 σ = 2． 207，μ 的 置 信 度 為 95% 的 置 信 區 間［4. 214， 4. 806］，σ 的 置 信 度 為 95% 的 置 信 區 間［1. 787， 2. 627］。擬合得到的 Ｒ square 為擬合函數的確定系數，越接近1，表示擬合函數對實際數據的解釋能力越好。此次擬合得到的Ｒ square 為 0. 949 9，較接近1，說明擬合方程具有較好的解釋能力。將正態分布函數歸一化得到:

將歸一化得到的中文術語長度函數 len( x) 作為單詞的主題相關性函數。其中 x 表示單詞的長度，可以看出長度越接近 4．5，函數值越高，單詞的主題相關性也越高。使用單詞主題相關性函數作為附加的權重，可以提高 TF－IDF 技術判斷單詞權重的準確性。最終得出關鍵詞 x 的權重計算公式為:

其中，tfx，j × idfx 為關鍵詞 x 在文檔 j 的TF－IDF值; len( x) 為單詞 x 的主題相關性函數。

2．3 Simhash 簽名值檢索階段的改進

Simhash 簽名值檢索階段使用哈希到桶的方法選出候選對，具體做法為將簽名值分塊，對同塊的簽名值使用相同的哈希函數，映射到桶，哈希到同一個桶中元素為候選對。此時可能會出現分布不均勻的情況，大量元素被哈希到了同一個桶，這個桶中的所有元素都是候選對，需要進行大量海明距離計算。
文中通過設定閾值的方法解決這個問題。當一個桶中元素超過此閾值，對桶中元素所屬簽名值除去桶中元素后再次分塊，對同塊的簽名值使用相同的哈希函數，二次哈希映射仍被映射到同一個桶中元素為候選對，可以減少候選對數量，使分布更加均勻。
具體步驟為:
( 1) 檢查每一個桶中的元素，判斷元素數量是否超過閾值，閾值定義為 ( 1 + μ) × AVEn ，其中 AVEn 為桶中元素的平均值，μ 為權重。
( 2) 當一個桶中的元素超過這個閾值時，對桶中元素所屬的簽名值除去桶中元素塊后，再次分塊，將同一塊的簽名值使用相同的哈希函數，進行二次哈希，二次哈希映射到相同桶中的元素作為候選對。
例如一共有 233 ( 將近 10 億篇文檔) ，每篇文檔每部分簽名為 16 位，則桶數組數目為 65 536( 216 ) 個，每個桶的平均元 素個數為 131 072 ( 233－16 ) 個，則AVEn = 131 072，現取 μ 為 2，則當某個桶中的元素超過 ( 1 + 2) × 131 072 = 393 216 時進行二次哈希，二次哈希的桶數組數目為 4 096( 212 ) 個，此時依舊被哈希到同一個桶的元素作為候選對進行海明距離計算。

3 實驗結果及分析

參考文獻:
馬成前，毛許光．網頁查重算法 Shingling 和 Simhash 研究［J］．計算機與數字工程，2009，37( 1) : 15－17．
顧志祥，謝龍恩，杜 雨.文本相似度計算的Simhash算法的實現與改進[J]信息通信，2020
王 誠，王宇成.基于Simhash 的大規模文檔去重改進算法研究[J].計算機技術與發展，2019
余 意，張玉柱，胡自健．基于 Simhash 算法的大規模文檔去重技術研究［J］．信息通信，2015( 2) : 28－29．

總結

以上是生活随笔為你收集整理的信息检索与搜索引擎：Simhash算法优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。