布隆过滤器的一个实战小例子

问题是这样的：现在服务器端有两个文件夹，里面的文件都是文件名为MD5后的字符串并且没有文件后缀。这两个文件夹里有少部分重复的文件（指文件名重复即认为重复）并且少量文件存在后缀名（这个也是不需要的）

一共有200万到300万的文件，20多个GB。

如果考虑速度的话最好可以使用hash表，但是几百万的文件建立map要消耗很大的空间，这里牺牲一定的准确性采用布隆过滤器

#!/usr/bin/python
# -*- coding: utf-8 -*-
# author:shq
import BitVector
import os
class Hash(object): # 哈希函数用来将元素映射到位向量中
def __init__(self, bit_size, seed):
self.bit_size = bit_size
self.seed = seed
def hash(self, string):
result = 0
for i in xrange(len(string)):
result += self.seed * result + ord(string[i]) # 哈希值计算公式
# 把hash值映射到比特向量中，&位运算保证返回的整数小于bit_size-1(不等0时)
return (self.bit_size - 1) & result
class Bloom_Filter(object):
'''
这个布隆过滤器首先需要：
1、一个位向量
2、n个种子用来生成hash函数
3、n个hash函数（用来映射位置）
'''
def __init__(self):
self.BIT_SIZE = 1 <<21
self.bitset = BitVector.BitVector(size=self.BIT_SIZE)
self.seeds = [12, 23, 34, 45, 56, 67, 78, 89]
self.hash_fun_list = [Hash(self.BIT_SIZE, seed) for seed in self.seeds]
def insert(self, string):
for hash_fun in self.hash_fun_list:
i = hash_fun.hash(string)
self.bitset[i] = 1
def judge_exist(self, string):
if string is None:
return False
for hash_fun in self.hash_fun_list:
i = hash_fun.hash(string)
if self.bitset[i] == 0:
return False
return True
def get_file_name(file_dir_1, file_dir_2):
'''
:param file_dir_1: 存储进过滤器的文件夹
:param file_dir_2: 被查找的文件夹
:return:
'''
test_BF = Bloom_Filter()
# 文件夹1的文件映射进过滤器
for _, _, files in os.walk(file_dir_1):
for file in files:
if '.' in file: # 去除后缀
os.rename(file_dir_1 + '/' + file, file_dir_1 + '/' + file.split('.')[0])
file = file.split('.')[0]
test_BF.insert(file)
# 判断文件夹2的文件是存在于过滤器
for _, _, files in os.walk(file_dir_2):
for file in files:
if '.' in file: # 去除后缀
os.rename(file_dir_2 + '/' + file, file_dir_2 + '/' + file.split('.')[0])
file = file.split('.')[0]
if test_BF.judge_exist(file):
change_time_1 = os.stat(file_dir_1 + '/' + file).st_mtime
change_time_2 = os.stat(file_dir_2 + '/' + file).st_mtime
if change_time_1 > change_time_2:
print u'删除：',file_dir_2 + '/' + file
os.remove(file_dir_2 + '/' + file)
else:
print u'删除：', file_dir_1 + '/' + file
os.remove(file_dir_1 + '/' + file)