火眼金睛演算法,教你海量短文本場景下去重

来源:https://www.cnblogs.com/qcloud1001/archive/2018/12/03/10059709.html
-Advertisement-
Play Games

本文由QQ大數據發表 最朴素的做法 在大多數情況下,大量的重覆文本一般不會是什麼好事情,比如互相抄襲的新聞,群發的垃圾簡訊,鋪天蓋地的廣告文案等,這些都會造成網路內容的同質化並加重資料庫的存儲負擔,更糟糕的是降低了文本內容的質量。因此需要一種準確而高效率的文本去重演算法。而最朴素的做法就是將所有文本進 ...


本文由QQ大數據發表

最朴素的做法

在大多數情況下,大量的重覆文本一般不會是什麼好事情,比如互相抄襲的新聞,群發的垃圾簡訊,鋪天蓋地的廣告文案等,這些都會造成網路內容的同質化並加重資料庫的存儲負擔,更糟糕的是降低了文本內容的質量。因此需要一種準確而高效率的文本去重演算法。而最朴素的做法就是將所有文本進行兩兩比較,簡單易理解,最符合人類的直覺,對於少量文本來說,實現起來也很方便,但是對於海量文本來說,這明顯是行不通的,因為它的時間複雜度是,針對億級別的文本去重時,時間消耗可能就要以年為單位,此路不通。

另外,我們講到去重,實際上暗含了兩個方面的內容,第一是用什麼方式去比較更為高效,第二是比較的時候去重標準是什麼。這裡的去重標準在文本領域來說,就是如何度量兩個文本的相似性,通常包含編輯距離,Jaccard距離,cosine距離,歐氏距離,語義距離等等,在不同領域和場景下選用不同的相似性度量方法,這裡不是本文的重點,所以按下不表,下麵著重解決如何進行高效率比較的問題。

核心思想

降低時間複雜度的關鍵: > 儘力將潛在的相似文本聚合到一塊,從而大大縮小需要比較的範圍

simHash演算法

海量文本去重演算法裡面,最為知名的就是simHash演算法,是谷歌提出來的一套演算法,並被應用到實際的網頁去重中。 simHash演算法的最大特點是:將文本映射為一個01串,並且相似文本之間得到的01串也是相似的,只在少數幾個位置上的0和1不一樣。為了表徵原始文本的相似度,可以計算兩個01串之間在多少個位置上不同,這便是漢明距離,用來表徵simHash演算法下兩個文本之間的相似度,通常來說,越相似的文本,對應simHash映射得到的01串之間的漢明距離越小。

為了讓這個過程更為清晰,這裡舉個簡單的例子。

t1 = "媽媽喊你來吃飯" t2 = "媽媽叫你來吃飯"

可以看到,上面這兩個字元串雖然只有一個字不同,但是通過簡單的Hash演算法得到的hash值可能就完全不一樣了,因而無法利用得到的hash值來表徵原始文本的相似性。然而通過simHash演算法的映射後,得到的simHash值便是如下這樣:

SH1 = "1000010010101101[1]1111110000010101101000[0]00111110000100101[1]001011" SH2 = "1000010010101101[0]1111110000010101101000[1]00111110000100101[0]001011"

仔細觀察,上面的兩個simHash值只有三個地方不一樣(不一樣的地方用"[]"標出),因此原始文本之間的漢明距離便是3。通常來說,用於相似文本檢測中的漢明距離判斷標準就是3,也就是說,當兩個文本對應的simHash之間的漢明距離小於或等於3,則認為這兩個文本為相似,如果是要去重的話,就只能留下其中一個。

simHash演算法的去重過程思路很簡單,首先有一個關鍵點: > 假如相似文本判斷標準為漢明距離3,在一個待去重語料集中存在兩個相似文本,那也就是說這兩個相似文本之間的漢明距離最大值為3(對應hash值最多有3個地方不同),如果simHash為64位,可以將這個64位的hash值從高位到低位,劃分成四個連續的16位,那麼這3個不同的位置最多只能填滿4個中的任意3個區間(可以反過來想,如果這4個區間都填滿了,那就變成漢明距離為4了)。也就是說兩個相似文本必定在其中的一個連續16位上完全一致。

想明白了這個關鍵點之後,就可以對整個待去重文本都進行一次simHash映射(本文中使用64位舉例),接著將這些01串從高位到低位均分成四段,按照上面的討論,兩個相似的文本一定會有其中一段一樣,仍用上面的例子,分成的四段如下所示:

t1 = "媽媽喊你來吃飯" SH1 = "1000010010101101[1]1111110000010101101000[0]00111110000100101[1]001011" SH1_1 = "1000010010101101" #第一段 SH1_2 = "[1]111111000001010" #第二段 SH1_3 = "1101000[0]00111110" #第三段 SH1_4 = "000100101[1]001011" #第四段 t2 = "媽媽叫你來吃飯" SH2 = "1000010010101101[0]1111110000010101101000[1]00111110000100101[0]001011" SH2_1 = "1000010010101101" #第一段 SH2_2 = "[0]111111000001010" #第二段 SH2_3 = "1101000[1]00111110" #第三段 SH2_4 = "000100101[0]001011" #第四段

這一步做完之後,接下來就是索引的建立。按照上面的討論,每一個simHash都從高位到低位均分成4段,每一段都是16位。在建立倒排索引的過程中,這些截取出來的16位01串的片段,分別作為索引的key值,並將對應位置上具有這個片段的所有文本添加到這個索引的value域中。 直觀上理解,首先有四個大桶,分別是1,2,3,4號(對應的是64位hash值中的第一、二、三、四段),在每一個大桶中,又分別有個小桶,這些小桶的編號從0000000000000000到1111111111111111.在建立索引時,每一個文本得到對應的simHash值後,分別去考察每一段(確定是1,2,3和4中的哪個大桶),再根據該段中的16位hash值,將文本放置到對應大桶中對應編號的小桶中。 索引建立好後,由於相似文本一定會存在於某一個16位hash值的桶中,因此針對這些分段的所有桶進行去重(可以並行做),便可以將文本集合中的所有相似文本去掉。

整個利用simHash進行去重的過程如下圖所示:

img

總結一下,整個simHash去重的步驟主要是三個: 1. 針對每一個待去重文本進行simHash映射; 2. 將simHash值分段建立倒排索引; 3. 在每一個分段的hash值中並行化去重操作。

利用simHash進行去重有兩個點非常關鍵: - simHash映射後仍然保持了原始文本的相似性; - 分而治之的思想大大降低了不必要的比較次數。

因此,有了這兩點做保證,對於長文本下的simHash演算法以及使用漢明距離來度量文本之間的相似性,可以極大降低演算法的時間複雜度,並且也能取得很好的去重效果。但是在短文本場景下,這種度量方法的效果將會變得很差,通常情況下,用來度量長文本相似的漢明距離閾值為3,但是短文本中,相似文本之間的漢明距離通常是大於3的,並且該演算法中,基於漢明距離的相似性閾值選取的越高,該演算法的時間複雜度也會越高,此時漢明距離無法繼續作為短文本相似性的度量標準應用到短文本去重中。

基於文本局部信息的去重演算法

基於文本局部信息的去重過程,其基本思想和simHash類似,只不過不是利用hash值,而是直接利用文本的一個子串作為key,然後凡是擁有這個子串的文本都會被放入到這個子串對應的桶中。 這裡隱含了一個前提: > 任意兩個可判定的相似文本,必定在一個或多個子串上是完全一致的。

此外,子串的產生,可以通過類似於n-grams(如果是詞和字層面的,對應shingles)的方法,直接從原始文本上滑動視窗截取,也可以去掉停用詞後在剩下的有序片語合中截取,還可以對原始文本進行摘要生成後再截取,總之只要是基於原始文本或可接受範圍內的有損文本,都可以利用類似的思想來產生這些作為索引的子串。

整個去重演算法分為五個大的框架,分別包括:文本預處理,倒排索引的建立,並行化分治,去重演算法的實現,文本歸併等。

文本預處理

文本預處理根據所選用的具體子串截取方法的不同,而有所不同。如果子串是由片語合形成的,則需要對文本進行分詞,如果需要去掉停用詞,那麼這也是文本預處理的工作。為了簡化過程的分析,這裡主要以原始文本直接截取子串為例,因此預處理的工作相對偏少一些。

倒排索引的建立

假定潛在的兩個相似文本(要求去重後其中一個被去掉)分別是t1和t2,二者之間完全一致的最大連續子文本串有k個,它們組成一個集合,將其定義為S = {s1,s2,...,sk},這些子文本串的長度也對應一個集合L = {l1,l2,...,lk},針對該特定的兩個文本進行去重時,所選擇的截取子文本串長度不能超過某一個閾值,因為如果截取長度超過了該閾值,這兩個文本便不再會擁有同一個子文本串的索引,因而演算法自始至終都不會去比較這兩個文本,從而無法達到去重的目的。這個閾值便被定義為這兩個文本上的最大可去重長度,有:

img

在所有的全局文本上去重的話,相應的也有一個全局去重長度m,它表徵瞭如果要將這部分全局文本中的相似文本進行去重的話,針對每一個文本需要選取一個合適的截取長度。一般來說,全局去重長度的選擇跟去重率和演算法的時間複雜度相關,實際選擇的時候,都是去重率和時間複雜度的折中考慮。全局去重長度選擇的越小,文本的去重效果越好(去重率會增大),但相應的時間複雜度也越高。全局去重長度選擇越大,相似文本去重的效果變差(部分相似文本不會得到比較),但時間複雜度會降低。這裡的原因是:如果全局去重長度選擇的過高,就會大於很多相似文本的最大可去重長度,因而這些相似文本便不再會判定為相似文本,去重率因而會下降,但也正是因為比較次數減少,時間複雜度會降低。相反,隨著全局去重長度的減小,更多的相似文本會劃分到同一個索引下,經過相似度計算之後,相應的相似文本也會被去除掉,因而全局的去重率會上升,但是由於比較次數增多,時間複雜度會增大。

假定有一個從真實文本中抽樣出來的相似文本集C,可以根據這個樣例集來決定全局去重長度m,實際情況表明,通常來說當m>=4(一般對應兩個中文詞的長度),演算法並行計算的時候,時間複雜度已經降低到可以接受的範圍,因此可以得到:

img

假定某個待去重的文本t,其長度為n。定義S為截取的m-gram子串的集合,根據m和n的大小關係,有下列兩種情況: (1)當n>=m時,可以按照m的大小截取出一些m-gram子串的集合,該集合的大小為n-m+1,用符號表示為S = {s1,s2,...,sn-m+1}; (2)當n<m時,無法截取長度為m的子串,因此將整個文本作為一個整體加入到子串集合當中,因此有S={t}. 每一個待去重文本的m-gram子串集合生成之後,針對每個文本t,遍歷對應集合中的元素,將該集合中的每一個子串作為key,原始文本t作為對應value組合成一個key-value對。所有文本的m-gram子串集合遍歷結束後,便可以得到每一個文本與其n-m+1個m-gram子串的倒排索引。 接下來,按照索引key值的不同,可以將同一個索引key值下的所有文本進行聚合,以便進行去重邏輯的實現。

img

演算法的並行框架

這裡的並行框架主要依托於Spark來實現,原始的文本集合以HDFS的形式存儲在集群的各個節點上,將這些文本按照上面所講的方法將每一個文本劃分到對應的索引下之後,以每一個索引作為key進行hash,並根據hash值將所有待去重文本分配到相應的機器節點(下圖中的Server),分散式集群中的每一個工作節點只需負責本機器下的去重工作。基於Spark的分散式框架如下,每一個Server便是一個工作節點,Driver負責分發和調配,將以HDFS存儲形式的文本集合分發到這些節點上,相當於將潛在的可能重覆文本進行一次粗粒度的各自聚合,不重覆的文本已經被完全分割開,因而每個Server只需要負責該節點上的去重工作即可,最終每個Server中留下的便是初次去重之後的文本。

img

去重的實現

並行化框架建立後,可以針對劃分到每一個索引下的文本進行兩兩比較(如上一個圖所示,每一個Server有可能處理多個索引對應的文本),從而做到文本去重。根據1中的分析,任意兩個可判定的相似文本t1和t2,必定在一個或多個子文本串上是完全一致的。根據3.1.1中的設定,這些完全一致的最大連續子串組成了一個集合S = {s1,s2,...,sk},針對t1和t2劃分m-gram子串的過程中,假定可以分別得到m-gram子串的集合為S1和S2,不妨假設S中有一個子串為si,它的長度|si|大於全局去重長度m,那麼一定可以將該子串si劃分為|si|-m+1個m-gram子串,並且這些子串一定會既存在於S1中,也會存在於S2中。更進一步,t1和t2都會同時出現在以這|si|-m+1個m-gram子串為key的倒排索引中。

去重的時候,針對每一個索引下的所有文本,可以計算兩兩之間的相似性。具體的做法是,動態維護一個結果集,初始狀態下隨機從該索引下的文本中選取一條作為種子文本,隨後遍歷該索引下的待去重文本,嘗試將遍歷到的每一條文本加入結果集中,在添加的過程中,計算該遍歷到的文本與結果集中的每一條文本是否可以判定為相似(利用相似性度量的閾值),如果與結果集中某條文本達到了相似的條件,則退出結果集的遍歷,如果結果集中完全遍歷仍未觸發相似條件,則表明此次待去重的文本和已知結果集中沒有任何重覆,因此將該文本添加到結果集中,並開始待去重文本的下一次遍歷。 去重的時候,兩個文本之間的相似性度量非常關鍵,直接影響到去重的效果。可以使用的方法包括編輯距離、Jaccard相似度等等。在實際使用時,Jaccard相似度的計算一般要求將待比較的文本進行分詞,假定兩個待比較的文本分詞後的集合分別為A和B,那麼按照Jaccard相似度的定義可以得到這兩個文本的相似度 顯然,兩個完全不一致的文本其Jaccard相似度為0,相反兩個完全一樣的文本其Jaccard相似度為1,因此Jaccard相似度是一個介於0和1之間的數,去重的時候,可以根據實際需要決定一個合適的閾值,大於該閾值的都將被判定為相似文本從而被去掉。

整個的去重實現偽代碼如下:

初始狀態: 文本集合T = {t_1,t_2,...,t_n} 去重結果R = {} 相似度閾值sim_th 輸出結果: 去重結果R 演算法過程: for i in T: flag = true for j in R: if( similarity(i,j) < sim_th ) flag = false break -> next i else continue -> next j if( flag ) R.append(i) #表示i文本和當前結果集中的任意文本都不重覆,則將i添加到結果集中

文本歸併去重

這一個步驟的主要目的是將分處在各個不同機器節點上的文本按照預先編排好的id,重新進行一次普通的hash去重,因為根據上一步的過程中,可能在不同子串對應的桶中會留下同一個文本,這一步經過hash去重後,便將這些重覆的id去除掉。 最終得到的結果便是,在整個文本集上,所有的重覆文本都只保留了一條,完成了去重的目的。整個的去重流程如下圖所示:

img

和simHash進行比較

這裡提出來的去重演算法與simHash比較,分別從時間複雜度和去重準確度上來說,

首先,時間複雜度大大降低 - 分桶的個數根據文本量的大小動態變化,大約為文本數的2倍,平均單個桶內不到一條文本,桶內的計算複雜度大大降低;而simHash演算法中,桶的個數是固定的4*216=26萬個 - 一般來說,只有相似文本才有相似的片語合,所以某個特定的片語合下相似文本占大多數,單個桶內的去重時間複雜度傾向於O(N);相應的,simHash單個桶內依然有很多不相似文本,去重時間複雜度傾向於O(N^2)

其次,相似性的度量更為精準: - 可以使用更為精準的相似性度量工具,但是simHash的漢明距離在短文本裡面行不通,召回太低,很多相似文本並不滿足漢明距離小於3的條件

總結

這裡提出的基於文本局部信息的去重演算法,是在短文本場景下simHash等去重演算法無法滿足去重目的而提出的,實際上,同樣也可以應用於長文本下的去重要求,理論上,時間複雜度可以比simHash低很多,效果能夠和simHash差不多,唯一的缺點是存儲空間會大一些,因為演算法要求存儲很多個文本的副本,但在存儲這些文本的副本時候,可以使用全局唯一的id來代替,所以存儲壓力並不會提升很多,相比時間複雜度的大大降低,這點空間存儲壓力是完全可以承擔的。

此文已由作者授權騰訊雲+社區發佈,更多原文請點擊

搜索關註公眾號「雲加社區」,第一時間獲取技術乾貨,關註後回覆1024 送你一份技術課程大禮包!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1. 啟動過程中的記憶體初始化 首先我們來看看start_kernel是如何初始化系統的, start_kerne定義在 "init/main.c?v=4.7, line 479" 其代碼很複雜, 我們只截取出其中與記憶體管理初始化相關的部分, 如下所示 table th:nth of type(1){ ...
  • diff 命令是 linux上非常重要的工具,用於比較文件的內容,特別是比較兩個版本不同的文件以找到改動的地方。diff在命令行中列印每一個行的改動。最新版本的diff還支持二進位文件。diff程式的輸出被稱為補丁 (patch),因為Linux系統中還有一個patch程式,可以根據diff的輸出將 ...
  • 前言:本篇博客是博主踩過無數坑,反覆查閱資料,一步步搭建完成後整理的個人心得,分享給大家~~~ 本文所需的安裝包,都上傳在我的網盤中,需要的可以打賞博主一杯咖啡錢,然後私密博主,博主會很快答覆呦~ 00.組件版本和配置策略 00-01.組件版本 Kubernetes 1.10.4 Docker 18 ...
  • (+)在等號的左邊表示右連接; (+)在等號的右邊表示左連接。 右連接 RIGHT JOIN 左連接 Left join ...
  • 上篇我們說了 SQL 的基本語法,掌握了這些基本語法後,我們可以對單表進行查詢及計算分析。但是一個大的系統,往往會有數十上百張表,而業務關係又錯綜複雜。我們要查的數據往往在好幾張表中,而要從多張表中來獲取信息就需要用到表聯結了。 先說說什麼是聯結,聯結就是用一條 SELECT 語句從多個表中查詢數據 ...
  • ***********模糊查詢*********/ 關鍵字: like (!!!!字元串類型) in (,,) 匹配()內的某個具體值(括弧里可以寫多個值) between... and.. 在某兩個值的區間範圍中(前後都包括,小的寫前面,大的寫後面) **********通配符********/ ...
  • 本文力在從oracle的基礎出發,從oracle的基礎結束,從資料庫的連接、用戶管理、sqlplus使用、plsql工具、存儲過程、函數、包、觸發器等一個DBA經常進行的操作與維護方面入手,旨在從這條最淺顯易懂的學習道路上,瞭解oracle的日常使用。相信對於初學者是個不錯的選擇,也希望自己的這篇整... ...
  • 一. 概述 Redis伺服器是可以與多個客戶端建立網路連接,每個客戶端可以向伺服器發送命令請求,而伺服器則接收並處理客戶端發送的命令請求,並向客戶端返回命令回覆。通過使用I/O多路復用技術實現的文件事件處理器,Redis伺服器使用單進程單線程的方式來處理命令請求,並與多個客戶端進行網路通信。 1.1 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...