読者です 読者をやめる 読者になる 読者になる

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())));
		
	}

}