BloomFilterを使ってみる
http://dev.ariel-networks.com/column/tech/boom_filter/
http://www.perl.com/pub/2004/04/08/bloom_filters.html
hadoopにBloomFilterの実装があったのでそのクラスを使ってみる。
その対象のデータに対して検索したい場合の検索インデックスとしてDBなどに保存するために、BloomFilterを使って生成したbit列をシリアライズする方法も試した。
bit列をもとに同じBloomFilterを復元することもできた。
なんかに使えそう。
/** * */ package jp.co.cyberagent.partner.util; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.DataInputStream; import java.io.DataOutputStream; import java.io.IOException; import junit.framework.Assert; import org.apache.hadoop.util.bloom.BloomFilter; import org.apache.hadoop.util.bloom.Key; import org.apache.hadoop.util.hash.Hash; import org.junit.Test; import org.junit.runner.RunWith; import org.springframework.context.annotation.Configuration; import org.springframework.test.context.ContextConfiguration; import org.springframework.test.context.junit4.SpringJUnit4ClassRunner; /** * @author watanabe_yusaku * */ @RunWith(SpringJUnit4ClassRunner.class) @ContextConfiguration() public class BloomFilterTest { @Configuration static class Config{ } @Test public void test() { //Filterテスト BloomFilter b = new BloomFilter(128, 128, Hash.MURMUR_HASH); b.add(new Key(new String("yuhsaku").getBytes())); b.add(new Key(new String("hiroki").getBytes())); b.add(new Key(new String("yumi").getBytes())); b.add(new Key(new String("kunitaka").getBytes())); b.add(new Key(new String("mitsuko").getBytes())); b.add(new Key(new String("tsuyoshi").getBytes())); Assert.assertTrue(b.membershipTest(new Key("yuhsaku".getBytes()))); Assert.assertFalse(b.membershipTest(new Key("hoge".getBytes()))); //Filterのbit列をシリアライズしてから再度復元してちゃんとFilterできるか確認 BloomFilter rebuildBloomFilter = new BloomFilter(128, 128, Hash.MURMUR_HASH); ByteArrayOutputStream bytearrayOs = new ByteArrayOutputStream(); DataOutputStream s = new DataOutputStream(bytearrayOs); byte[] bytes; try { b.write(s); System.out.println("size:" + s.size()); bytes = new byte[s.size()]; bytes = bytearrayOs.toByteArray(); rebuildBloomFilter.readFields(new DataInputStream(new ByteArrayInputStream(bytes))); }catch(IOException ioe) { Assert.fail(); } Assert.assertTrue(b.membershipTest(new Key("yuhsaku".getBytes()))); Assert.assertFalse(b.membershipTest(new Key("hoge".getBytes()))); } }