河北省住房和城乡建设厅网站查,ps设计师网站,简阳网站建设,网络推广app是违法的吗目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信…
目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信息摘要 hash 算法介绍3.2 信息摘要 hash 算法去重方案实现3.3 基于 simhash 算法的去重3.3.1 Simhash 介绍以及应用场景3.3.2 Simhash 的特征3.3.3 Simhash 值得比对3.3.4 示例代码四、布隆过滤器原理与实现4.1 布隆过滤器 (bloomfilter) 原理4.2 布隆过滤器实现一、概要
去重应用场景以及基本原理基于信息摘要算法的去重基于 simhash 算法的去重布隆过滤器原理与实现
二、去重应用场景以及基本原理
2.1 爬虫中什么业务需要使用去重
防止发出重复的请求防止存储重复的数据
2.2 去重实现的基本原理
根据给定的 判断依据 和给定的 去重容器将原始数据逐一进行判断判断去重容器中是否有该数据。如果没有那就把该数据对应的判断依据添加去重容器中同时标记该数据是不重复数据如果有就不添加同时标记该数据是重复数据。
重点
判断依据原始数据、原始数据特征值)去重容器存储判断数据) set()
2.3 根据原始数据进行去重判断 2.4 根据原始数据的特征值进行去重判断 思考为什么要用原始数据的特征值进行判断? 理解1、节省存储空间 2、比对更加快捷高效 2.5 临时去重容器与持久化去重容器 临时去重容器指如利用 list、set 等编程语言的数据结构存储去重数据一旦程序关闭或重启后去重容器中的数据就被回收了。使用与实现简单方便但无法共享、无法持久化。 持久化去重容器指如利用 redis、mysql 等数据库存储去重数据。持久化、共享但使用与实现相对复杂 2.6 常用几种特殊的原始数据特征值计算
信息摘要 hash 算法(指纹)SimHash 算法布隆过滤器方式
三、基于信息摘要算法的去重
3.1 信息摘要 hash 算法介绍
信息摘要 hash 算法指可以将任意长度的文本、字节数据通过一个算法得到一个固定长度的文本。如 MD5(128位)、SHA1(160位) 等。 特征只要源文本不同计算得到的结果必然不同(摘要)。 摘要摘要算法主要用于比对信息源是否一致因为只要源发生变化得到的摘要必然不同而且通常结果要比源短很多所以称为 摘要。正因此利用信息摘要算法能大大降低去重容器的存储空间使用率并提高判断速度直由于其强唯—性的特征几乎不存在误判。 注意 hash 算法得出的结果其实本质上就是一串数值如 md5 的128位指的是二进制的长度十六进制的长度是32位。一个十六进制等于四个二进制。
3.2 信息摘要 hash 算法去重方案实现
基类的实现
# 基于信息摘要算法进行数据的去重判断和存储# 1. 基于内存的存储
# 2. 基于redis的存储
# 3. 基于mysql的存储import hmacclass BaseFilter(object):基于信息摘要算法进行数据的去重判断和存储def __init__(self,digest_modMD5,redis_hostlocalhost,redis_port6379,redis_db0,redis_keyfilter,mysql_urlNone,mysql_table_namefilter):self.redis_host redis_hostself.redis_port redis_portself.redis_db redis_dbself.redis_key redis_keyself.mysql_url mysql_urlself.mysql_table_name mysql_table_name# self.key self.digest_mod digest_modself.storage self._get_storage()def _safe_data(self, data)::param data: 给定的原始数据:return: 二进制类型的字符串数据if isinstance(data, bytes):return dataelif isinstance(data, str):return data.encode()else:raise Exception(please provide a string...)def _get_hash_value(self, data):根据给定的数据返回的对应信息摘要hash值:param data: 给定的原始数据二进制类型的字符串数据:return: hash值data self._safe_data(data)key amoxiang666.encode(utf8)hash_obj hmac.new(key, data, digestmodself.digest_mod)hash_value hash_obj.hexdigest()return hash_valuedef save(self, data):根据data计算出对应的指纹进行存储:param data: 给定的原始数据:return: 存储的结果hash_value self._get_hash_value(data)return self._save(hash_value)def _save(self, hash_value):存储对应的hash值交给对应的子类去继承:param hash_value: 通过信息摘要算法求出的hash值:return: 存储的结果passdef is_exists(self, data):判断给定的数据对应的指纹是否存在:param data: 给定的原始数据:return: True or Falsehash_value self._get_hash_value(data)return self._is_exists(hash_value)def _is_exists(self, hash_value):判断对应的hash值是否已经存在交给对应的子类去继承:param hash_value: 通过信息摘要算法求出的hash值:return: 判断的结果True or Falsepassdef _get_storage(self):返回对应的一个存储对象交给对应的子类去继承:return:passfrom .mysql_filter import MySQLFilter
from .memory_filter import MemoryFilter
from .redis_filter import RedisFilter普通内存版本
# 基于python中的 集合数据结构进行去重判断依据的存储
from . import BaseFilterclass MemoryFilter(BaseFilter):基于python中的 集合数据结构进行去重判断依据的存储def _get_storage(self):return set()def _save(self, hash_value):利用set进行存储:param hash_value::return:return self.storage.add(hash_value)def _is_exists(self, hash_value):if hash_value in self.storage:return Truereturn FalseRedis 持久化版
# 基于redis的持久化存储的去重判断依据的实现
import redisfrom . import BaseFilterclass RedisFilter(BaseFilter):基于redis的持久化存储的去重判断依据的实现def _get_storage(self):返回一个redis连接对象pool redis.ConnectionPool(hostself.redis_host, portself.redis_port, dbself.redis_db)client redis.StrictRedis(connection_poolpool)return clientdef _save(self, hash_value):利用redis的无序集合进行存储:param hash_value::return:return self.storage.sadd(self.redis_key, hash_value)def _is_exists(self, hash_value):判断redis对应的无序集合中是否有对应的判断依据return self.storage.sismember(self.redis_key, hash_value)MySQL 持久化版本
# 基于mysql的去重判断依据的存储from sqlalchemy import create_engine, Column, Integer, String
from sqlalchemy.orm import sessionmaker
from sqlalchemy.ext.declarative import declarative_basefrom . import BaseFilterBase declarative_base()class MySQLFilter(BaseFilter):基于mysql的去重判断依据的存储def __init__(self, *args, **kwargs):self.table type(kwargs[mysql_table_name],(Base,),dict(__tablename__kwargs[mysql_table_name],idColumn(Integer, primary_keyTrue),hash_valueColumn(String(40), indexTrue, uniqueTrue)))BaseFilter.__init__(self, *args, **kwargs)def _get_storage(self):返回一个mysql连接对象(sqlalchemy的数据库连接对象)engine create_engine(self.mysql_url)Base.metadata.create_all(engine) # 创建表、如果有就忽略Session sessionmaker(engine)return Sessiondef _save(self, hash_value):利用redis的无序集合进行存储:param hash_value::return:session self.storage()filter self.table(hash_valuehash_value)session.add(filter)session.commit()session.close()def _is_exists(self, hash_value):判断redis对应的无序集合中是否有对应的判断依据session self.storage()ret session.query(self.table).filter_by(hash_valuehash_value).first()session.close()if ret is None:return Falsereturn True测试
# python3
from information_summary_filter import MemoryFilter
from information_summary_filter import RedisFilter
from information_summary_filter import MySQLFilter# filter MemoryFilter()
# filter RedisFilter(redis_keytest1)
mysql_url mysqlpymysql://root:123456127.0.0.1:3306/db_admin?charsetutf8
filter MySQLFilter(mysql_urlmysql_url, mysql_table_nametest20230319)data [111, qwe, 222, 333, 111, qwe, 中文, qwer]for d in data:if filter.is_exists(d):print(发现重复的数据: , d)else:filter.save(d)print(保存去重的数据, d)3.3 基于 simhash 算法的去重
3.3.1 Simhash 介绍以及应用场景
Simhash 算法是一种局部敏感哈希算法能实现 相似 文本内容的去重。比如下列两篇新闻数据
3.3.2 Simhash 的特征
与信息摘要算法的区别
信息摘要算法如果原始内容只相差一个字节所产生的签名也很可能差别很大。Simhash 算法如果原始内容只相差一个字节所产生的签名差别非常小。
Simhash 值比对通过两者的 simhash 值的二进制位的差异来表示原始文本内容的差异。差异个数又被称为 海明距离。 注意Simhash 对长文本 500字 比较适用短文本可能偏差较大。在google的论文给出的数据中64位simhash值在海明距离为3的情况下可认为两篇文档是相似的或者是重复的。当然这个值只是参考值针对自己的应用可能有不同的测试取值。 3.3.3 Simhash 值得比对
Python 实现的 simhash 算法。该模块得出的 simhash 值长度正是64位。https://github.com/leonsim/simhash
如对比前面列出的人民网和中国网的两篇相似新闻(以下值仅供参考)。128位MD5值 64位simhash值
3.3.4 示例代码
import re
from simhash import Simhash, SimhashIndexdef get_features(s):width 3s s.lower()s re.sub(r[^\w], , s)return [s[i:i width] for i in range(max(len(s) - width 1, 1))]data {key1: uHow are you? I Am fine. blar blar blar blar blar Thanks.,key2: uHow are you i am fine. blar blar blar blar blar than,key3: uThis is simhash test.,4: uHow are you i am fine. blar blar blar blar blar thank
}
objs [(str(k), Simhash(get_features(v))) for k, v in data.items()
]
print(objs)
index SimhashIndex(objs, k4) # k相当于海明距离print(index.bucket_size()) # 11s1 Simhash(get_features(uHow are you i am fine. blar blar blar blar blar thank))
print(index.get_near_dups(s1)) # [1]index.add(4, s1)
print(index.get_near_dups(s1)) # [4, 1]# 二进制位的比对 只能在内存中进行
# 序列化工具 将一个对象转换为二进制的一个数据
# 反序列化二进制-- 对象四、布隆过滤器原理与实现
4.1 布隆过滤器 (bloomfilter) 原理 4.2 布隆过滤器实现
Python 实现的内存版布隆过滤器 pybloom参考地址https://github.com/jaybaird/python-bloomfilter
手动实现的 redis 版布隆过滤器示例代码如下
# -*- coding: utf-8 -*-
# Time : 2023-03-23 23:28
# Author : AmoXiang
# File : test.py
# Software: PyCharm
# Blog : https://blog.csdn.net/xw1680# 布隆过滤器 redis版本实现
import hashlibimport redis
import six# 1. 多个hash函数的实现和求值
# 2. hash表实现和实现对应的映射和判断class MultipleHash(object):根据提供的原始数据和预定义的多个salt生成多个hash函数值def __init__(self, salts, hash_func_namemd5):self.hash_func getattr(hashlib, hash_func_name)if len(salts) 3:raise Exception(please give three salt at least....)self.salts saltsdef get_hash_values(self, data):根据提供的原始数据, 返回多个hash函数值hash_values []for i in self.salts:hash_obj self.hash_func()hash_obj.update(self._safe_data(data))hash_obj.update(self._safe_data(i))ret hash_obj.hexdigest()hash_values.append(int(ret, 16))return hash_valuesdef _safe_data(self, data)::param data: 给定的原始数据:return: 二进制类型的字符串数据if isinstance(data, bytes):return dataelif isinstance(data, str):return data.encode()else:raise Exception(please give string....) # 建议使用英文来描述class BloomFilter(object):def __init__(self, salts, redis_hostlocalhost, redis_port6379, redis_db0, redis_keybloomfilter):self.redis_host redis_hostself.redis_port redis_portself.redis_db redis_dbself.redis_key redis_keyself.client self._get_redis_client()self.multiple_hash MultipleHash(salts)def _get_redis_client(self):返回一个redis连接对象pool redis.ConnectionPool(hostself.redis_host, portself.redis_port, dbself.redis_db)client redis.StrictRedis(connection_poolpool)return clientdef save(self, data):hash_values self.multiple_hash.get_hash_values(data)for hash_value in hash_values:offset self._get_offset(hash_value)self.client.setbit(self.redis_key, offset, 1)return Truedef is_exists(self, data):hash_values self.multiple_hash.get_hash_values(data)for hash_value in hash_values:offset self._get_offset(hash_value)v self.client.getbit(self.redis_key, offset)if v 0:return Falsereturn Truedef _get_offset(self, hash_value):# 2**8 256# 2**20 1024 * 1024# (2**8 * 2**20 * 2*3) 代表hash表的长度 如果同一项目中不能更改return hash_value % (2 ** 8 * 2 ** 20 * 2 * 3)if __name__ __main__:data [asdfasdf, 123, 123, 456, asf, asf]bm BloomFilter(salts[1, 2, 3, 4], redis_host172.17.0.2)for d in data:if not bm.is_exists(d):bm.save(d)print(映射数据成功 , d)else:print(发现重复数据, d)
