使用布隆過濾器

Question

查找文檔中的單詞的出現的可能性，我有這樣的單詞列表 - 列表1 =男孩，蘋果，芒果，車]我有兩個文件具有以下內容：

document1= The boy driving a car ate apple and mango. 
document2= The boy ate an apple. 

我只需要找出給定的單詞列表是否存在於文檔中。

爲了檢查list1中的單詞是否存在於文檔中，我可以爲list1（比如bloomlist1）和bloom1過濾器（比如bloomdocument1）創建一個bloom過濾器。然後，我可以按位進行檢查，並檢查結果是否與bloomlist1相同。如果它相同，我可以說在list1中的所有單詞都存在於document1中。所以，它會返回True。

如果我對document2執行相同的處理方法，即逐位處理，則結果爲False。但是，即使文檔中包含列表中的單個單詞，我也需要得到True。

這是可能與布隆過濾器或我需要任何其他數據結構。如果否，那麼什麼纔是符合這兩個標準的最佳數據結構。

Answer 1

我不認爲你使用Bloom過濾器是合適的。

您聲明需要構建兩個過濾器 ，其中一個用於單詞列表，另一個用於搜索文檔。然後你按位與過濾器。如果結果與原始單詞列表過濾器相同，則接受 文檔，否則您拒絕它。

如果這是你的過程有正確的認識還是比較清楚的是，文件只能通過 如果它包含了所有的單詞從列表（或散列衝突的手段了一些額外的比特是 集的文檔布隆過濾器可能會導致其接受 - 可能導致誤報）。

如果您希望在列表中的一個單詞匹配後立即選擇一個文檔，那麼只需要一個Bloom過濾器用於單詞列表（對於正在測試的文檔不需要）。使用布隆過濾器散列函數逐個散列文檔中的每個單詞。只要結果散列匹配單詞列表Bloom filter中的所有相應位（這是一個命中）就接受文檔。然後您需要驗證命中不是由於 誤報。

Bloom過濾器的「美」是它不會遭受錯誤的否定。也就是說，如果您的文檔中沒有任何 單詞在Bloom過濾器中有「命中」，則可以100％確定文檔中沒有單詞出現在相關單詞列表中。

您面臨的一個問題是布盧姆過濾器容易出現假 積極因素。假陽性是指布隆過濾器中有一個不在關聯列表中的單詞。 因此，只要Bloom過濾器指示「命中」，您就必須使用實際單詞列表明確驗證每個命中的「真相」。 沒有辦法繞過它。

構建一個好的布隆過濾器的「藝術」是找到一組哈希函數，這些哈希函數執行起來便宜，並且導致低的誤報率（通常這等於散列函數之間的獨立性和良好的分佈）。關於 的關於多少哈希函數和多大的過濾器 需要達到給定的假陽性率（假設有很好的散列函數），Bloom過濾器將給你提供很多指導。

如果您進行計算，您會發現，對於任何重要大小的單詞列表，您至少需要使用7個哈希函數來實現可接受的假陽性率。對於大文檔中的每個 單詞運行7個哈希函數將會「昂貴」，無論您如何操作。此外，如果您的文檔 包含大量不同的單詞，則在布隆過濾器 上遭受錯誤肯定命中的可能性可能變得顯着 - 降低其有用性。

此處的其他答案表明，更好的方法是爲列表中的單詞構造一個簡單的哈希表，然後從文檔中散列每個單詞 以查看它是否在列表中有匹配。如果是這樣，請選擇文檔。簡單。這種技術 很可能會針對這種類型的應用程序執行布隆過濾器方法，除非在您的問題中未列出某些非常特殊的情況。

編輯 - 什麼是最好的方法？

上有一個給定的文本做多字符串搜索的許多方面。這是 很難說哪一個將是爲你的應用的最佳解決方案，因爲大多數的算法和 它們的實現是複雜的因素（如平均字大小， 區別詞數，文件大小，文字的數量敏感搜索列表，可用內存，具有「命中」的可能性等）。這裏沒有一個正確的答案。

使用布隆過濾器很可能是一種合理的方法，但是，你至少應該看看其他 替代品。幾個例子可能是：

• Suffix Trees這對於中等大小的單詞列表可以是非常有效的。
• Compact encoding schemes匹配多串
• Hybrid algorithms combining Bloom filters plus a Suffix Tree也可以很有效的
• 而且，如果你可以做一些簡單的假設，如模式來匹配具有相同的長度，像this可能是有用的

底線是你應該看看一個更廣泛的戰略，解決任何具體的解決方案之前。

Answer 2

要檢查是否在列表中的單詞任何文件中存在：

• 創建布隆過濾器。
• 將列表中的所有單詞插入它。
• 然後檢查文檔中的每個單詞是否包含在布隆過濾器中。只要你找到一個，你可以返回true。如果你找不到，返回false。

bloom過濾器當然有誤報的可能性 - 即使該詞不存在，它也可以返回true。爲了避免這種情況，你可以使用一個散列表（與上面描述的方式相同） - 但這會使用更多的內存。

Answer 3

如果您正在搜索數百萬個已知詞彙集的文檔，那麼布隆過濾器並不是最佳選擇。您最終爲每個文檔中的每個單詞插入Bloom過濾器，並且對於每個文檔，最終必須檢查每個單詞的Bloom過濾器以確定它是否存在於文檔中。

如果您只需要知道文檔中是否存在您的任何單詞，則可以爲要檢查的單詞構建散列表，並測試文檔中的每個單詞。因此，舉例來說：

hashTable = {"boy", "mango", "car", "apple"} 
for each document 
{ 
    found = false 
    for each word in document 
    { 
     if word in hash table 
     { 
      found = true 
      break // found a word. Skip the rest of the document. 
     } 
     if found then output success else output failure 
    } 
} 

這將是比布隆過濾器的方法更好地爲幾個原因：

• 哈希表查找將一般會比布隆過濾器設置多個位快。
• 使用散列表，如果您發現它包含其中一個單詞，您可以跳過大部分文檔。
• 你只需要初始化散列表一次。您必須清除每個文檔的布隆過濾器。
• 您所需的布隆過濾器的大小取決於文檔中唯一字的數量。如果你的Bloom過濾器太小，那麼誤報率可能會不合理地高。