simhash海量文本去重的工程化

article/2025/6/4 0:25:30

https://yuerblog.cc/2018/05/30/simhash-text-unique-arch/

simhash算法是google发明的,专门用于海量文本去重的需求,所以在这里记录一下simhash工程化落地问题。

下面我说的都是工程化落地步骤,不仅仅是理论。

背景

互联网上,一篇文章被抄袭来抄袭去,转载来转载去。

被抄袭的文章一般不改,或者少量改动就发表了,所以判重并不是等于的关系,而是相似判断,这个判别的算法就是simhash。

simhash计算

给定一篇文章内容,利用simhash算法可以计算出一个哈希值(64位整形)。

判别两篇文章是相似的方法,就是两个simhash值的距离<=3,这里距离计算采用汉明距离,也就是2个simhash做一下异或运算,数一下比特位=1的有N位,那么距离就是N。

现在问题就是,如何计算文本的simhash?

分词+权重

首先需要将文章作分词,得到若干个(词组,权重)。

分词我们知道很多库都可以实现,最常见的就是结巴分词。权重是怎么得来的呢?

权重一般用TF/IDF算法,TF表示词组在本文章内的频次比例,出现越多则对这篇文章来说越重要,文章分词后TF可以立马计算出来。

IDF是词组在所有文章中的出现比例,出现越多说明词组对文章的区分度越低越不重要,但是IDF因为需要基于所有文章统计,所以一般是离线去批量计算出一个IDF字典。

结巴分词支持加载IDF词典并且提供了一个默认的词典,它包含了大量的词组以及基于海量文本统计出来的IDF词频,基本可以拿来即用,除非你想自己去挖掘这样一个字典。如果文章产生的分词在IDF字典里不存在,那么会采用IDF字典的中位数作为默认IDF,所谓中庸之道。

所以呢,我建议用结巴分词做一个分词服务,产生文章的(分词,权重),作为simhash计算的输入。

TOP N词组参与计算

文章分词产生的词组太多,一般我们取TF/IDF最大的N个,这个N大家看心情定。

对于每个词组,套用一个哈希算法(比如times33,murmurhash…)把词组转换成一个64位的整形,对应的二进制就是01010101000…这样的。

接下来,遍历词组哈希值的64比特,若对应位置是0则记为-权重,是1就是+权重,可以得到一个宽度64的向量:[-权重,+权重,-权重,+权重…]。

然后将TOP N词组的向量做加法,得到一个最终的宽64的向量。

生成simhash

接下来,遍历这个宽度64的向量,若对应位置<0则记录为0,>0则记录为1,从而又变成了一个64比特的整形,这个整形就是文章的simhash。

海量simhash查询

抽屉原理

之前说过,判定2篇文章相似的规则,就是2个simhash的汉明距离<=3。

查询的复杂性在于:已有100亿个文章的simhash,给定一个新的simhash,希望判断是否与已有的simhash相似。

我们只能遍历100亿个simhash,分别做异或运算,看看汉明距离是否<=3,这个性能是没法接受的。

优化的方法就是”抽屉原理”,因为2个simhash相似的标准是<=3比特的差异,所以如果我们把64比特的simhash切成4段,每一段16比特,那么不同的3比特最多散落在3段中,至少有1段是完全相同的。

同理,如果我们把simhash切成5段,分别长度 13bit、13bit、13bit、13bit、12bit,因为2个simhash最多有3比特的差异,那么2个simhash至少有2段是完全相同的。

建立索引

对于一个simhash,我们暂时决定将其切成4段,称为a.b.c.d,每一段16比特,分别是:a=0000000000000000,b=0000000011111111,c=1111111100000000,d=111111111111111。

因为抽屉原理的存在,所以我们可以将simhash的每一段作为key,将simhash自身作为value追加索引到key下。

假设用redis做为存储,那么上述simhash在redis里会存成这样:

key:a=0000000000000000 value(set结构):{000000000000000000000000111111111111111100000000111111111111111}

key:b=0000000011111111 value(set结构):

{000000000000000000000000111111111111111100000000111111111111111}

key:c=1111111100000000 value(set结构):

{000000000000000000000000111111111111111100000000111111111111111}

key:d=111111111111111 value(set结构):

{000000000000000000000000111111111111111100000000111111111111111}

也就是一个simhash会按不同的段分别索引4次。

判重

假设有一个新的simhash希望判重,它的simhash值是:

a=0000000000000000,b=000000001111110,c=1111111100000001,d=111111111111110

它和此前索引的simhash在3段中一共有3比特的差异,符合重复的条件。

那么在查询时,我们对上述simhash做4段切割,然后做先后4次查询:

用a=0000000000000000 找到了set集合,遍历集合里的每个simhash做异或运算,发现了汉明距离<=3的重复simhash。

用b=000000001111110 没找到set集合。

用c=1111111100000001 没找到set集合。

用d=d=111111111111110 没找到set集合。

优化效果

经过上述索引与查询方式,其实可以估算出优化后的查询计算量。

假设索引库中有100亿个simhash(也就是2^34个simhash),并且simhash本身是均匀离散的。

一次判重需要遍历4个redis集合,每个集合大概有 2^32 / 2^16个元素,也就是26万个simhash,比遍历100亿次要高效多了。

图片左侧表示了一个simhash索引了4份,右侧表示查询时的分段4次查找。

权衡时间与空间

假设分成5段索引,分别命名为:a.b.c.d.e。

根据抽屉原理,至多3比特的差异会导致至少有2段是相同的,所以一共有这些组合需要索引:

  • a,b
  • a,c
  • a,d
  • a,e
  • b,c
  • b,d
  • b,e
  • c,d
  • c,e
  • d,e

一个simhash需要索引10份,一个集合的大小是2^34 / 2^(26)=256个。

一次查询需要访问10次集合,每个集合256个元素,一共只需要异或计算2560次,基本上查询性能已不再是瓶颈。

但是也可以知道,因为冗余的索引份数从4份变成了10份,所以其实是在牺牲空间换取时间。

对应的,这么大量的存储空间,再继续使用redis也是不可能的事情,需要换一个依靠廉价磁盘的分布式存储。

存储选型

毫无疑问选择hbase,特别适合SCAN遍历集合。

rowkey设计:4字节的segment+1字节的段标识flag+8字节的simhash。

切4段,索引一段需要16比特;切5段,索引2段需要13+13比特;所以用4字节的segments来存段落。

1字节的抽屉标识,比如是切4段则标识是1,2,3,4;切5段则可以是1,2,3,4,5,6,7,8,9,10,分别代表(a,b),(a,c),(a,d),(a,e),(b,c) …

然后最后追加上simhash自身作为区分值,这样在查询时只需要指定segment+flag做4/10次SCAN操作,进行异或运算即可。


http://chatgpt.dhexx.cn/article/6auk1FhA.shtml

相关文章

自然语言处理学习笔记5:去重处理之使用SimHash进行海量文本去重

摘要: 传统的Hash算法只负责将原始内容尽量均匀随机地映射为一个签名值&#xff0c;原理上仅相当于伪随机数产生算法。传统的hash算法产生的两个签名&#xff0c;如果原始内容在一定概率下是相等的&#xff1b;如果不相等&#xff0c;除了说明原始内容不相等外&#xff0c;不再…

python编写url文本去重和url探测存活一体化工具

因为项目需要&#xff0c;长时间使用360的quake和奇安信的hunter进行资产收集。但是收集到的资产很多无法访问&#xff0c;hunter的都是200。所以写了一个简单的脚本&#xff0c;让quake和hunter进行对比&#xff0c;去掉重复部分&#xff0c;然后再探测存活&#xff0c;存活ur…

使用NotePad++快速实现字符串统计/抽取,以及使用Notepad进行文本去重

软件测试技术交流群 : 1、QQ交流群&#xff1a;群号 429183023 2、添加JeongJinWin&#xff0c;或者扫描头像二维码 背景&#xff1a;日常工作中&#xff0c;可能在Windows下需要对一些文本进行解析&#xff0c;抽取出某种类型的字段、或者特定字符串&#xff0c;在Linux下可…

在线文本去重统计工具

在线文本去重统计工具 在线文本去重统计工具 本工具可以统计文本列表的重复项以及统计每个重复项出现的次数。 本工具可以统计文本列表的重复项以及统计每个重复项出现的次数。 本工具可以统计文本列表的重复项以及统计每个重复项出现的次数。 https://tooltt.com/unique/

论__大量文本内容去重的方式

论__大量文本内容去重的方式 本文由 Luzhuo 编写,请尊重个人劳动成果,转发请保留该信息. 原文: http://blog.csdn.net/Rozol/article/details/50640179 微博: http://weibo.com/u/2524456400 最近拿到大量的文本文件,文件的大小少个几十M,多则几十G,这么多且大的文本想必有很…

[039]文本去重、过滤——文本指纹

1. 文本指纹介绍 互联网网页存在大量的重复内容网页&#xff0c;无论对于搜索引擎的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪、还是社交媒体等文本去重和聚类&#xff0c;都需要对网页或者文本进行去重和过滤。 最简单的文本相似性计算方法可以利用空间向量模型&…

TXT文本去重 TXT去重 TXT文本合并去重工具 —— 20亿行130GB的数据只需60分钟

例如&#xff1a;多个TXT大数据文本文件合并以及文本行去重 130GB20亿行数据60分钟即可完成去重操作 测试数据大小&#xff1a;20亿行130GB的数据只需60分钟 平均去重速度&#xff1a;2000000000(行) 3600(秒) ‬ 555555(行/秒)≈55万行/秒 作者QQ&#xff1a;24759362 以…

文本去重:sim哈希算法

站在巨人_啊哈、zstu_翊、lengye7、黑夜路人的肩膀上~ 分析数据前&#xff0c;我们需要对数据去重&#xff0c;如何选择和设计文本的去重算法&#xff1f; 常见的去重算法有&#xff1a;余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法是先将两篇文…

文本去重的技术方案讨论(一)

转发请注明出处&#xff1a;https://blog.csdn.net/HHTNAN 对于文本去重来说&#xff0c;我个人处理上会从数据量、文本特征、文本长度&#xff08;短文本、长文本&#xff09;几个方向考虑。 常见的去重任务&#xff0c;如网页去重&#xff0c;帖子去重&#xff0c;评论去重等…

git 生成公钥 及使用笔记

1.输入 ssh-keygen -t rsa -C 2101419675qq.com 2.一路回车&#xff0c; 提示输入文件名和密码都直接回车 3.公钥就生成了&#xff0c;路径为 4.在GitHub或gittree中直接将id_rsa.pub中的内的内容加在sskey中就行 下面是gittree 5.其它 mkdir test cd test git init touch …

git生成公钥私钥(windows)

配置用户名和邮箱 git config --global user.name "v_sunhaojie" $ git config --global user.email "v_sunhaojiebaidu.com" 会在当前用户的目录下(C:\Users\v_sunhaojie)生成 .gitconfig文件 [user] name v_sunhaojie email v_sunhaoji…

git生成公钥的步骤

git生成公钥的步骤 1. 设置Git账户2.生成命令 1. 设置Git账户 命令如下 git config user.name &#xff08;查看git账户&#xff09; git config user.email &#xff08;查看git邮箱&#xff09; git config --global user.name “账户名” &#xff08;设置全局账户名和邮箱…

【Git】ssh公钥如何生成

1. 在C盘用户目录文件下找到.ssh文件&#xff08;若之前未生成.ssh则进行第2步&#xff09; 里面保存的是之前生成的文件&#xff0c;将.ssh文件夹删除。 2. 右键&#xff0c;点击git bash here&#xff0c;进入git界面 3. 输入ssh-keygen -t rsa -C *.com &#xff0c;连点三…

git配置公钥

一、 生成.ssh文件 在桌面打开Git Bash&#xff0c;输入以下命令&#xff1a; ssh-keygen -t rsa -C "你的邮箱xxx.com"一直按回车&#xff0c;出现以下界面表示生成ssh文件成功 二、 找到id_rsa.pub文件 到C盘下找到.ssh文件夹&#xff1a;C:\Users\86187.ssh&am…

使用Git工具生成公钥与私钥

生成密钥对 keytool -genkeypair -alias shopping -keyalg RSA -keypass shopping -keystore shopping.jks -validity 365 -storepass shopping 解析私钥 keytool -list -rfc --keystore shopping.jks | openssl x509 -inform pem -pubkey 输入口令即可

超简单git生成ssh公钥(ssh-keygen)

首先在桌面右键&#xff0c;点击Git bash Here 在命令窗口输入 ssh-keygen -t rsa -C "你的邮箱地址" 回车 这时让你输入密码&#xff0c;这个密码会在你提交项目时使用 然后直接三个回车 到达最后 你会发现桌面上会有一个.pub的文件&#xff0c;右键用记事本打开…

【技术分享】Mac环境下git生成SSH公钥

文章目录 1.查看本机的ssh公钥2.生成ssh公钥 1.查看本机的ssh公钥 ①终端进入~/.ssh目录 cd ~/.ssh②使用ls命令查看&#xff0c;如果有id_rsa.pub文件说明已经生成了公钥。 ls③使用cat命令查看公钥具体内容&#xff0c;如下图所示 cat id_rsa.pub2.生成ssh公钥 注意XXXX…

git ssh key的配置,git生成ssh公钥

git clone支持https和git&#xff08;即ssh&#xff09;两种方式下载源码。 使用git方式下载时&#xff0c;如果没有配置过ssh key&#xff0c;则会有如下错误提示&#xff1a; 1.首先配置用户名&#xff0c;邮箱。 git config --global user.name "这里换上你的用户名…

【Git】Gitee生成/添加SSH公钥

Gitee 提供了基于SSH协议的Git服务&#xff0c;在使用SSH协议访问仓库之前&#xff0c;需要先配置好账户/仓库的SSH公钥。 按如下命令来生成 sshkey: ssh-keygen -t ed25519 -C "xxxxxxxxxx.com" 注意&#xff1a;这里的 xxxxxxxxxx.com 只是生成的 sshkey 的名称…

git生成ssh公钥

学习一下&#xff0c;感谢&#xff01; gitee 步骤&#xff1a; 1.打开终端&#xff08;git&#xff09;进入.ssh目录 cd ~/.ssh 如果.ssh文件夹不存在&#xff0c;执行指令自动创建 mkdir ~/.ssh 2.生成RSA密钥对并进行命名 ssh-keygen -t rsa -C "你的邮箱xxx…