phpはブルームフィルターを実装します

ブルーム フィルター (BF) は、1970 年にブルームによって提案されたマルチハッシュ関数マッピングのための高速検索アルゴリズムです。要素がセットに属しているかどうかを 素早く 見つけるために使用されますが、100% の精度は必要ありません。ブルーム フィルターは通常、クローラー URL の重複排除、つまり特定の URL がクロールされたかどうかを判断するために使用されます。 原理に関しては、他の人が書いた記事を引用しましたので、ここでは詳しく説明しません。詳細については、彼の論文を参照してください。 BF の PHP 実装をいくつか見てきましたが、この記事では主にブルーム フィルターの PHP 実装について説明します。

原則:

1. 例

ブルームフィルターの重要性を説明するために、例を挙げてみましょう:

ウェブスパイダー (ウェブクローラー) を書くように頼まれたとします。巣の間には複雑なつながりがあるため、クモは巣を這うときに「ループ」を形成する可能性があります。 「ループ」の形成を避けるためには、スパイダーがどの URL にアクセスしたかを知る必要があります。 URL が与えられた場合、クモがその URL を訪問したかどうかをどうやって知ることができるでしょうか?少し考えてみると、次のような解決策が考えられます:

1. 訪問したURLをデータベースに保存します。

2. HashSetを使用して、訪問したURLを保存します。その後、O(1) に近いコストで URL が訪問されたかどうかを確認できます。

3. URLはMD5やSHA-1などの一方向ハッシュ化の後、HashSetまたはデータベースに保存されます。

4. ビットマップ方式。 BitSet を作成し、ハッシュ関数を通じて各 URL を特定のビットにマッピングします。

方法 1 ～ 3 はすべて、訪問した URL を完全に保存しますが、方法 4 は URL の 1 つのマッピング ビットのみをマークします。

データ量が少ない場合は上記の方法で完璧に問題を解決できますが、データ量が非常に多くなると問題が発生します。

方法 1 の欠点: データの量が非常に大きくなると、リレーショナル データベースのクエリの効率が非常に低くなります。また、すべての URL に対してデータベース クエリを開始するのはやりすぎでしょうか?

方法 2 の欠点: メモリを大量に消費します。 URL の数が増えると、より多くのメモリが占​​有されます。 URL が 1 億しかないとしても、各 URL は 50 文字しかカウントせず、5GB のメモリが必要です。

方法 3: MD5 処理後の文字列の情報ダイジェスト長は 128Bit のみで、SHA-1 処理後の文字列の情報ダイジェスト長は 160Bit のみであるため、方法 3 は方法 2 よりも数倍のメモリを節約します。

方法 4 はメモリ消費量が比較的少ないですが、単一のハッシュ関数の衝突確率が高すぎるという欠点があります。データ構造のクラスで学んだ、ハッシュ テーブルの競合に対するさまざまな解決策をまだ覚えていますか?競合の可能性を 1% に下げるには、BitSet の長さを URL 数の 100 倍に設定します。

実際、上記のアルゴリズムは重要な暗黙の条件を無視しています。それは、小さな確率のエラーは許容するが、100% 正確である必要はないということです。言い換えれば、少数の URL は実際には Web スパイダーによって訪問されず、それらを訪問済みと誤って判断した場合のコストは、せいぜいいくつかの Web ページを節約するだけです。

2. ブルームフィルターのアルゴリズム

ナンセンスな話はこれくらいにして、この記事の主人公を紹介しましょう。実際、上記の方法 4 の考え方はブルーム フィルターに非常に近いです。方法 4 の致命的な欠点は、競合の可能性が高いことです。競合の概念を減らすために、ブルーム フィルターは 1 つのハッシュ関数ではなく複数のハッシュ関数を使用します。

ブルームフィルターのアルゴリズムは次のとおりです:

(1)初始化

mビットのBitSetを作成し、最初にすべてのビットを0に初期化し、次にk個の異なるハッシュ関数を選択します。文字列 str を i 番目のハッシュ関数でハッシュした結果は h(i, str) として記録され、h(i, str) の範囲は 0 ～ m-1 です。

(2) 检查字符串是否存在

以下は、文字列 str が BitSet によって記録されているかどうかを確認するプロセスです:

文字列 str に対して、 h (1, str), h (2, str)... h (k, str) を計算します。 ） それぞれ。次に、BitSet の h (1, str)、h (2, str)... h (k, str) ビットが 1 であるかどうかを確認します。それらのいずれかが 1 でない場合、str には次の値が含まれていてはいけないと判断できます。記録されている。すべてのビットが 1 の場合、文字列 str は存在すると「みなされます」。

文字列に対応するビットがすべて 1 ではない場合、その文字列はブルーム フィルターによって記録されていないと確信できます。 (文字列は記録されており、対応するバイナリ ビットはすべて 1 に設定されている必要があるため、これは明らかです)

しかし、文字列に対応するビットがすべて 1 である場合、実際にはその文字列について 100% 確信することはできません。ブルームフィルターで記録。 (文字列のすべてのビットが他の文字列に正確に対応する可能性があるため) 文字列が誤って分割されるこの状況は、偽陽性と呼ばれます。

(3) 删除字符串 :

一度追加した文字列は、削除すると他の文字列に影響するため削除できません。本当に文字列を削除する必要がある場合は、基本的なブルーム フィルターの変形であるカウンティング ブルーム フィルター (CBF) を使用できます。CBF は、基本的なブルーム フィルターの各ビットをカウンターに変更して、削除機能を実現します。文字列。

Bloom Filter と単一ハッシュ関数 Bit-Map の違いは、Bloom Filter が k 個のハッシュ関数を使用し、各文字列が k ビットに対応することです。これにより、競合の可能性が減少します。

三. Bloom Filter参数选择

(1)哈希函数选择

　　哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。

(2)Bit数组大小选择

　　哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1。该文献证明了对于给定的m、n，当 k = ln(2)* m/n 时出错的概率是最小的。

　　同时该文献还给出特定的k，m，n的出错概率。例如：根据参考文献，哈希函数个数k取10，位数组大小m设为字符串个数n的20倍时，false positive发生的概率是0.0000889 ，这个概率基本能满足网络爬虫的需求了。

实现：

<?php ///*************************************************************************** // *  // * Copyright (c) 2015 Baidu.com, Inc. All Rights Reserved // *  // **************************************************************************/ //  //  //  ///** // * @file bloomfilter.php // * @author Rachel Zhang(zrqsophia@sina.com) // * @date 2015/07/24 18:48:57 // * @version $Revision$  // * @brief  // *  // **/ class BloomFilter{ var $m; # blocksize var $n; # number of strings to hash var $k; # number of hashing functions var $bitset; # hashing block with size m function BloomFilter($mInit,$nInit){ $this->m = $mInit; $this->n = $nInit; $this->k = ceil(($this->m/$this->n)*log(2)); echo "number of functions: $this->k\n"; $this->bitset = array_fill(0, $this->m, false); } function hashcode($str){ $res = array(); #put k hashing bit into $res $seed = crc32($str); mt_srand($seed); // set random seed, or mt_rand wouldn't provide same random arrays at different generation for($i=0 ; $i<$this->k ; $i++){ $res[] = mt_rand(0,$this->m-1); } return $res; } function addKey($key){ foreach($this->hashcode($key) as $codebit){ $this->bitset[$codebit]=true; } } function existKey($key){ $code=$this->hashcode($key); foreach($code as $codebit){ if($this->bitset[$codebit]==false){ return false; } } return true; } } $bf = new BloomFilter(10,2); $str_add1 = "test1"; $str_add2 = "test2"; $str_notadd3 = "test3"; //var_dump($bf->hashcode($str)); $bf->addKey($str_add1); $bf->addKey($str_add2); var_dump($bf->existKey($str_add1)); var_dump($bf->existKey($str_add2)); var_dump($bf->existKey($str_notadd3)); ?>

版权声明：本文为博主原创文章，未经博主允许不得转载。