URL排重之 Bloom Filter算法实现（内存与外存）-Delphi版
{————参考资料———————–
Bloom Filter 数据结构的原理分析
Bloom Filter 数据结构广泛地应用于网络技术中，它是由 Burton Bloom 在 1970 年提出来的。
它的优点是可以有效地节省空间，缺点是不能做到精确无误，不过这个看似很郁闷的缺点却可以使用调节参数的方法有效控制，
也可以通过不同的应用手段来避免差错。Bloom Filter 数据结构有很多应用，将在下一篇文章里叙述，
而这篇文章将简要叙述这个算法的原理和分析。
问题定义：如何用简单节省的方法将一个集合中的所有元素表述出来？
原理：有一个集合 S = ( x1, x2, … , xn), 用一个 n bit 的数组把这个集合表示出来。
使用 k 个独立的哈希函数，将 S 中的每个元素 xi 映射到这个 n bit 的数组中的某一位上，
对于 S 中的每个元素要做 k 次哈希。n bit 的数组初始化每一位为 0 。
如图所示：
0 0 0 0 0 0 0 0 0 0 0 0
x1________|
|
0 1 0 1 0 1 0 1 0 0 1 0
x1′______|
0 1 0 1 0 1 0 1 0 0 1 0
从上图可见，x1 , x2 被映射到 n-bit 中，来了两个查询，x1′ 和 x2′ ，
对这两个查询也分别做 k 个哈希映射，结果 x1′ 对应的值不全是 1 ，
这说明在集合S中肯定不存在和 x1′ 相同的元素。而 x2′ 对应的 bit 都是1，这说明 x2′ 有可能存在于集合中。
但是它不存在的可能性也是有的，因为不能保证不同的元素的哈希值不同。
下面是几个关于 bloom filter 的延伸分析。
1）使用 bloom filter 可以做集合的并、交运算。只需将 n-bit 数组 OR 或 AND 就可以了。
但是结果并不精确。
2）bloom filter 有时会用在描述一个变化的集合上。
添加一个新的集合元素进入 bloom filter 很容易，而删除从集合中删除一个元素，
却不是那么简单，因为会附带着把其他元素的信息也删除掉。为了解决这个问题，
使用多个 bit 位取代使用一个 bit 位。每次映射到这个位置，就加 1 。
}
{——-Bloom Filter 个人的理解及实现方法———————————
Bloom Filter是可作为URL排重算法的一种算法.
它的基本思想来源于Hash表.但又不同.
Hash表的思想是通过散过函数快速定位的Hash桶位置.如果Hash冲突则开链表保存.
基本上一个合适的Hash函数,和合适的Hash桶大小,会使Hash冲突变得很小.
因而Hash表具有极快速的添加,查找,删除功能.也非常适合用于URL排重. 但是Hash表的实现空间效率不好.
而Bloom Filter是一种Hash表思想的延伸.它并不通过Hash表开链表的形式来解决冲突.
而是用多个Hash函数来计算数据,而取得多个Hash数组的下标,并标记,以多个Hash函数的计算结果来稀释冲突的机率.
例如用10个Hash函数分别计算同一个数据,而得到10个数组下标,通过判断这十个下标相对应的标记位的标记即可判断是否存在.
我的实现方法是这样的,申请一块大内存作为数组,数组每个单位为2个字节即16位的空间,用于保存10种不同Hash算法的标记位.
数组起始地址.
FBasePointer
那 数组第I个单位的超始位置即为 FBasePointer +2*I
}
{类设计说明:
THashFuncMan 为一个Hash函数的调用结构体,同时定义Hash函数,编号和计算结果.方便使用.
IBloomFilter为算法算法,各种不同的程序可通过实现该接口来保证接口统一.
TBloomFilterBase 自己实现了10种Hash算法的一个基类.各种存储类可通过继承它来实现.当然,也可以用组合.
TPointerBloomFilterBase -> (TBloomFilterBase,IBloomFilter) 比较完整实现了IBloomFilter算法的类. 但它操作的指针为虚拟.要子类为指针指定内容.
TMemoryBloomFilter->TPointerBloomFilterBase 内存存储方式的BloomFilter算法实现类
TMemoryFileBloomFilter->BloomFilter 内存映射文件存储方式的BloomFilter算法实现类,外存
}
unit uBloomFilter;
interface
uses
Classes, SysUtils, Windows, MD5, SyncObjs, SHA1;
const
MaxHashFuncCount = 10;
type
//计算Hash数组下标的函数形式
//备注:该定义为通用方式,而我在下面的代码应用中的散列函数的实现中并没有用到其中的参数
TGetHashIndexFunc = function(ABuffer: PChar; ALen: Integer; AMaxCount:
TGetHashIndexEvent = function(ABuffer: PChar; ALen: Integer; AMaxCount:
//Hash数组计算对象,关链函数和编号
THashFuncMan = record
end;
{————–BloomFilter算法接口————————}
IBloomFilter = interface
['{F8E72812-E7CD-4460-9549-7920A9C762C4}']
end;
{————BloomFilter 的Hash算法实现的类———————————–
—————————————————————————–}
TBloomFilterBase = class(TInterfacedObject)
private
protected
public
end;
{————指针操作数组的BloomFilter实现的虚类———–}
TPointerBloomFilterBase = class(TBloomFilterBase, IBloomFilter)
private
protected
public
end;
{————使用内存数组的的BloomFilter实现的类———–}
TMemoryBloomFilter = class(TPointerBloomFilterBase)
public
end;
{————使用外存文件,用内存映射文件的的BloomFilter实现的类———–}
TMemoryFileBloomFilter = class(TPointerBloomFilterBase)
private
public
end;
implementation
{ TBloomFilterBase }
{—————10个取得Hash数组下标的函数——————-}
constructor TBloomFilterBase.Create(AMaxCount : Cardinal);
var
I : Integer;
begin
inherited Create;
//—-初始化计算Hash下标的函数组– 如果修改 MaxHashFuncCount 这里也要修改
HashFuncMans[0].GetHashIndexFunc := GetHashIndexFunc0;
HashFuncMans[1].GetHashIndexFunc := GetHashIndexFunc1;
HashFuncMans[2].GetHashIndexFunc := GetHashIndexFunc2;
HashFuncMans[3].GetHashIndexFunc := GetHashIndexFunc3;
HashFuncMans[4].GetHashIndexFunc := GetHashIndexFunc4;
HashFuncMans[5].GetHashIndexFunc := GetHashIndexFunc5;
HashFuncMans[6].GetHashIndexFunc := GetHashIndexFunc6;
HashFuncMans[7].GetHashIndexFunc := GetHashIndexFunc7;
HashFuncMans[8].GetHashIndexFunc := GetHashIndexFunc8;
HashFuncMans[9].GetHashIndexFunc := GetHashIndexFunc9;
for I := 0 to MaxHashFuncCount – 1 do
FLock := TCriticalSection.Create;
FMaxCount := AMaxCount;
end;
destructor TBloomFilterBase.Destroy;
begin
FLock.Leave;
inherited;
end;
procedure TBloomFilterBase.CelHashIndex(AStr: string);
var
I: Integer;
begin
FLock.Enter;
try
finally
end;
end;
function TBloomFilterBase.GetHashIndexFunc0(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
var
I: Integer;
begin
//使用MD5
Result := 0;
for I := 0 to 3 do
Result := Result mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc1(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FMD5Digest.A) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc2(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FMD5Digest.B) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc3(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FMD5Digest.C) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc4(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result :=Cardinal(FMD5Digest.D) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc5(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FSHADigest.A) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc6(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FSHADigest.B) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc7(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FSHADigest.C) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc8(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FSHADigest.D) mod FMaxCount;
end;
function TBloomFilterBase.GetHashIndexFunc9(ABuffer: PChar; ALen:
Integer; AMaxCount: Cardinal):
Cardinal;
begin
Result := Cardinal(FSHADigest.E) mod FMaxCount;
end;
{ TPointerBloomFilterBase }
constructor TPointerBloomFilterBase.Create(AMaxCount: Integer);
var
I: Integer;
begin
inherited Create(AMaxCount);
//保存大小
FLock := TCriticalSection.Create;
end;
destructor TPointerBloomFilterBase.Destroy;
begin
FLock.Free;
inherited;
end;
function TPointerBloomFilterBase.FilterData(AStr: string;
AAutoAdd: Boolean): Boolean;
var
I: Integer;
begin
//临界保护读写.
FLock.Enter;
try
//计算Hash下标
finally
end;
end;
function TPointerBloomFilterBase.GetMaxCount: Cardinal;
begin
Result := FMaxCount;
end;
{ TMemoryBloomFilter }
constructor TMemoryBloomFilter.Create(AMaxCount: Integer);
begin
inherited Create(AMaxCount);
GetMem(FBasePointer, FMaxCount * 2);
end;
destructor TMemoryBloomFilter.Destroy;
begin
FreeMem(FBasePointer, FMaxCount * 2 );
inherited;
end;
{ TMemoryFileBloomFilter }
constructor TMemoryFileBloomFilter.Create(AFileName: string;
AMaxCount: Integer; ACreateNew: Boolean);
begin
inherited Create(AMaxCount);
if (not ACreateNew) and (not FileExists(AFileName)) then
if ACreateNew then
begin
end
else
begin
end;
if hFile = INVALID_HANDLE_VALUE then
hFileMap := CreateFileMapping(hFile, nil, PAGE_READWRITE, 0, FMaxCount *
if hFileMap = 0 then
FBasePointer := MapViewOfFile(hFileMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);
if not Assigned(FBasePointer) then
end;
destructor TMemoryFileBloomFilter.Destroy;
begin
FlushViewOfFile(FBasePointer, 0);
UnmapViewOfFile(FBasePointer);
CloseHandle(hFileMap);
CloseHandle(hFile);
inherited;
end;
end.
undefined
测试结果:
procedure TForm1.btnTestURLClick(Sender: TObject);
var
BloomFilter : IBloomFilter;
I : Integer;
Count : Integer;
SueeCount : Integer;
ErrorCount : Integer;
begin
qry1.Close;
qry1.SQL.Text := ‘Select DISTINCT Url From Song’;
qry1.Open;
Count := qry1.RecordCount;
qry1.First;
BloomFilter := TMemoryBloomFilter.Create(Count*4);
while not qry1.Eof do
begin
end;
qry1.Close;
lbledtTestCount.Text := IntToStr(Count);
lbledtSuee.Text := IntToStr(SueeCount);
lbledtError.Text := IntToStr(ErrorCount);
lbledtScal.Text := FloatToStr(ErrorCount/SueeCount);
end;
以上是测试的函数,数组大小为测试数据的4倍大小.
测试结果:
测试URL数:97301
不重复数:97300
冲突数:1
冲突比例:1.02774922918808E-5
