using System;
using System.Collections;
using System.Text;
using NUnit.Framework;
namespace OurAlgorithmCollections
{
public class BloomFilter
{
/// <summary>
/// BitArray用来替代内存块,在C/C++中可使用BITMAP替代
/// </summary>
private static BitArray bitArray = null;
private int size = -1;
/// <summary>
/// 构造函数,初始化分配内存
/// </summary>
/// <param name="size">分配的内存大小,必须保证被2整除</param>
public BloomFilter(int size)
{
if (size % 2 == 0)
{
bitArray = new BitArray(size, false);
this.size = size;
}
else
{
throw new Exception("错误的长度,不能被2整除");
}
}
/// <summary>
/// 将str加入Bloomfilter,主要是HASH后找到指定位置置true
/// </summary>
/// <param name="str">字符串</param>
public void Add(string str)
{
int[] offsetList = getOffset(str);
if (offsetList != null)
{
put(offsetList[0]);
put(offsetList[1]);
}
else
{
throw new Exception("字符串不能为空");
}
}
/// <summary>
/// 判断该字符串是否重复
/// </summary>
/// <param name="str">字符串</param>
/// <returns>true重复反之则false</returns>
public Boolean Contains(string str)
{
int[] offsetList = getOffset(str);
if (offsetList != null)
{
if ((get(offsetList[0]) == true) && (get(offsetList[1]) == true))
{
return true;
}
}
return false;
}
/// <summary>
/// 返回内存块指定位置状态
/// </summary>
/// <param name="offset">位置</param>
/// <returns>状态为TRUE还是FALSE 为TRUE则被占用</returns>
private Boolean get(int offset)
{
return bitArray[offset];
}
/// <summary>
/// 改变指定位置状态
/// </summary>
/// <param name="offset">位置</param>
/// <returns>改变成功返回TRUE否则返回FALSE</returns>
private Boolean put(int offset)
{
//try
//{
if (bitArray[offset])
{
return false;
}
bitArray[offset] = true;
//}
//catch (Exception e)
//{
// Console.WriteLine(offset);
//}
return true;
}
private int[] getOffset(string str)
{
if (String.IsNullOrEmpty(str) != true)
{
int[] offsetList = new int[2];
string tmpCode = Hash(str).ToString();
int hashCode = Hash2(tmpCode);
int offset = Math.Abs(hashCode % (size / 2) - 1);
offsetList[0] = offset;
hashCode = Hash3(str);
offset = size - Math.Abs(hashCode % (size / 2))-1;
offsetList[1] = offset;
return offsetList;
}
return null;
}
/// <summary>
/// 内存块大小
/// </summary>
public int Size
{
get { return size;}
}
/// <summary>
/// 获取字符串HASHCODE
/// </summary>
/// <param name="val">字符串</param>
/// <returns>HASHCODE</returns>
private int Hash(string val)
{
return val.GetHashCode();
}
/// <summary>
/// 获取字符串HASHCODE
/// </summary>
/// <param name="val">字符串</param>
/// <returns>HASHCODE</returns>
private int Hash2(string val)
{
int hash = 0;
for (int i = 0; i < val.Length; i++)
{
hash += val[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
/// <summary>
/// 获取字符串HASHCODE
/// </summary>
/// <param name="val">字符串</param>
/// <returns>HASHCODE</returns>
private int Hash3(string str)
{
long hash = 0;
for (int i = 0; i < str.Length; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ str[i] ^ (hash >> 5)));
}
}
unchecked
{
return (int)hash;
}
}
}
[TestFixture]
public class TestBloomFilter
{
System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
BloomFilter bf = new BloomFilter(10485760);
const int maxNum=100000;
double count = 0;
[Test]
public void TestAdd()
{
watch.Reset();
watch.Start();
for (int i = 0; i <maxNum; i++)
{
if (bf.Contains(i.ToString()) != true)
{
bf.Add(i.ToString());
}
else
{
//Console.Write("发生碰撞数字:");
//Console.WriteLine(i);
count++;
}
}
watch.Stop();
Console.WriteLine("碰撞概率:"+ (count/(double)maxNum*100) + "%");
Console.Write("运行时间:");
Console.WriteLine(watch.ElapsedMilliseconds.ToString() + "ms");
}
}
}
BloomFilter中文布隆过滤器,主要应用于消重和拼写检查,以上实例实现了一个针对字符串重复检查的过滤器,具体碰撞概率跟内存分配大小及HASH函数有关,可通过增加HASH函数次数或增加内存分配来减小碰撞,具体测试方式可参考测试代码。
其算法主要是通过整块的内存申请,得到线性的连续空间,该空间所有位置上默认状态为0,对待测试重复的对象HASH后取模,模数为内存块的大小以控制取模后的值范围在内存可分配范围内,取模的值对应位置上改变状态为1,通过对测试对象重复前面的HASH 取模 对应位置改变状态为1的方式来保存对象在空间内的状态,如有测试对象所有对应空间位置的状态为1则可判断该对象存在重复。 [Last Modified By King, at 2008-03-07 15:40:57]
分享到:
相关推荐
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
C# 海量数据处理算法BloomFilter算法的实现和测试例子;C# 海量数据处理算法BloomFilter算法的实现和测试例子
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
基于bloomfilter算法的c语言实验的url去重。使用的时候被去重的文件需要是txt格式的。
C语言实现的Bloomfilter算法。
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地...因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。
转载:基于Bloom-Filter算法的URL过滤器的实现,算法简介,基本思想,应用,具体实现(C代码)
主要介绍了PHP中实现Bloom Filter算法,本文直接给出实现代码,代码中给出详细注释,Bloom Filter算法介绍等内容,需要的朋友可以参考下
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
#资源达人分享计划#
bloomfilter.js, 使用FNV的JavaScript bloom filter快速散列 Bloom过滤器This过滤器实现使用非加密 Fowler-Noll-Vo散列函数来实现速度。用法var bloom = new BloomFilter( 32 * 256,//number of bits to all
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
针对流与流之间传输的公平性问题,基于BLUE算法,结合Bloom filter,提出了一种改进的AQM算法EFBLUE。通过仿真实验对新算法从分组丢失率、吞吐量、延时等方面的性能进行了测试并与RED算法进行了性能对比。NS2仿真实验...
提出一种针对动态集合的矩阵型Bloom filter表示与查找法(matrix Bloom filter,MBF),它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。
linux下编写的网络爬虫,可以实现bloom filter 去重过滤,不过是用来垂直爬取www.8684.cn网站的。运行的时候请输入www.8684.cn
Bloom Filter 在数据库系统的应用