基于BloomFilter的去重方法研究

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

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

關鍵詞：信息超載；個性化推薦系統；BloomFilter

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

1引言

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

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

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

2個性化推薦系統

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

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

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

3基于隊列的去重方法

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

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

4BloomFilter

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

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

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

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

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

在不超過一定誤判率的情況下，BloomFilter中位數組的大小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倍，說明了在哈希函數的個數取到最優時，要讓錯誤率不超過ε，m至少需要取到最小值的1.44倍。

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

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

5單BloomFilter位數組

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

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

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

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

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

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

6雙BloomFilter位數組

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

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

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

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

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

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

7BloomFilter位數組鏈

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

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

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

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

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

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

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

使用5個100字節的BloomFilter位數組，代替1個500字節的BloomFilter位數組。實現相對簡單，靈活性好，支持動態擴展，占用較少內存。

參數

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

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

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

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

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

8結語

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

參考文獻

[1]羅玲.信息時代的信息超載影響及對策[J].現代情報，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]王國霞，劉賀平.個性化推薦系統綜述[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