数据去重方法

hash序列化过滤

使用hash哈希方法去重的场景

当数据量不大的时候，并且数据所占内存不多的时候
当只有几万条url去重的时候，可以直接使用hash+redis的set类型进行数据的去重

使用sha1-redis去重的实例

import hashlib

import redis

from redis import *

class Filter_hash(object):

# 创建redis客户端对象

sr = StrictRedis(host='localhost', port=6379, db=0)

# 定义存储hash后数据的key_name

key = 'hash_list'

def add_hash_num(self, key_name，url):

# 创建一个哈希对象

fp = hashlib.sha1()

# 对url进行哈希序列化

fp.update(url)

fp_num = fp.hexdiget()

# 将十六进制后的序列化的hash数值进行存储

added = self.server.sadd(self.key, fp_num)

return added # 如果插入成功，返回1，表示数据不重复插入成功，否则返回0

filter_cur = Filter_hash()

if __name__ == '__main__':

filter_cur.add_hash_num('url'， 'https://www.baidu.com')

bloom-布隆过滤

什么是布隆过滤器

是一种space efficient的概率模型数据结构，用于判断一个元素是否在集合中。
一个空的布隆过滤器是一个m bit的bitmap，每一位都初始化为0。布隆过滤器定义有k个hash函数，对输入的数据生成k个hash值，定义一个map函数将k个hash值映射到bitmap的k个位。

bitmap数据类型

bitmap介绍

Bitmap不是一个确切的数据类型，而是基于String类型定义的一系列面向位操作的方法。因为String是二进制安全的并且它们的最大长度是512MB，所以String类型很合适去作为一个2^32长度的位数组。

位操作方法可以被分为两组：

一、对单一位的操作，比如设置某一位为1或0，或者得到这一位的值；
二、对一组位的操作，比方说计算一定范围内的1的个数（比如计数）

bitmap的应用场景

bitmap一个最大的优势是它通常能在存储信息的时候节省大量空间。比方说一个用增量ID来辨别用户的系统，可以用仅仅512MB的空间来标识40亿个用户是否想要接受通知。

使用SETBIT和GETBIT命令来对位进行置数和检索（redis中实现的bitmap类型数据的操作）

> setbit key 10 1
(integer) 1
> getbit key 10
(integer) 1
> getbit key 11
(integer) 0
返回的是该位上之前的数值
SETBIT 如上所示，意思是将第10位置位为1，第二个参数可为0或1。如果设置的位超出了当前String的长度，那么会自动增长。（最长2^32，下同）
GETBIT 如上所示，返回第10位和第11位的数据，分别是1和0。如果查找的位超出了当前String的长度，那么会返回0。
接下来是三个对一组位进行操作的命令:
BITOP 执行不同字符串之间的逐位操作。所提供的操作有AND，OR，XOR和NOT。BITCOUNT
BITCOUNT 计数,返回bitmap里值为1的位的个数.
BITPOS 返回第一个0或1的位置
BITPOS和BITCOUNT不仅可以作用于整个bitmap，还可以作用于一定的范围,下面是一个BITCOUNT的例子

布隆过滤的原理

布隆过滤器需要的是一个位数组(和位图类似)和K个映射函数(和Hash表类似)，在初始状态时，对于长度为m的位数组array，它的所有位被置0

对于有n个元素的集合S={S1,S2...Sn},通过k个映射函数{f1,f2,......fk}，将集合S中的每个元素Sj(1<=j<=n)映射为K个值{g1,g2...gk}，然后再将位数组array中相对应的array[g1],array[g2]......array[gk]置为1：

如果要查找某个元素item是否在S中，则通过映射函数{f1,f2,...fk}得到k个值{g1,g2...gk}，然后再判断array[g1],array[g2]...array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。

布隆过滤优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。
布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
k 和 m 相同，使用同一组 Hash 函数的两个布隆过滤器的交并差运算可以使用位操作进行。

缺点

误算率（False Positive），随着存入的元素数量增加，错判“在集合内”的概率就越大了，误算率随之增加。
一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

布隆过滤器的应用场景

在对大量的数据进行去重的时候，可以使用布隆过滤器判断元素是否已经在集合中，通过判断的结果，来对数据进行相应的操作

布隆过滤实现（包在下方）

构造HashMap类

这里新建了一个HashMap类。构造函数传入两个值，一个是m位数组的位数，另一个是种子值seed。不同的散列函数需要有不同的seed，这样可以保证不同的散列函数的结果不会碰撞。
在hash()方法的实现中，value是要被处理的内容。这里遍历了value的每一位，并利用ord()方法取到每一位的ASCII码值，然后混淆seed进行迭代求和运算，最终得到一个数值。这个数值的结果就由value和seed唯一确定。
我们再将这个数值和m进行按位与运算，即可获取到m位数组的映射结果，这样就实现了一个由字符串和seed来确定的散列函数。
当m固定时，只要seed值相同，散列函数就是相同的，相同的value必然会映射到相同的位置。
所以如果想要构造几个不同的散列函数，只需要改变其seed就好了。以上内容便是一个简易的散列函数的实现。

构造BloomFilter

Bloom Filter里面需要用到k个散列函数，这里要对这几个散列函数指定相同的m值和不同的seed值
由于我们需要亿级别的数据的去重，即前文介绍的算法中的n为1亿以上，散列函数的个数k大约取10左右的量级

实现判断元素是否重复和添加元素到集合的方法

insert方法

Bloom Filter算法会逐个调用散列函数对放入集合中的元素进行运算，得到在m位位数组中的映射位置，然后将位数组对应的位置置1。
这里代码中我们遍历了初始化好的散列函数，然后调用其hash()方法算出映射位置offset，再利用Redis的setbit()方法将该位置1。

exit方法

我们要实现判定是否重复的逻辑，方法参数value为待判断的元素。我们首先定义一个变量exist，遍历所有散列函数对value进行散列运算，得到映射位置，用getbit()方法取得该映射位置的结果，循环进行与运算。
这样只有每次getbit()得到的结果都为1时，最后的exist才为True，即代表value属于这个集合。如果其中只要有一次getbit()得到的结果为0，即m位数组中有对应的0位，那么最终的结果exist就为False，即代表value不属于这个集合。