Bloom-Filterアルゴリズム
一、Bloom-Filterアルゴリズムの概要.Bloom-Filter、つまりBloomフィルタは1970年にBloomから提出されました.これは、1つのセットにおいて要素があるかどうかを検索するために用いることができ、その利点は、空間効率と照会時間が他のアルゴリズムをはるかに超えていることであり、Bloom-Filterには誤審があることにある.
二、Bloom-Filterの基本思想.Bloom-Filterアルゴリズムの核心思想は複数の異なるHash関数を利用して「衝突」を解決することです.ある要素xが1つのセットにあるかどうかを計算し、まず考えられる方法は、すべての既知の要素を保存してセットRを構成し、要素xとこれらのRの要素を逐一比較して、セットRに存在するかどうかを判断することである.チェーンなどのデータ構造を使って実現できます.しかし、セットRの要素が増加するにつれて、その占有メモリはますます大きくなる.考えてみてください.もし何千万個かの異なるウェブページがあれば、必要なメモリはプロセス全体のメモリアドレス空間を占有するのに十分です.すなわち、MD 5を使用して、UUUIDのこれらの方法は、URLを固定された短い文字列に変換し、メモリ占有もかなり大きい.
日常生活の中で、コンピューターソフトを設計する時も含めて、一つの要素が一つのセットにあるかどうかを常に判断します.例えばワープロソフトでは、英語の単語のスペルが正しいかどうかをチェックします.FBIでは、容疑者の名前はすでに容疑者リストにありますか?ネットの爬虫類の中で、1つのURLは訪問されたことがありますか?一番直接的な方法は、集合中のすべての元素をコンピュータに存在させ、新しい元素に出会う時、それを集合中の元素と直接比較すればいいです. 一般に、コンピュータのセットはハッシュテーブルで格納される.その利点は高速で正確で、欠点はストレージスペースがかかります.集合が比較的小さいと、この問題は顕著ではないが、集合が大きいと、ハッシュ・テーブルの格納効率が低いという問題が明らかになった.
三、Bloom-Filterの応用.Bloom-Filterは、一般的に、大きなデータ量のセットにおいて、ある要素が存在するかどうかを判定するために使用される.例えば、メールサーバの迷惑メールフィルタ.検索エンジンの分野では、Bloom-Filterが最もよく使われているのは、ネットワーク蜘蛛のURLフィルタリングです.ネットワークスパイダーには通常、ダウンロードするURLとダウンロードしたウェブページのURLが保存されています.ウェブページから新しいURLが抽出された後、このURLがリストに存在しているかどうかを判断する必要があります.この時、Bloom-Filterアルゴリズムが一番良い選択です. 例えば、Yahoo!HotmailやGmailのような公衆メールプロバイダは、迷惑メールを送信する人からの迷惑メールをフィルタリングする必要があります.一つの方法は、迷惑メールのメールアドレスを記録することです.これらの送信者は絶えず新しい住所を登録していますので、全世界では少なくとも数十億個の迷惑メールの住所があります.彼らを全部保存するには大量のネットサーバーが必要です.
ブルロンフィルタはバートン・ブルロンによって1970年に提案された.これは実際には長いバイナリベクトルと一連のランダムマッピング関数である.私たちは上記の例を通して仕事の原理を説明します.
一億の電子メールアドレスを記憶すると仮定して、まず16億バイナリ(ビット)、すなわち二億バイトのベクトルを作成して、16億のバイナリビットを全部ゼロに設定します.各電子メールアドレスXについては、8つの異なる乱数発生器(F 1,F 2,…,F 8)を用いて8つの情報指紋(f 1,f 2,…,f 8)を生成する.もう一つの乱数発生器Gでこの8つの情報の指紋を1から16億までの8つの自然数g 1,g 2,…,g 8にマッピングします.この8つの位置のバイナリビットを全部一つに設定します.私たちはこの一億個のメールアドレスに対してこのような処理を行いました.これらのメールアドレスに対する布隆フィルタが完成しました.(下図参照)
今は、ブラックリストの中にあるかどうかをブロンフィルタで確認してみましょう.私たちは同じ8つの乱数発生器(F 1、F 2、…、F 8)を使ってこのアドレスに対して8つの情報の指紋s 1、s 2、…、s 8を生成し、その後この8つの指紋をブロンフィルタの8つのバイナリビットに対応させ、それぞれt 1、t 2、…、t 8である.Yがブラックリストにある場合、明らかに、t 1,t 2,…,t 8に対応する8つのバイナリは、必ず1である.このようにブラックリストの中の電子メールアドレスに出会っても、私たちは正確に見つけることができます.
ブラックリストの中の怪しい住所は決して漏れません.しかし、足りないところがあります.つまり、ブラックリストにないメールアドレスをブラックリストの中に判定する可能性が極めて小さいのです.良いメールアドレスがあるかもしれません.ちょうど8つに対応して2進数ビットに設定されています.幸いこの可能性は小さいです.私たちはそれを誤認確率と呼びます.上記の例では、誤認確率は万分の一以下です.
布隆フィルタの利点は、高速、省スペースにあります.しかし、一定の誤認率があります.一般的な救済方法は、小さな白いリストを作成し、誤審の可能性があるメールアドレスを保存しています.
四、Bloom-Filterの具体的な実現(java言語).
二、Bloom-Filterの基本思想.Bloom-Filterアルゴリズムの核心思想は複数の異なるHash関数を利用して「衝突」を解決することです.ある要素xが1つのセットにあるかどうかを計算し、まず考えられる方法は、すべての既知の要素を保存してセットRを構成し、要素xとこれらのRの要素を逐一比較して、セットRに存在するかどうかを判断することである.チェーンなどのデータ構造を使って実現できます.しかし、セットRの要素が増加するにつれて、その占有メモリはますます大きくなる.考えてみてください.もし何千万個かの異なるウェブページがあれば、必要なメモリはプロセス全体のメモリアドレス空間を占有するのに十分です.すなわち、MD 5を使用して、UUUIDのこれらの方法は、URLを固定された短い文字列に変換し、メモリ占有もかなり大きい.
日常生活の中で、コンピューターソフトを設計する時も含めて、一つの要素が一つのセットにあるかどうかを常に判断します.例えばワープロソフトでは、英語の単語のスペルが正しいかどうかをチェックします.FBIでは、容疑者の名前はすでに容疑者リストにありますか?ネットの爬虫類の中で、1つのURLは訪問されたことがありますか?一番直接的な方法は、集合中のすべての元素をコンピュータに存在させ、新しい元素に出会う時、それを集合中の元素と直接比較すればいいです. 一般に、コンピュータのセットはハッシュテーブルで格納される.その利点は高速で正確で、欠点はストレージスペースがかかります.集合が比較的小さいと、この問題は顕著ではないが、集合が大きいと、ハッシュ・テーブルの格納効率が低いという問題が明らかになった.
三、Bloom-Filterの応用.Bloom-Filterは、一般的に、大きなデータ量のセットにおいて、ある要素が存在するかどうかを判定するために使用される.例えば、メールサーバの迷惑メールフィルタ.検索エンジンの分野では、Bloom-Filterが最もよく使われているのは、ネットワーク蜘蛛のURLフィルタリングです.ネットワークスパイダーには通常、ダウンロードするURLとダウンロードしたウェブページのURLが保存されています.ウェブページから新しいURLが抽出された後、このURLがリストに存在しているかどうかを判断する必要があります.この時、Bloom-Filterアルゴリズムが一番良い選択です. 例えば、Yahoo!HotmailやGmailのような公衆メールプロバイダは、迷惑メールを送信する人からの迷惑メールをフィルタリングする必要があります.一つの方法は、迷惑メールのメールアドレスを記録することです.これらの送信者は絶えず新しい住所を登録していますので、全世界では少なくとも数十億個の迷惑メールの住所があります.彼らを全部保存するには大量のネットサーバーが必要です.
ブルロンフィルタはバートン・ブルロンによって1970年に提案された.これは実際には長いバイナリベクトルと一連のランダムマッピング関数である.私たちは上記の例を通して仕事の原理を説明します.
一億の電子メールアドレスを記憶すると仮定して、まず16億バイナリ(ビット)、すなわち二億バイトのベクトルを作成して、16億のバイナリビットを全部ゼロに設定します.各電子メールアドレスXについては、8つの異なる乱数発生器(F 1,F 2,…,F 8)を用いて8つの情報指紋(f 1,f 2,…,f 8)を生成する.もう一つの乱数発生器Gでこの8つの情報の指紋を1から16億までの8つの自然数g 1,g 2,…,g 8にマッピングします.この8つの位置のバイナリビットを全部一つに設定します.私たちはこの一億個のメールアドレスに対してこのような処理を行いました.これらのメールアドレスに対する布隆フィルタが完成しました.(下図参照)
今は、ブラックリストの中にあるかどうかをブロンフィルタで確認してみましょう.私たちは同じ8つの乱数発生器(F 1、F 2、…、F 8)を使ってこのアドレスに対して8つの情報の指紋s 1、s 2、…、s 8を生成し、その後この8つの指紋をブロンフィルタの8つのバイナリビットに対応させ、それぞれt 1、t 2、…、t 8である.Yがブラックリストにある場合、明らかに、t 1,t 2,…,t 8に対応する8つのバイナリは、必ず1である.このようにブラックリストの中の電子メールアドレスに出会っても、私たちは正確に見つけることができます.
ブラックリストの中の怪しい住所は決して漏れません.しかし、足りないところがあります.つまり、ブラックリストにないメールアドレスをブラックリストの中に判定する可能性が極めて小さいのです.良いメールアドレスがあるかもしれません.ちょうど8つに対応して2進数ビットに設定されています.幸いこの可能性は小さいです.私たちはそれを誤認確率と呼びます.上記の例では、誤認確率は万分の一以下です.
布隆フィルタの利点は、高速、省スペースにあります.しかし、一定の誤認率があります.一般的な救済方法は、小さな白いリストを作成し、誤審の可能性があるメールアドレスを保存しています.
四、Bloom-Filterの具体的な実現(java言語).
import java.util.BitSet;
public class SimpleBloomFilter {
private static final int DEFAULT_SIZE =2 << 24 ;
private static final int [] seeds =new int []{5,7, 11 , 13 , 31 , 37 , 61};
private BitSet bits= new BitSet(DEFAULT_SIZE);
private SimpleHash[] func=new SimpleHash[seeds.length];
public static void main(String[] args) {
String value = "[email protected]" ;
SimpleBloomFilter filter=new SimpleBloomFilter();
System.out.println(filter.contains(value));
filter.add(value);
System.out.println(filter.contains(value));
}
public SimpleBloomFilter() {
for( int i= 0 ; i< seeds.length; i ++ ) {
func[i]=new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public void add(String value) {
for(SimpleHash f : func) {
bits.set(f.hash(value), true );
}
}
public boolean contains(String value) {
if(value ==null ) {
return false ;
}
boolean ret = true ;
for(SimpleHash f : func) {
ret=ret&& bits.get(f.hash(value));
}
return ret;
}
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash( int cap, int seed) {
this.cap= cap;
this.seed =seed;
}
public int hash(String value) {
int result=0 ;
int len= value.length();
for (int i= 0 ; i< len; i ++ ) {
result =seed* result + value.charAt(i);
}
return (cap - 1 ) & result;
}
}
}
、 Bloom-Filter （C ）。
hash 。
1. 。
/** bitmap array of bloom‐filter */
struct
bitmap_bloomfilter_t
{
u32_t * bitmap1; /* hash */
u32_t
* bitmap2; /* hash */
long max_size; /*
};
2. 。
bitmap_bloomfilter_t
， 。
(1)bitmap_bloomfilter_t *
create_bitmap_bloomfilter( long max_size
)， bitmap_bloomfilter_t , max_size 。
(2)void
free_bitmap_bloomfilter( bitmap_bloomfilter_t ** bbf
), bitmap_bloomfilter_t ， 。
bloom‐filter ， 。
(3)int
bloomfilter_filter( const bitmap_bloomfilter_t * bbf, const void *
data, long len )
。 ， 1，
1。
(4)static __INLINE__ BOOL get_bitmap_bit( const u32_t *
bitmap, u32_t 2
offset ), 1。
(5)static
__INLINE__ void set_bitmap_bit( const u32_t * bitmap, u32_t offset
)， 1。
hash 。
(6)static u32_t hash_f1( const
void * data, long len )
(7)static u32_t hash_f2( const void * data,
long len )
2. 。
long * url[10] = {
“http://www.baidu.com/”,
“http://www.google.com/”,
“http://www.rising.com.cn”,
“http://www.yahoo.com/”,
“http://www.microsoft.com/”,
“http://www.baidu.com/”,
“http://www.baidu.com.cn”,
“http://www.baidu.com”,
“http://www.baidu.com/index.html”,
“http://www.firefox.org/”
};
int
main( int argc, char ** argv )
{
int i;
bitmap_bloomfilter_t *
bbf = create_bitmap_bloomfilter( 10000 );/* */
for ( i=0;
i<10; i++ ) /* url 10 */
{
fprintf( stdout,
"%ld‐>filtered(%d)./n", data[i], bloomfilter_filter(bbf,
(void*)(data+i), strlen(url[i])) );
}
free_bitmap_bloomfilter(
&bbf );/* */
return 0;
}