基于BloomFilter的去重方法研究

趙艷紅 李洪奇 朱麗萍 詹坤林

摘要：在個性化新聞推薦系統(tǒng)中，文章去重是一個重要的模塊，避免了同一篇文章被重復推薦的現(xiàn)象。在海量用戶場景下，采用傳統(tǒng)的基于隊列的去重方法將會消耗大量的內存。BloomFilter是一種空間效率很高的隨機數(shù)據結構，適用于允許有一定誤判率的場景。本文基于BloomFilter，設計雙BloomFilter位數(shù)組結構和BloomFilter位數(shù)組鏈結構。實驗證明，基于BloomFilter位數(shù)組鏈的去重方法，不僅大大降低了程序對服務器內存要求，而且具有較好的靈活性和擴展性。

關鍵詞：信息超載；個性化推薦系統(tǒng)；BloomFilter

中圖分類號：TP3文獻標識碼：A

1引言

隨著互聯(lián)網技術的迅速發(fā)展，新聞數(shù)據呈爆炸式的增長，用戶很難從海量的新聞中找到自己真正感興趣的內容，信息超載問題嚴重[1]。個性化推薦系統(tǒng)是目前解決信息超載問題最有效的工具，它能主動地從用戶注冊信息、用戶瀏覽日志、歷史評分記錄等方面進行分析，挖掘出用戶的興趣偏好和項目特征，并根據用戶需求和項目信息的變化及時調整推薦的內容和服務方式，實現(xiàn)“以用戶為中心”的個性化服務[2]。一個完整的推薦系統(tǒng)包括收集用戶信息、建立用戶興趣模型和推薦算法三部分，推薦算法是最為核心的部分。協(xié)同過濾、基于內容推薦、基于圖結構推薦和混合推薦是目前較為常見的推薦方法[3，4]。在傳統(tǒng)的新聞系統(tǒng)中，用戶僅僅通過聚合頁面瀏覽新聞，同一條新聞可能不斷地出現(xiàn)在用戶的推薦列表中，降低了用戶的體驗度。為了避免同一篇文章被重復推薦的現(xiàn)象，在個性化新聞推薦系統(tǒng)中添加了去重模塊，如果該新聞用戶近期已經閱讀過，則從推薦列表中刪除。文章去重是一個重要的模塊，保證了用戶每次閱讀的新聞都是最新的。

在個性化新聞推薦系統(tǒng)中，傳統(tǒng)的去重方法為每個用戶維護一個長度為N的隊列，隊列中始終保持著最近向用戶推薦過的N篇文章的ID。推薦時，將隊列中存儲的文章ID解析出來，存放到map或者hash表中，用做去重。但是當用戶量較大的時候，該方法會消耗大量的內存。BloomFilter[5]是一種空間效率很高的隨機數(shù)據結構，它采用位數(shù)組表示一個集合，并能快速地判斷一個元素是否屬于這個集合。由于哈希查找的常數(shù)時間和少量的存儲空間開銷，使得它具有非常好的應用價值[6]，而且還可以根據具體的應用場景進行擴展[7]。BloomFilter存在一定的誤判率（falsepositiverate）[8]，不適用于嚴格要求100%正確的場合。在BloomFilter中，哈希函數(shù)個數(shù)k、位數(shù)組大小m、元素個數(shù)n都會影響到BloomFilter的誤判率。文獻[9]給出了BoomFilter取得最小誤判率的情況下，k與m/n之間的關系。

采用單BloomFilter位數(shù)組的去重方法，雖然可以節(jié)省大量的內存，但是當用戶閱讀數(shù)量超過BloomFilter的最大緩存數(shù)量時，BloomFilter位數(shù)組將會失效，發(fā)生誤判。為了解決這個問題，本文設計了雙BloomFilter位數(shù)組的去重方法，當用戶閱讀數(shù)量超過給定閾值的時候，創(chuàng)建從位數(shù)組，在推薦過程中，不斷地進行主/從位數(shù)組的切換和清空。雙位數(shù)組的方法避免了單BloomFilter的失效問題，但是該方法擴展性較差。因此，本文又設計了BloomFilter位數(shù)組鏈的去重方法，不僅節(jié)省了更多的內存，而且具有較好的靈活性和擴展性。

2個性化推薦系統(tǒng)

個性化新聞推薦系統(tǒng)有三個重要的模塊：用戶興趣建模模塊、新聞建模模塊、推薦算法模塊。推薦系統(tǒng)把用戶興趣模型中的興趣信息和新聞模型中的特征信息匹配，同時使用相應的推薦算法進行計算和篩選，找到用戶可能感興趣的新聞，然后推薦給用戶[10]。在傳統(tǒng)的新聞系統(tǒng)中，所有用戶看到的新聞都相同。而在個性化新聞系統(tǒng)中，由于用戶興趣千差萬別，不同的用戶將看到不同的新聞。傳統(tǒng)新聞系統(tǒng)通常是提供一個聚合了所有新聞鏈接的導航頁面供用戶瀏覽新聞，個性化新聞系統(tǒng)則有一個刷新按鈕，用戶可以通過刷新操作不斷獲取新的新聞。

推薦算法模塊有4個重要的模塊：觸發(fā)模塊、去重模塊、排序模塊和篩選模塊，通用的推薦流程如圖1所示。觸發(fā)模塊根據用戶興趣從文章池中檢索出文章，同時去重模塊會判斷檢索出的文章是否和用戶歷史閱讀文章重復，保證檢索出的文章不重復，構成文章候選集。排序模塊計算候選集中每篇文章的分值并排序。篩選模塊根據一定的策略篩選出最終的文章列表并推薦給用戶，同時，推薦列表將更新到用戶歷史閱讀列表用于下一次推薦去重。

去重模塊至關重要，它能夠保證用戶每次閱讀到的都是新文章。為提高計算效率，每個用戶閱讀過的歷史文章列表需要全部存儲到內存。對于一個擁有千萬甚至億級用戶的推薦系統(tǒng)，這將消耗大量的內存。為節(jié)約系統(tǒng)內存，推薦系統(tǒng)將為每個用戶設置一個緩沖區(qū)，存放用戶最近閱讀的N篇新聞（如N=500），并且每個用戶的緩沖區(qū)有一個超時限制，例如用戶24小時沒有閱讀過文章，緩沖區(qū)將被清空。

3基于隊列的去重方法

傳統(tǒng)的去重方法為每個用戶維護一個最大長度為N的隊列，當推薦新文章時，就向隊列首部插入文章ID，當隊列滿了時就將隊列尾部的文章ID拋棄，如圖2所示。這樣隊列中始終保存著已向用戶推薦的最近的N篇文章。推薦時，只需將隊列中存儲的文章ID解析出來，存放到map或者hash表中，用做去重。

新聞的ID通常是一個較長的字符串，例如一個URL。為了節(jié)約內存，在存儲時會將文章ID求md5值，然后取md5值的高64位，這樣一篇文章ID需要使用8個字節(jié)存儲。500篇文章需消耗500×8=4000字節(jié)，當用戶量較大時，將非常消耗內存。例如如果有1千萬用戶，則存儲所有歷史文章列表就需要消耗40G內存。當然，在實際應用中，并非所有用戶都會閱讀500篇文章，部分低活躍用戶的閱讀量可能少于500，而高活躍用戶的閱讀量可能多于500。endprint

4BloomFilter

BloomFilter的突出優(yōu)點是空間效率高，當一個元素加入集合時，通過k個Hash函數(shù)將這個元素映射成一個位陣列（Bitarray）中的k個點，把它們置為1，如圖3所示。檢索時，如果這些點有任何一個為0，則被檢索元素一定不在；如果都是1，則被檢索元素很可能在。

BloomFilter在判斷一個元素是否屬于一個集合的時候，存在一定的誤判率。元素集合的大小n、哈希函數(shù)個數(shù)k、位數(shù)組大小m都與BloomFilter的誤判率有關。文獻[9]給出了BloomFilter的誤判率公式：

f=（1-e-kn/m）k=（1-p）k（1）

其中p=e（-kn/m），當p=1/2（哈希函數(shù)的個數(shù)k=（m/n）·ln2）的時候，誤判率最小：

fmin=（1/2）k=（1/2）（m/n）·ln2（2）

在不超過一定誤判率的情況下，BloomFilter中位數(shù)組的大小m在滿足一定條件下才能表示全集中任意n個元素的集合。假設全集中共有u個元素，允許的最大錯誤率為ε，根據文獻[11]所述，m應滿足

m≥log2unn+ε（u-n）n

≈log2unεun≥log2ε-n=nlog2（1/ε）（3）

由式（1）和式（2）可得，當k=（m/n）·ln2的時候，誤判率最小，令f≤ε，可得

m≥nlog2（1/ε）ln2=log2e·nlog2（1/ε）（4）

式（4）所得的m值要比式（3）所得的m值大log2e≈1.44倍，說明了在哈希函數(shù)的個數(shù)取到最優(yōu)時，要讓錯誤率不超過ε，m至少需要取到最小值的1.44倍。

在本文實驗中，最大誤判率為ε=0.02，元素個數(shù)n=500，根據式（3）可得m的最小值為2822。為了使得哈希函數(shù)的個數(shù)達到最優(yōu)，同時應滿足式（4），可得m最小值應為1.44×2822=4064，從而計算出k=（m/n）×ln2=8ln2≈5.633=6。

因此，在給定最大誤判率為ε=0.02，元素個數(shù)n=500的時候，本文構造的BloomFilter的位數(shù)組大小m=4064bit≈500字節(jié)，哈希函數(shù)的個數(shù)k=6。

5單BloomFilter位數(shù)組

在個性化推薦系統(tǒng)中，將用戶瀏覽過的文章ID通過BloomFilter的k個哈希函數(shù)映射到位數(shù)組中的k個點上，并將這k個點的值全部設置為1，用于標記該文章已經閱讀過。使用BloomFilter實現(xiàn)歷史文章去重的主要流程如圖4所示。

1）使用BloomFilter需要事先給定最大誤判率ε、緩存的用戶歷史文章數(shù)量N，然后根據公式2和公式3，計算出最優(yōu)哈希函數(shù)的個數(shù)k和位數(shù)組大小m。

2）根據參數(shù)k和m，構造BloomFilter，開辟m/8字節(jié)的空間作為歷史文章的緩存，并初始化為0。

3）通過用戶的興趣模型獲取的推薦列表，需要送入BloomFilter進行去重。如果推薦的文章ID已經在歷史文章中，則從推薦列表中刪除，否則，將新文章插入BloomFilter中。

在本文中，緩存的歷史文章數(shù)量為N=500，最大誤判率ε=0.02，則構建BloomFilter時，哈希函數(shù)的個數(shù)為k=6，位數(shù)組大小m=4064bit≈500字節(jié)，此時誤判率f=0.0156（計算公式見章節(jié)1.3）。假設有一千萬的用戶量，采用傳統(tǒng)的基于隊列的方法存儲用戶的歷史記錄，需要消耗約40G的內存（106×500×8字節(jié)，具體參見章節(jié)1.2），而采用BloomFilter的方法，只需要約5G的內存（106×500字節(jié)）。由此可以看出，使用BloomFilter可以節(jié)約大量的內存。

使用單個BloomFilter需要預設能夠緩存的最大歷史文章數(shù)量，本文取N=500。當寫入BloomFilter的文章數(shù)量在500以內的時候，BloomFilter的誤判率為0.0156，在可接受范圍之內。當500條文章全部插入BloomFilter的時候，位數(shù)組幾乎全部為1。此時使用BloomFilter去重會出現(xiàn)誤判，新插入的任何文章都會被誤認為已經存在于歷史文章列表中。為了解決此問題，我們設計了雙BloomFilter的位數(shù)組結構。

6雙BloomFilter位數(shù)組

雙BloomFilter的位數(shù)組結構為主從式結構，如圖5所示。

主位數(shù)組用于推薦去重，推薦時不斷地向主位數(shù)組中插入文章ID，當主位數(shù)組中文章的數(shù)量達到某個閾值（例如60%×500=300）時，創(chuàng)建從位數(shù)組。之后，文章ID要同時寫入主位數(shù)組和從位數(shù)組中。當主位數(shù)組中文章數(shù)量達到最大值500時，將從位數(shù)組切換為主位數(shù)組，并清空原來的主位數(shù)組。此時，新的主位數(shù)組中存儲了用戶最近閱讀的200條文章，推薦新聞時，這200條文章就不會重復推薦給用戶。系統(tǒng)推薦的時候，按照上述邏輯不斷地進行主/從位數(shù)組的切換和清空，操作邏輯如圖6所示。

基于雙BloomFilter位數(shù)組的方法，當單個用戶的閱讀數(shù)量沒有達到閾值時，只需要500字節(jié)的存儲空間；對于活躍用戶，當其閱讀數(shù)量超過閾值時，會新建一個位數(shù)組，此時需要500×2=1000字節(jié)的存儲空間。采用雙BloomFilter位數(shù)組的方法，雖然避免了單BloomFilter位數(shù)組寫滿時出現(xiàn)誤判的情況，但是也存在一些問題：

1）位數(shù)組切換時只能維護用戶最近閱讀的200篇文章列表，而傳統(tǒng)的基于隊列的方法可以維護用戶最近瀏覽的500篇。

2）該方法涉及主/從位數(shù)組的切換，邏輯實現(xiàn)復雜，而且缺乏一定的靈活性，當修改用戶緩沖池的時候，例如將N值由500改為1000，邏輯操作將會更加復雜。

由于上述缺點，我們設計了BloomFilter位數(shù)組鏈結構。endprint

7BloomFilter位數(shù)組鏈

根據章節(jié)1.3中的公式，當N=100的時候，BloomFilter最優(yōu)哈希函數(shù)的個數(shù)k=6，位數(shù)組大小m=812bit≈100字節(jié)，此時誤判率仍為0.0156。因此，緩存100篇文章，只需要約100字節(jié)的位數(shù)組。如果緩存500篇文章，我們可以使用5個100字節(jié)的BloomFilter位數(shù)組，而不是1個500字節(jié)的bloomfilter位數(shù)組。BloomFilter位數(shù)組鏈結構如圖7所示。

當用戶閱讀文章時，創(chuàng)建第1個位數(shù)組，向其中插入文章ID；當用戶閱讀了100篇文章，第1個位數(shù)組填滿，此時創(chuàng)建第2個位數(shù)組，使用第1個位數(shù)組去重，并向第2個位數(shù)組中插入文章ID。依次類推，直至填滿第5個位數(shù)組。當5個位數(shù)組都填滿后，繼續(xù)插入文章時，將第1個位數(shù)組清空，使用編號為2，3，4，5的位數(shù)組去重，新文章插入第1個位數(shù)組。當?shù)?個位數(shù)組填滿時，將第2個位數(shù)組清空，使用編號為1，3，4，5的位數(shù)組去重，新文章插入第2個位數(shù)組，以此類推。

該方法類似一個循環(huán)單鏈表，其中只有一個節(jié)點存儲文章（主數(shù)組），其他節(jié)點都用于去重。第i號數(shù)組填滿時，需要清空第（i%5+1）號數(shù)組（1≤i≤5）。

與雙位數(shù)組的方法相比，基于位數(shù)組鏈的方法實現(xiàn)相對簡單，而且更加節(jié)省內存。雙位數(shù)組方法每個用戶至少消耗500字節(jié)的內存，當主/從位數(shù)組切換的時候需要消耗1000字節(jié)的內存。而采用位數(shù)組鏈的方法，最少只需要消耗100字節(jié)的內存，最多也只消耗500字節(jié)的內存。當位數(shù)組鏈中第i號填滿，清空第i%5+1號數(shù)組時，仍會保存用戶最近閱讀的400篇文章，而雙位數(shù)組方法只能保存用戶最近閱讀的200篇文章。此外，基于位數(shù)組鏈的方法更易于擴展，如果將緩存的用戶歷史文章數(shù)量N由500改為1000，只需要新建5個100字節(jié)的BloomFilter位數(shù)組即可，現(xiàn)存的BloomFilter為數(shù)組仍可繼續(xù)使用。

在個性化新聞推薦系統(tǒng)中，假設有一千萬個用戶，緩存的用戶歷史文章數(shù)量N=500。從內存、時間和擴展性等方面對本文所述的方法進行測試，實驗結果如表1所示。

將用戶瀏覽的歷史文章通過k個哈希函數(shù)映射到位數(shù)組的k個點上，空間效率高。

設計了主從位數(shù)組結構，推薦過程中不斷地進行主從數(shù)組的切換和清空，需要設置閾值。

使用5個100字節(jié)的BloomFilter位數(shù)組，代替1個500字節(jié)的BloomFilter位數(shù)組。實現(xiàn)相對簡單，靈活性好，支持動態(tài)擴展，占用較少內存。

參數(shù)

隊列長度為N=500，誤判率f=0

緩存的歷史文章數(shù)量N=500，最大誤判率ε=0.02，由此計算出BloomFilter中位數(shù)組大小m≈500字節(jié)，

哈希函數(shù)個數(shù)k=6，誤判率f≈0.0156。

緩存的歷史文章數(shù)量N=500，最大誤判率ε=0.02，閾值X=300。由此計算出單個BloomFilter中位數(shù)組大小m≈500字節(jié)，哈希函數(shù)個數(shù)k=6，誤判率f≈0.0156。

緩存的歷史文章數(shù)量N=100，最大誤判率ε=0.02。由此計算出單個BloomFilter中位數(shù)組大小m≈100字節(jié)，哈希函數(shù)個數(shù)k=6，誤判率f≈0.0156。

8結語

在個性化新聞推薦系統(tǒng)中，文章去重是其中一個重要的模塊。當用戶量達到千萬級別的時候，傳統(tǒng)的基于隊列的去重方法會消耗大量的內存。BloomFilter是一種空間效率很高的數(shù)據結構，采用單BloomFilter位數(shù)組的方法實現(xiàn)去重，雖然節(jié)省了大量的內存，但是當用戶閱讀數(shù)量超過BloomFilter的最大緩存數(shù)量時，BloomFilter位數(shù)組失效，發(fā)生誤判。為了解決這個問題，本文提出了主從式的雙BloomFilter位數(shù)組結構，解決了單BloomFilter位數(shù)組失效的問題，但是該方法缺乏靈活性，不能動態(tài)擴展。最后，本文設計的BloomFilter位數(shù)組鏈結構，不僅節(jié)省更多的內存，而且具有較好的靈活性，支持位數(shù)組鏈的動態(tài)擴展。

參考文獻

[1]羅玲.信息時代的信息超載影響及對策[J].現(xiàn)代情報，2011，31（6）：36-38.

[2]陳潔敏，湯庸，李建國，等.個性化推薦算法研究[J].華南師范大學學報：自然科學版，2014，46（5）：8-15.

[3]LIUJ，DOLANP，PEDERSENER.Personalizednewsrecommendationbasedonclickbehavior[C]//Proceedingsofthe15thinternationalconferenceonIntelligentuserinterfaces.ACM，2010：31-40.

[4]楊博，趙鵬飛.推薦算法綜述[J].山西大學學報：自然科學版，2012（3）：337-350.

[5]MITZENMACHERM.Compressedbloomfilters[J].IEEE/ACMTransactionsonNetworking（TON），2002，10（5）：604-612.

[6]肖明忠，代亞非.BloomFilter及其應用綜述[J].計算機科學，2004，31（4）：180-183.

[7]TIANX，CHENGY.Bloomfilterbasedscalablemulticast：methodology，designandapplication[J].Network，IEEE，2013，27（6）：89-94.

[8]BLOOMBH.Space/timetradeoffsinhashcodingwithallowableerrors[J].CommunicationsoftheACM，1970，13（7）：422-426.

[9]FANL，CAOP，AlmeidaJ，etal.Summarycache：ascalablewideareawebcachesharingprotocol[J].IEEE/ACMTransactionsonNetworking（TON），2000，8（3）：281-293.

[10]王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].ComputerEngineeringandApplications，2012，48（7）：66-76.

[11]BRODERrA，MITZENMACHERM.Networkapplicationsofbloomfilters：Asurvey[J].Internetmathematics，2004，1（4）：485-509.第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint