資訊專欄INFORMATION COLUMN
摘要：新問題拋出有沒有一種簽名算法，如果文本非常相似，簽名值也非常相似呢二文本相似性的簽名算法上文提出的問題，可以用局部敏感哈希解決，局部敏感哈希是一類文本越相似，哈希值越相似的算法，有興趣的同學自行百度，這里分享一下的思路。
緣起：
（1）原創不易，互聯網抄襲成風，很多原創內容在網上被抄來抄去，改來改去
（2）百度的網頁庫非常大，爬蟲如何判斷一個新網頁是否與網頁庫中已有的網頁重復呢？
這是本文要討論的問題（盡量用大家都能立刻明白的語言和示例表述）。
一、傳統簽名算法與文本完整性判斷
問題拋出：
（1）運維上線一個bin文件，將文件分發到4臺線上機器上，如何判斷bin文件全部是一致的？
（2）用戶A將消息msg發送給用戶B，用戶B如何判斷收到的msg_t就是用戶A發送的msg？
思路：
一個字節一個字節的比對兩個大文件或者大網頁效率低，我們可以用一個簽名值（例如md5值）代表一個大文件，簽名值相同則認為大文件相同（先不考慮沖突率）
回答：
（1）將bin文件取md5，將4臺線上機器上的bin文件也取md5，如果5個md5值相同，說明一致
（2）用戶A將msg以及消息的md5同時發送給用戶B，用戶B收到msg_t后也取md5，得到的值與用戶A發送過來的md5值如果相同，則說明msg_t與msg相同
結論：md5是一種簽名算法，常用來判斷數據的完整性與一致性
md5設計原則：兩個文本哪怕只有1個bit不同，其md5簽名值差別也會非常大，故它只適用于“完整性”check，不適用于“相似性”check。
新問題拋出：
有沒有一種簽名算法，如果文本非常相似，簽名值也非常相似呢？
二、文本相似性的簽名算法
上文提出的問題，可以用局部敏感哈希LSH（Locality Sensitive Hash）解決，局部敏感哈希是一類文本越相似，哈希值越相似的hash算法，有興趣的同學自行百度，這里分享一下minHash的思路。
問題的提出：什么是minHash？
回答：minHash是局部敏感哈希的一種，它常用來快速判定集合的相似性，也常用于檢測網頁的重復性，其思路為，用相同的規則抽取集合中的少部分元素代表整個集合，如果少部分元素的重合度很高，非常可能整個集合的重復度也很高。
舉例：待判定的集合為A{1, 7, 5, 9, 3, 11, 15, 13}
已有的集合為：
B{10, 8, 2, 4, 6, 0, 1, 16},
C{100, 700, 500, 900, 300, 1100, 1500,1300},
D{1, 3, 2, 4, 6, 5, 8, 7}
假設使用部分元素代替全體集合的規則為：集合內元素進行排序，取值最小的4個（這個過程有信息損失，我們可以認為是一個hash過程）
處理結果為：
A{1, 3, 5, 7}
B{0, 1, 2, 4} => A與B有1個元素相同
C{100, 300, 500, 700} => A與C有0個元素相同
D{1, 2, 3, 4} => A與D有2個元素相同
判斷結論：我們認為集合A與集合D是最相似的
這個例子有點2，但基本能說明整體思路，實際在執行的過程中：
（1）我們可以使用更多的元素來代表集合，以提高準確性（例如，將上例中的4個元素代表集合升級為8個元素代表集合）
（2）我們可以使用更多的hash函數來代表集合，以提高準確性（例如，上例除了“排序后取值最小的4個元素代表集合”，還可以增加一個哈希函數“排序后取值最大的4個元素代表集合”）
（3）minHash可以量化評判相似度，亦可以評判網頁是否重復（一個分類問題），設定相似度閾值，高于閾值為重復，低于閾值為不重復
（4）實際排重過程中，網頁庫中的哈希值都可以提前計算，只有待判定的集合或者網頁的哈希值需要臨時計算
三、minHash與長文本重復度檢測有什么關系
目前看來沒什么關系，但如果我們能將每一個長文本用一個集合來表示，就能將長文本的相似度用minHash來解決了。
問題的提出：如何將長文本轉化為集合？
回答：我去，分詞不是就可以么
舉例：待判定的長文本為A{我是58沈劍，我來自58到家}
已有網頁庫集合為：
B{我是一只來自58的狼}
C{58到家，服務到家}
D{這事和我沒關系，我是湊數的}
使用分詞將上述文本集合化：
A{我，58，沈劍，來自，到家}
B{我，58，來自，狼}
C{58，服務，到家}
D{事，我，湊數，關系}
判斷結論：當當當當，轉化為集合后，可以快速判斷A與B的相似度最高，當然實際執行過程中，除了分詞還得考慮詞頻，用這種方法對長文本進行相似度檢測，準確率非常高（文本越長越準）
四、還有沒有更有效的方法
使用上述方法進行文本相似度檢測，需要進行中文分詞，詞頻統計，哈希值計算，相似度計算，計算量微大。
然而，抄襲成風，一字不改的風氣，讓技術有了更廣闊的優化空間，贊！
怎么優化呢？
不再進行分詞，而是進行“分句”，用標點符號把長文按照句子分開，使用N個句子集合（例如一篇文章中5條最長的句子作為簽名，注意，長句子比短句子更具有區分性）作為文章的簽名，在抄襲成風的互聯網環境下，此法判斷網頁的重復度能大大降低工程復雜度，并且準確度也異常的高。
五、結論
在抄襲成風的互聯網環境下，采用“分句”的方式，用5條最長的網頁內容作為網頁的簽名，能夠極大的降低排重系統復雜度，提高排重準確率，不失為一種好的選擇。
摘“ 架構師之路”，不錯的訂閱號！ 58---沈劍
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/25918.html
摘要：如有感興趣，請自行查閱相關文檔，進一步的了解前端的性能優化單行文本去重單行文本去重可兼容不支持接口的瀏覽器這里應該很好明白是在干什么吧需要傳入一個初始空字符串參數，否則你將得到的是一個字符串被拆分后的數組。 之前偶然看到一篇使用正則實現字符去重及多行去重的文章。感覺寫的有點糙，而且性能也不夠高，對新手的使用和理解都有一點難度。于是忍不住就搞了一個比較可愛的出來。而且不是一般的可愛，因為...
摘要：中文網頁的一大特點就是天下文章一大抄，各種博文新聞幾乎一字不改或稍作修改就被網站發表了。這個特點，很適合這個百度算法。但是，實際中個別字的修改，會導致被轉載的最長的那句話不一樣，從而其值也不一樣了，最終結果是，準確率很高，召回率較低。 在互聯網出現之前，抄很不方便，一是源少，而是發布渠道少；而在互聯網出現之后，抄變得很簡單，鋪天蓋地的源源源不斷，發布渠道也數不勝數，博客論壇甚至是自建網...
摘要：前言今天，把自己之前封裝過的一部分小功能操作分享出現，都是一些可以說是比較常用，實現起來比較簡單，代碼又比較少的一些功能或操作，比如關鍵詞變色，數組打亂，數組去重等。關鍵詞變色這個功能很常見，特別是在搜索引擎執行搜索的時候。 1.前言 今天，把自己之前封裝過的一部分小功能操作分享出現，都是一些可以說是比較常用，實現起來比較簡單，代碼又比較少的一些功能或操作，比如關鍵詞變色，數組打亂，數...
閱讀 2725·2021-11-22 13:52
閱讀 1189·2021-10-14 09:43
閱讀 3646·2019-08-30 15:56
閱讀 2956·2019-08-30 13:22
閱讀 3279·2019-08-30 13:10
閱讀 1570·2019-08-26 13:45
閱讀 1105·2019-08-26 11:47
閱讀 2796·2019-08-23 18:13
