1.原理理解:
这篇文章相当好:
/maybe2030/p/5203186.html
/qcloud1001/p/10059709.html
理解了整体思路,中间有个地方不好理解:
1.如何分桶,分桶的目的,只是缩小比较次数,尽快找到待比较的文本,进行海明计算:
现在一个text文本,分词处理提取关键词,进行加权算法及simhash处理,变成64位签名串,平均按照位置放入四个桶,找到这个文本对应的其他待比较文本(有任何一个桶是相同的,就是需要的待比较文本)
2.关于比较的方式
1)假设数据量2^34,数据分布到桶里比较均匀,那么每一条数据的重合度大概是2^34/2^16 =262144个候选结果(想象这么多数据的前16位,每个桶里数据是2^16,这样计算就知道每个数据有多少重复的),那么需要比较的次数就是262144*4,这么多相似的数据是需要拿去做海明计算的,这样就不用拿着64位的串,比较2^34次了
待比较次数公式:
count = (2^34)*64/(2^n)*n
n为每个桶多少位
n越大,比较的次数越小,但是越不精准,桶越小越精准
2.代码实现:
/qq_16912257/article/details/72156277
/madujin/article/details/53152619
思路:
1)将每个text文本转化为64位签名
2)对应到4个桶的16位签名,一个64位签名对应4个索引
3)新增的数据,走同样的1、2操作,如果发现有重复的桶,要进行海明距离计算,如果相似,鉴定重复,不插入桶中数据,如果不相似,要进行插入
4)数据存储于内存,持久化一份到表里
5)持久化数据结果:id(你的文本库的文章主键)、simhash、bucket1、bucket2、bucket3、bucket4
6)确定存储方式:id主键,16位签名+bucket_num,值是ids(以逗号隔开),64位simhash以逗号隔开,json存的是
API接口设计:
id,content;持久化写库操作,写内存操作;返回是否重复
另一种存储方式:
mongodb存储数据
{buckethashcode:'dsdfsdsdvsvvsddsdfsdsdvsvvsd',
'simhashcode_id':{'abc...0000':'100'}}
(内存消耗后续可能相当大)
需要计数,文件中,计数一个最大id,以后从这个id往后取数据,取一万条进行计算和处理;
3.思路步骤图
文章(id,title+content)——>分词、权重计算,得出64位sim_hashcode——>分成4个bucket,分别查询,找出需要比较的sim_hashcode——>比较如果有相似,修改数据表状态,存储和之前的相似id;如果没有相似分别存入4个桶对应的16位值
注:多线程情况下,对于内存消耗相当高,需要进行内存的合理分配
1)清洗文章内容:去掉各种标签,只保留文本中文内容
2)拆分方式(准确率如何,取决于自己根据业务场景需求,选取的特定分词方式)
拆分为长文本,比如10个词一组
拆分为词语,使用jieba的TF-IDF方式切分
按照标点符号拆分
分词:使用jieba的TF-IDF,统计每个词的权重,IDF的语料库为jieba默认的idf.txt语料库;查看jieba源码得知,如果语料库不存在该词,默认self.median_idf=11.9547675029,权重值=次数*(self.median_idf/total),total为各个词的次数求和值
经过调整验证,按照标点符号分长句子的方式比较好一点:
处理思路:
1.分为一个一个长段句子;
2.如果最长4句话相同,则认为非常相似文章;
3)根据各个长文本情况,进行64位签名计算
4)计算海明距离
代码参见自己修改的,已上传github,处理速度:500万篇文章/h,最高库里可存储173亿亿篇文章!
4.经过自己实践踩坑后的总结
jieba分词,采用TF-IDF方式,具体分成哪些词,是jieba内部算法设计(有一套词库和词的可达性算法设计),IDF也有jieba内部的语料库进行统计;
分好词及对应的权重之后就比较好进行计算了,加和每个词的64位签名,计算一个统一的simhash值
两个文本的simhash计算海明距离
验证得知:
1.此方法不适合短文本,文本越长统计效果越好
2.此方法敏感度比较高,并非网上说的海明距离<3以内才算相似
有人私信我希望要代码案例,所以我将主体代码写在下面
# @Time : 19/6/25 10:40# @Author : 504747754@(ZengYang)# @File : simhash_worker.py# @Software: PyCharm# @ToUse : simhash的海明计算,单独的算法模型"""maxid——17642803去燥分词(获取中文分词)计算签名(tokens,)海明计算(最快的批量计算方式)如果发现有小于3,即不再计算simhash处理的时候,正则匹配中英文,拆分所有四字短语准确度优化方案:1.拆分短句2.统计短句出现的次数,进行签名计算计算方式:1.从数据库一条条拿数据计算simhash,id,放入redis,修改数据表的持久化状态,否则不做调整2.计算海明距离后,如果相似,记录相似id,并且修改状态3.不相似,不做任何操作"""import jsonimport loggingimport reimport syssys.path.append('../../')import timeimport jieba.analyseimport numpy as npfrom ant_kandian.settings import MYSQL_HOSTfrom ant_kandian.tools.dao_tools import Mysql, RedisMsgQueuestr2 = """"""REDIS_SIM_KEY = 'simkey'CHECK_MAX_ID = 'max_id'ID_SIMHASH_MAP = 'id_simhash'class Simhash_worker():"""用来进行分布式文章去重check"""passdef web_content_filter(content):"""只保留汉字:param content::return:"""reg = r'[\u4e00-\u9fcc]+'# reg = r'[\W\u4e00-\u9fcc]+'content = ''.join(re.findall(reg, content))return contentdef distance_haiming(hash1, hash2):t1 = '0b' + str(hash1)t2 = '0b' + str(hash2)n = int(t1, 2) ^ int(t2, 2)i = 0while n:n &= (n - 1)i += 1return iclass SimhashManager:def __init__(self, content):self.simhash = self.simhash(content)def __str__(self):return str(self.simhash)def simhash(self, content):content = web_content_filter(content)seg = jieba.cut(content)# jieba.analyse.set_stop_words('stopword')# jieba.analyse.set_idf_path(r'my_idf')keyWord = jieba.analyse.extract_tags('|'.join(seg), topK=50, withWeight=True, allowPOS=()) # 在这里对jieba的tfidf.py进行了修改# 将tags = sorted(freq.items(), key=itemgetter(1), reverse=True)修改成tags = sorted(freq.items(), key=itemgetter(1,0), reverse=True)# 即先按照权重排序,再按照词排序keyList = []# print(len(keyWord))# print(keyWord)for feature, weight in keyWord:# weight = int(weight * 100)feature = self.string_hash(feature)temp = []for i in feature:if (i == '1'):temp.append(weight)else:temp.append(-weight)keyList.append(temp)list1 = np.sum(np.array(keyList), axis=0)if (keyList == []): # 编码读不出来return '00'simhash = ''for i in list1:if (i > 0):simhash = simhash + '1'else:simhash = simhash + '0'return simhashdef string_hash(self, source):if source == "":return 0else:x = ord(source[0]) << 7m = 1000003mask = 2 ** 128 - 1for c in source:x = ((x * m) ^ ord(c)) & maskx ^= len(source)if x == -1:x = -2x = bin(x).replace('0b', '').zfill(64)[-64:]return str(x)def distance(self, com):t1 = '0b' + self.simhasht2 = '0b' + com.simhashn = int(t1, 2) ^ int(t2, 2)i = 0while n:n &= (n - 1)i += 1return idef simhash_by_sentence(self, content):simhash = ''return simhashif __name__ == '__main__':this_simhash1 = str(SimhashManager('今年来5.1万电信网络诈骗嫌疑人被抓获 关于诈骗的这些坑必须防范'))this_simhash2 = str(SimhashManager('报告显示:90后被骗概率高 男性比女性更容易上当报告显示:90后被骗概率高 男性比女性更容易上当'))print(distance_haiming(this_simhash1, this_simhash2))
如果觉得《使用simhash进行海量文章数据相似度去重》对你有帮助,请点赞、收藏,并留下你的观点哦!