?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
/*ブルーム フィルター アルゴリズムでフィルターを解除します。
ブルーム フィルターの基本的な処理アイデアを紹介します。0 1 の情報を格納する空間のバッチを適用し、各ハッシュ関数の対応する位置の値に基づいて要素の対応する位置を決定します。ハッシュ関数がすべて1であるということは、この要素が存在することを意味します。逆に 0 の場合、対応する位置の値は 1 に設定されます。異なる要素が同じハッシュ値を持つ可能性、つまり複数の要素の情報が同じ場所に格納される可能性があるため、一定の誤判定率が発生します。
適用空間が小さすぎると、要素数が増えるにつれて1が多くなり、各要素間で競合する可能性が高まり、誤判定率が増加します。また、ハッシュ関数の選択と数はバランスよく行う必要がありますが、複数のハッシュ関数を使用すると正確な判定が可能になりますが、プログラムの処理速度が低下し、ハッシュ関数の数が増えると、より多くの場所情報を保存する必要があります。
ブルームフィルターアプリケーション。 ブルームフィルターは通常、大規模なデータコレクションに要素が存在するかどうかを判断するために使用されます。たとえば、メール サーバーのスパム フィルターです。検索エンジンの分野では、Web スパイダーによる URL フィルタリングに Bloom-Filter が最も一般的に使用されます。Web スパイダーには、ダウンロードされる Web ページの URL と、Web スパイダーがダウンロードしたときにダウンロードされた Web ページの URL を保存する URL リストがあります。 Web ページの場合は、Web ページから URL を抽出します。新しい URL を抽出した後、その URL がリストにすでに存在するかどうかを確認する必要があります。現時点では、ブルーム フィルター アルゴリズムが最適な選択です。 たとえば、Yahoo、Hotmail、Gmai などのパブリック電子メール (電子メール) プロバイダーは、スパマーからのスパムを常にフィルターする必要があります。 1 つの方法は、スパムの送信元の電子メール アドレスを記録することです。送信者は常に新しいアドレスを登録しているため、世界中には少なくとも数十億のスパム アドレスが存在し、それらすべてを保存するには多数のネットワーク サーバーが必要になります。
ブルームフィルターは1970年にBarton Bloomによって提案されました。これは実際には長いバイナリ ベクトルと一連のランダム マッピング関数です。動作原理を説明するために上記の例を使用します。
1 億の電子メール アドレスを保存するとします。まず、2 億バイトのベクトルである 16 億のバイナリ ビット (ビット) を作成し、次に 16 億のバイナリ ビットをすべて 0 に設定します。電子メール アドレス X ごとに、8 つの異なる乱数ジェネレーター (F1、F2、...、F8) を使用して、8 つのメッセージ フィンガープリント (f1、f2、...、f8) を生成します。次に、乱数発生器 G を使用して、これら 8 つの情報フィンガープリントを 1 ～ 16 億の 8 つの自然数 g1、g2、...、g8 にマッピングします。ここで、これら 8 つの位置のすべての 2 進ビットを 1 に設定します。この処理を 1 億件すべての電子メール アドレスに対して実行した場合。これらの電子メール アドレス用のブルーム フィルターが構築されます。 (下の画像を参照) それでは、ブルーム フィルターを使用して、不審なメール アドレス Y がブラックリストに含まれているかどうかを検出する方法を見てみましょう。同じ 8 つの乱数ジェネレータ (F1、F2、...、F8) を使用して、このアドレスの 8 つの情報フィンガープリント s1、s2、...、s8 を生成し、これら 8 つのフィンガープリントをブルーム フィルタリングの 8 つのバイナリ ビットにマッピングします。デバイスの時間は t1、t2、...、t8 です。 Y がブラックリストにある場合、t1、t2、...、t8 に対応する 8 つの 2 進数は 1 でなければなりません。このようにして、ブラックリストにある電子メール アドレスを正確に見つけることができます。 ブルームフィルターはブラックリスト内の疑わしいアドレスを決して見逃しません。ただし、欠点が 1 つあります。つまり、適切な電子メール アドレスが、すべて 1 に設定されている 8 つのバイナリ ビットに偶然対応する可能性があるため、ブラックリストにない電子メール アドレスがブラックリストにあると判断される可能性は非常に低いです。幸いなことに、この可能性は非常に小さいです。これを誤認識確率と呼びます。上の例では、誤認の確率は 10,000 分の 1 未満です。 ブルームフィルターの利点は、高速でスペースを節約できることです。ただし、一定の誤認識率があります。一般的な解決策は、誤って識別される可能性がある電子メール アドレスの小さなホワイトリストを作成することです。
*/
// 上記のアルゴリズムを記述するにはphpプログラムを使用します
$set = 配列(1,2,3,4,5,6); // $set に 5 があるかどうかを判断します
$bloomFiter = 配列(0,0,0,0,0,0,0,0,0,0);
// 何らかのアルゴリズムを通じてセットを表すように $bloomFiter 中央値配列を変更します。 ここでは、簡単なアルゴリズムを使用して、ブルームの位置に対応するセット内の値を 1 に変更します。 //アルゴリズムは次のとおりです
foreach($setを$key){
$bloomFiter[$key] = 1; }
var_dump($bloomFiter) ;
//この時点では $bloomFiter = array(1,1,1,1,1,1);
//セットに含まれているかどうかを判断します
if($bloomFiter[9] ==1){ エコー「セット内」; }その他{ エコー「セットにありません」 ; }
// 上記は単なる例です。実際には、いくつかのハッシュ アルゴリズムが必要ですが、一方で、ハッシュ関数の数が少ない場合、ビット配列内の 0 の数が多くなります。
クラスブルームフィルター{
関数 __construct($hash_func_num=1, $space_group_num=1) { $max_length = pow(2, 25); $binary = パック('C', 0);
//1バイトは8ビットを占有します $this->one_num = 8;
//デフォルト 32m*1 $this->space_group_num = $space_group_num; $this->hash_space_assoc = array();
//スペースを割り当てる for($i=0; $i<$this->space_group_num; $i++){ $this->hash_space_assoc[$i] = str_repeat($binary, $max_length); }
$this->pow_array = array( 0 => 1, 1 => 2、 2 => 4, 3 => 8、 4 => 16、 5 => 32、 6 => 64、 7 => 128、 ); $this->chr_array = array(); $this->ord_array = array(); for($i=0; $i<256; $i++){ $chr = chr($i); $this->chr_array[$i] = $chr; $this->ord_array[$chr] = $i; }
$this->hash_func_pos = array( 0 => 配列(0, 7, 1), 1 => 配列(7, 7, 1), 2 => 配列(14, 7, 1), 3 => 配列(21, 7, 1), 4 => 配列(28, 7, 1), 5 => 配列(33, 7, 1), 6 => 配列(17, 7, 1), );
$this->write_num = 0; $this->ext_num = 0;
if(!$hash_func_num){ $this->hash_func_num = count($this->hash_func_pos); } その他{ $this->hash_func_num = $hash_func_num; } }
関数追加($key) { $hash_bit_set_num = 0; // 個別キー $hash_basic = sha1($key); // 最初の 4 桁を切り取って、16 進数を 10 進数に変換します $hash_space = hexdec(substr($hash_basic, 0, 4)); //係数を取得します $hash_space = $hash_space % $this->space_group_num;
for($hash_i=0; $hash_i<$this->hash_func_num; $hash_i++){ $hash = hexdec(substr($hash_basic, $this->hash_func_pos[$hash_i][0], $this->hash_func_pos[$hash_i][1])); $bit_pos = $hash >> $max = $this->ord_array[$this->hash_space_assoc[$hash_space][$bit_pos]]; $num = $hash - $bit_pos * $this->one_num; $bit_pos_value = ($max >> $num) & 0x01; if(!$bit_pos_value){ $max = $max | $this->pow_array[$num]; $this->hash_space_assoc[$hash_space][$bit_pos] = $this->chr_array[$max]; $this->write_num++; } その他{ $hash_bit_set_num++; } } if($hash_bit_set_num == $this->hash_func_num){ $this->ext_num++; true を返す; } false を返す; }
関数 get_stat() { 配列を返す( 'ext_num' => $this->ext_num, 'write_num' =>$this->write_num, ; );} }
//テスト //6 つのハッシュ値を取得します。現在は最大 7 つです $hash_func_num = 6;
// 1 つのストレージ スペースを割り当てます。理論的には、スペースが大きいほど、php.ini の使用可能なメモリ制限に注意してください。 $space_group_num = 1;
$bf = 新しいブルームフィルター($hash_func_num, $space_group_num);
$list = 配列( 「http://test/1」、 「http://test/2」、 「http://test/3」、 「http://test/4」、 「http://test/5」、 「http://test/6」、 「http://test/1」、 「http://test/2」、 ); foreach($list as $k => $v){
if($bf->add($v)){ echo $v, "n"; } }
|