題外話：歡迎將公眾號設置為星標，技術文章第一時間看到。我們將一如既往精選技術好文，提供有價值的閱讀。如有讀者想要投稿，可以在公眾號任意文章下留言，技術博主獎勵豐厚。

作者：haolujun

cnblogs.com/haolujun/p/8399275.html

背景

最近工作中遇到了一個問題：如何對大規模題庫去重？公司經過多年的積累，有著近億道題目的題庫，但是由于題目來源不一導致題庫中有很多重復的題目，這些重復的題目在檢索時，除了增加搜索引擎的計算量外，并不會提高準確率。

此外由于題目過多，搜索引擎往往采取了截斷策略，只對一部分題目進行計算，這導致了某些正確的題目反而得不到計算，拍搜準確率甚至不增反降。所以對于一個搜索引擎來說，雖然初期增加題目數量往往可以大幅提高拍搜準確率，但是當題目量大到一定程度時，反而會由于計算量跟不上導致準確率下降。如何盡可能的去除重復題目顯得尤為重要。

一些嘗試方案

比較MD5值

對每道題目計算其MD5值作為簽名，這樣在新增題目時，只要判斷題庫中是否有相同的MD5值即可。

這種方案只適用于兩道題目一模一樣的情況，而現實中題目往往不只是這樣。

• “A比B大10"與"B比A小10”

• “小紅買10本書”與“小明買10本書”

• “今天空氣溫度為10度”與“今天的空氣溫度為10度”

這些應該是重復題，但是MD5值不同，沒法去重。

利用最長公共子序列和最小編輯距離算法

利用最長公共子序列算法與最小編輯距離算法計算兩個題目的相似度，如果相似度大于一定比例，例如大于90%，就認為是重復的題目。

這個方法理論上可行，但是計算量太大。假如文檔數為N，平均文檔長度為M，那么計算量大致為：O(N2?M2) 。

假設N=1000萬，M=200，則計算量約為 4?1018 ，筆者線下可用機器有限，沒有這么大的計算能力。但是如果能夠把相似的題目歸攏到一起，然后去比較這一小撮題目中兩兩相似程度，這個還是可行的。

Jaccard相似度

為此，我特意看了兩本書：《信息檢索導論》的19.6章節以及《大數據-互聯網大規模數據挖掘與分布式處理》的3.2與3.3節。這里面講述了如何計算兩個集合的Jaccard相似度：|A∩B||A∪B| 。這個公式對于去重來說沒什么卵用，因為計算量還是那么大。

所以這兩本書還特意介紹了與其等價的算法：轉換成隨機全排列，基于概率算法去計算Jaccard的近似值。這個轉換的證明本文不贅述，有興趣的小伙伴直接去看這兩本書。但是這里面有一個有意思的問題也是計算Jaccard相似度最關鍵的一步：如何對一個超級大的N生成一個0~N-1隨機全排列？我這里給出一個近似算法，學過初等數論的小伙伴應該對下面的定理不陌生。

定理： y=(a?x+b)modn ，如果a與n互質(即a與n的最大公約數為1)，當x取遍0~n-1時，y取遍0~n-1。

證明：假如存在兩個數 x1 和 x2，使得 y1=(a?x1+b)modn=y2=(a?x2+b)modn ，則 (a?x1+b)%n=(a?x2+b)%n ，得出 (a?x1+b?a?x2?b)%n=0 ，繼而得到 a?(x1?x2)%n=0。由于a與n互質，最大公約數為1，所以得出 x1?x2=k?n ，即 x1=x2+k?n。當 x1 和 x2 都小于n時，k只能等于0，即 x1=x2。這就說明當x取遍0~n-1時，其余數肯定不重復，由于余數的取值范圍也是0~n-1，所以結論得證。

這樣，當我們知道n時，只要找到與n互質的100或者200個數就行，甚至可以找到小于n的100個或者200個素數(素數篩法大家自行百度)，然后再隨機生成100次到200次b，就能構造出一批這樣的函數。

例如，a = 3，b = 4, n = 8

x?=?0?y?=?4
x?=?1?y?=?7
x?=?2?y?=?2
x?=?3?y?=?5
x?=?4?y?=?0
x?=?5?y?=?3
x?=?6?y?=?6
x?=?7?y?=?1

雖然這個概率算法能夠降低一些計算量，但是我還是不能夠接受。因為我們現在的關鍵問題是找出相似的一小撮，并在這一小撮中進行更精細化的判斷策略，怎么找到這一小撮咧？

利用線上拍搜日志進行挖掘

正所謂具體情況具體分析，不能一味追求高科技卻忽略現實條件。比如百度也有去重策略，但是其最后應用到線上的并不是Jaccard相似度，而是找文檔中最長的幾個句子，根據這幾個句子是否一樣判斷兩個文檔是否重復，而且準確率出奇的好。所以，我們也要具體問題具體分析。

觀察一下拍搜流程，檢索日志中會記錄每次搜索結果中幾個匹配程度最高的文檔id，那么我就可以認為這幾個文檔是一個小簇，沒有必要再重新聚簇。此外由于拍搜的優化策略極多，準確率極高，這比我自己再重新發明一個聚簇算法要省事并且效果好。有這么好的日志在手，就要充分利用起來。接下來我就詳細說說我是如何實現去重策略的。

日志格式如下：

[[1380777178,0.306],[1589879284,0.303],
[1590076048,0.303],[1590131395,0.303],
[1333790406,0.303],[1421645703,0.303],
[1677567837,0.303],[1323001959,0.303],
[1440815753,0.303],[1446379010,0.303]]

這是一個json數組，每個數組中有題目的ID和其得分。

日志選取

選取題目ID得分比較高的日志作為候選日志。這么選取是因為線上的圖像識別不能保證百分百準確，如果圖片質量特別差，那么根據識別內容檢索到的題目之間差別較大，可能根本不是一類。

聚簇

初始集合建立

對于每條日志，由排在第一位的ID作為簇標識，其它元素作為簇中的元素。

集合求并

看如下樣例：

A?->?B,C,D
E?->?C,D,F

由于兩個集合中有相同的ID，我們推測這兩個集合其實屬于一個簇，如何實現兩個集合的并？利用并查集算法(自行百度之，參加過編程競賽的小伙伴應該都不陌生。)

我寫的一個樣例代碼，如下，并查集能夠出色的完成集合合并操作。例如，可以利用并查集的join操作完成兩條日志的合并。

https://github.com/haolujun/Algorithm/tree/master/union_find_set

union_find_set.join(A,B)
union_find_set.join(A,C)
union_find_set.join(A,D)

union_find_set.join(E,C)
union_find_set.join(E,D)
union_find_set.join(E,F)

調用完操作后，我們會發現A,B,C,D,E,F都屬于同一個集合。

集合元素限制

在實際測試時發現，某些集合中的題目數量可能會達到百萬，這種情況出現是因為聚類過程中的計算偏差導致的。比如：A與B相似，B與C相似，我們會把A，B，C放到一個簇中，但是實際上A和C可能不相似，這是聚類過程中非常容易出現的問題。

簇過大會加大后面的精細計算的計算量，這是一個比在大題庫中去重稍簡單的問題，但是也非常難。考慮到題庫中重復題目不會太多，可以對每個集合大小設置上限元素數目，如果兩個將要合并的集合元素總數大于上限，則不將這兩個集合合并，這個利用并查集也非常容易實現。

精細計算

如何判斷兩個題目是否重復

現在得到的簇是一個經過拍搜的結果聚合的，但是拍搜有一個問題就是檢索使用的文字是由OCR識別生成的，其中難免會有識別錯誤，搜索引擎為了能容忍這種錯誤，加入了一定的模糊策略，這導致簇中的結果并不完全相似，所以精細計算是必要的。

那么如何比較兩個題目是否是重復的呢？特別是對于數學題這種數字和運算符、漢字混合的題目，該如何辦？經過長時間分析發現，不能夠把數字、字母與漢字同等比較。數字、字母如果不相等，那么八成這兩道題是不同的；如果數字、字母相同那么漢字描述部分可以允許一些差異，但是差異也不要太大。

這就得到了我最后的精細去重策略：分別提取題目的漢字和數字、字母、運算符，數字、字母、運算符完全相等并且漢字部分的相似度(可以使用最小編輯距離或者最長公共子序列)大于80%，就可以認為兩道題目相同。

“A比B大10"與"B比A小10”??-- 數字與字母組成的字符串不相等，不認為重復
“小紅買10本書”與“小明買10本書”???-- 數字字母相同，漢字相似度大于80%，認為重復
“今天空氣溫度為10度”與“今天的空氣溫度為10度”??-- 數字字母相同，漢字相似度大于80%，認為重復

雖然這個策略不能百分百去重所有重復題，但是能確保它能去重大部分重復題。

保留哪些題目，去除哪些題目？

考慮到搜索引擎在存儲倒排是按照題目ID大小進行排序的(存放ID與ID之間的差值)，所以留下小的ID去掉大的ID非常必要，這個不難實現。

周期性迭代

我們的去重算法是基于日志進行的去重，那么可以每次去重一部分，上線后再撈取一段時間內的日志進行去重，這樣不斷的迭代進行。

計算量還大么？

根據單機的計算量，一次撈取一定數量的日志進行去重，單機就可以完成，不需要集群，不需要分布式。

結語

聰明的小伙伴可能發現，我投機取巧了。我并沒有直接對題庫去蠻力去重，而是從拍搜日志下手，增量的一步步的實現題庫去重，只要迭代次數足夠，可以最終去重所有題目，并且每次去重可以實實在在看到效果，可以更方便調整策略細節。所以，在面對一個問題時，換一個角度可能會有更簡單的做法。

推薦閱讀

1.?SpringBoot 整合篇

2.?手寫一套迷你版HTTP服務器

3.?記住：永遠不要在MySQL中使用UTF-8

4.?Springboot啟動原理解析

來都來了

點個在看再走唄？

總結

以上是生活随笔為你收集整理的两个listmap合并去重_我是如何用单机实现亿级规模题库去重的？的全部內容，希望文章能夠幫你解決所遇到的問題。

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