精易论坛
标题: 【文章查重】改自谷歌海量Simhash文本去重 [打印本页]
作者: 明天自然醒 时间: 2023-3-16 18:24
标题: 【文章查重】改自谷歌海量Simhash文本去重
本帖最后由 明天自然醒 于 2023-3-18 22:29 编辑
1. SimHash与传统hash函数的区别 传统的Hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上仅相当于伪随机数产生算法。传统的hash算法产生的两个签名，如果原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别很大。所以传统的Hash是无法在签名的维度上来衡量原内容的相似度，而SimHash本身属于一种局部敏感哈希算法，它产生的hash签名在一定程度上可以表征原内容的相似度。
我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hash签名也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hash却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。
通过simhash计算结果为：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过传统hash计算为：
0001000001100110100111011011110
1010010001111111110010110011101
大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hash却不能做到，这个就是局部敏感哈希的魅力。
2. SimHash算法思想 假设我们有海量的文本数据，我们需要根据文本内容将它们进行去重。对于文本去重而言，目前有很多NLP相关的算法可以在很高精度上来解决，但是我们现在处理的是大数据维度上的文本去重，这就对算法的效率有着很高的要求。而局部敏感hash算法可以将原始的文本内容映射为数字（hash签名），而且较为相近的文本内容对应的hash签名也比较相近。SimHash算法是Google公司进行海量网页去重的高效算法，它通过将原始的文本映射为64位的二进制数字串，然后通过比较二进制数字串的差异进而来表示原始文本内容的差异。
3. SimHash流程实现 simhash是由 Charikar 在2002年提出来的，本文为了便于理解尽量不使用数学公式，分为这几步：
（注：具体的事例摘自Lanceyan的博客《海量数据相似度计算之simhash和海明距离》） 1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。
整个过程的流程图为：
4. SimHash签名距离计算 我们把库里的文本都转换为simhash签名，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两个simhash的01有多少个不同吗？对的，其实也就是这样，我们通过海明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。
5. SimHash存储和索引 经过simhash映射以后，我们得到了每个文本内容对应的simhash签名，而且也确定了利用汉明距离来进行相似度的衡量。那剩下的工作就是两两计算我们得到的simhash签名的汉明距离了，这在理论上是完全没问题的，但是考虑到我们的数据是海量的这一特点，我们是否应该考虑使用一些更具效率的存储呢？其实SimHash算法输出的simhash签名可以为我们很好建立索引，从而大大减少索引的时间，那到底怎么实现呢？
这时候大家有没有想到hashmap呢，一种理论上具有O(1)复杂度的查找数据结构。我们要查找一个key值时，通过传入一个key就可以很快的返回一个value，这个号称查找速度最快的数据结构是如何实现的呢？看下hashmap的内部结构：
如果我们需要得到key对应的value，需要经过这些计算，传入key，计算key的hashcode，得到7的位置；发现7位置对应的value还有好几个，就通过链表查找，直到找到v72。其实通过这么分析，如果我们的hashcode设置的不够好，hashmap的效率也不见得高。借鉴这个算法，来设计我们的simhash查找。通过顺序查找肯定是不行的，能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图：
存储：
1、将一个64位的simhash签名拆分成4个16位的二进制码。（图上红色的16位）
2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。（放大后的16位）
3、对应位置没有元素，直接追加到链表上；对应位置有则直接追加到链表尾端。（图上的 S1 — SN）
查找：
1、将需要比较的simhash签名拆分成4个16位的二进制码。
2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
3、如果有元素，则把链表拿出来顺序查找比较，直到simhash小于一定大小的值，整个过程完成。
原理：
借鉴hashmap算法找出可以hash的key值，因为我们使用的simhash是局部敏感哈希，这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本，至少有16位的simhash是一样的。具体选择16位、8位、4位，大家根据自己的数据测试选择，虽然比较的位数越小越精准，但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb，扩大4倍1.5G左右，还可以接受
6. SimHash存储和索引 1. 当文本内容较长时，使用SimHash准确率很高，SimHash处理短文本内容准确率往往不能得到保证；
2. 文本内容中每个term对应的权重如何确定要根据实际的项目需求，一般是可以使用IDF权重来进行计算。
7. 参考内容8. 实现（附带2015年新闻语料库）
1.查重设置
你可以设置文章切分成一句一句话，也可以大概每30字符切分一次，（论文一般取13个字）
最大汉明距离取3，为大数据实验结果值。
性能选择：高效模式，只要判断重复即可返回。精准模式，检索所有重复结果，并取最大相似度的那一分段。
2.使用效果。黄色为中等相似度，红色为高相似度。下图为每30字符对比结果。数据库已加载1万新闻语料库。上图右侧是每一句话的重复出处，因为要展示效果，所以复制了这个文章，并修改了一下。
3.生成分析。暂未实现完。下次更新附上生成论文查重详细报表。应该是用内存画板画出来。
下图展示了句子相似度分布图。采用内存画板实现。但是可能和分词模块冲突了，所以我用另外一个程序写出来了，然后特别粗糙的调用的，但效果丝毫不影响。
4.源码
码字不易，来点好评回血，支持作者继续更新
回复可见
补充内容 (2023-12-31 14:28):
最新帖：1.04
https://125.confly.eu.org/thread-14807724-1-1.html
作者: quary 时间: 2023-3-16 19:21
谢谢楼主分享！！！
好人一生平安！！！
作者: linchen888 时间: 2023-3-16 19:24
\
支持开源~！感谢分享
作者: 书染 时间: 2023-3-16 19:31
RE: 【文章查重】改自谷歌海量Simhash文本去重 [修改]
作者: 59hdvj 时间: 2023-3-16 19:36
谢谢分享
作者: 曦月 时间: 2023-3-16 19:40
论坛有你更精彩
作者: zifeiyu 时间: 2023-3-16 19:48
6666666666666666
作者: 深圳梦 时间: 2023-3-16 19:53
支持开源~！感谢分享
作者: 安哥 时间: 2023-3-16 20:03
看看速度咋样
作者: 点点丶滴滴 时间: 2023-3-16 20:05
作者: qgchqgch89 时间: 2023-3-16 20:25
看看高科技啦
作者: 学习122 时间: 2023-3-16 20:35
支持开源~！感谢分享
作者: 君九 时间: 2023-3-16 21:13
文章查重
作者: 咚咚鼠 时间: 2023-3-16 21:24
感谢分享！
作者: renjianhong48we 时间: 2023-3-16 21:28
感谢分享
作者: chinapk 时间: 2023-3-16 21:47
不易，来点好评回血，支持作
作者: 光影魔术 时间: 2023-3-16 21:58
感谢楼主的干货知识，学习了，收藏夹+1
作者: zg2600 时间: 2023-3-16 21:59
写论文的用一下
作者: fooker 时间: 2023-3-16 22:01
感谢分享
作者: shituo 时间: 2023-3-16 22:08
点好评回血，支持作者继续更新
作者: 小小小Baby 时间: 2023-3-16 22:16
感谢开源，下载来看看查重结果怎么样
作者: 515889127 时间: 2023-3-16 22:36
感谢分享。。。
作者: 以后的我以后 时间: 2023-3-16 22:47
以后的我以后，如果您要查看本帖隐藏内容请回复
作者: hxq7311 时间: 2023-3-16 23:10
干货满满。感谢分享
作者: 794229345 时间: 2023-3-16 23:41
楼主辛苦了，谢谢楼主，感谢楼主分享，楼主好人一生平安！！！
作者: 明天自然醒 时间: 2023-3-16 23:51
本帖最后由 明天自然醒 于 2023-3-19 22:25 编辑
更新1.02：添加多线程，改用zysql3.35模块，多线程并发cha询，提速至少10倍。
更新1.03：修正偏移相似度，并合并连续分段的相似结果，取极大值。
全新版下载：
https://share.weiyun.com/l8hWoL2p
作者: menghan 时间: 2023-3-17 01:20
感谢楼主分享，支持一下~~
作者: 285275928 时间: 2023-3-17 02:34
码字不易，来点好评回血，支持作者继续更新
作者: 凉城o 时间: 2023-3-17 05:36
来看看 
作者: 一指温柔 时间: 2023-3-17 08:35
开源精神必须支持~
作者: 痞子刘哥 时间: 2023-3-17 09:53
码字不易，来点好评回血，支持作者继续更新
作者: 网络注册网员 时间: 2023-3-17 10:43
学习一下
作者: wjswzj0 时间: 2023-3-17 11:06
支持开源~！感谢分享
作者: myl1712 时间: 2023-3-17 11:15
哈哈哈哈哈哈哈哈哈或
作者: feng5555 时间: 2023-3-17 11:19
#在这里快速回复#支持开源~！感谢分享
作者: Medicalcrazy 时间: 2023-3-17 12:48
收藏了，慢慢研究
作者: xtavoxing 时间: 2023-3-17 13:57
大神就是大神,弄 的那么详细. 真厉害.
作者: 鱼雨遇玉羽 时间: 2023-3-17 14:02
辛苦了谢谢分享
作者: AFK 时间: 2023-3-17 14:25
支持开源~！感谢分享
作者: 完玩 时间: 2023-3-17 16:33
这才是大佬嘛
作者: wxb130260 时间: 2023-3-17 18:05
谢谢LZ分享
作者: airaz 时间: 2023-3-17 19:22
优秀 感谢开源
作者: shentong 时间: 2023-3-17 19:43
kkkkkkkkkkkkkkk
作者: Solo98k 时间: 2023-3-17 22:19
感谢分享！！
作者: 亿万 时间: 2023-3-17 22:20
支持开源~！感谢分享
作者: fyh505099 时间: 2023-3-17 22:22
学习学习 感谢分享
作者: 4858p 时间: 2023-3-17 22:34
大佬多谢指教
作者: hzhzpp1209 时间: 2023-3-17 22:40
6666666666666
作者: 风中冰雨 时间: 2023-3-17 22:52
看看........
作者: Yy闲人 时间: 2023-3-18 02:23
支持开源~！感谢分享
作者: hqz9494 时间: 2023-3-18 03:37
支持开源~！感谢分享
作者: weihua2018 时间: 2023-3-18 04:08
可以取出重复的不
作者: zzzyf 时间: 2023-3-18 08:28
#在这里快速回复#厉害！
作者: 回不到的过去 时间: 2023-3-18 08:45
支持开源~！感谢分享
作者: 凌哥 时间: 2023-3-18 09:24
主要的算法是分词分句
作者: 达人秀110 时间: 2023-3-18 09:59
文章查重】改自谷歌海量Simhash文本去重
作者: fengyishen 时间: 2023-3-18 11:15
有点意思，下载学习
作者: 396384183 时间: 2023-3-18 14:15
开源精神必须支持~
作者: 〞剑舞长空 时间: 2023-3-18 16:00
支持开源~！感谢分享
作者: 执骨哟 时间: 2023-3-18 16:06
主要的算法是分词分句，感谢大佬
作者: pyms 时间: 2023-3-18 16:17
感谢发布原创作品，精易因你更精彩！
作者: wuqingg 时间: 2023-3-18 16:19
感谢发布原创作品，精易因你更精彩！
作者: 梦想ol 时间: 2023-3-18 16:35
支持开源~！感谢分享
作者: a521qaz 时间: 2023-3-18 17:36
瑰石拓 的原在
作者: 华庭大哥 时间: 2023-3-18 19:15
感谢发布原创作品，精易因你更精彩！
作者: 寻找星空 时间: 2023-3-18 19:17
看看
作者: cymx735243556 时间: 2023-3-18 19:21
谢谢楼主分享
作者: Delude 时间: 2023-3-18 19:58
谢谢楼主分享
作者: 落雪无尘 时间: 2023-3-18 20:45
支持一下啊
作者: 三克油 时间: 2023-3-18 21:38
支持开源~！感谢分享
作者: zhifu3158 时间: 2023-3-18 23:26
码字不易，支持作者继续更新
作者: 滴滴滴滴滴 时间: 2023-3-18 23:52
作者: kangzunjun 时间: 2023-3-19 00:57
11111111111111111111
作者: 陽陽陽 时间: 2023-3-19 02:05
D I F F还没搞明白的我
作者: sskxin 时间: 2023-3-19 03:22
66666666666666666666666666666666
作者: alanwoo 时间: 2023-3-19 08:34
支持作者继续更新
作者: Singmy 时间: 2023-3-19 09:09
支持开源~！感谢分享
作者: Singmy 时间: 2023-3-19 09:10
感谢分享，很给力！~
作者: a521qaz 时间: 2023-3-19 09:21
gfhfghfgh5464564564
作者: 冷眸藐视 时间: 2023-3-19 09:56
如果您要查看本帖隐藏内容请
作者: dljy 时间: 2023-3-19 10:15
感谢分享，很给力！~
作者: 沈远 时间: 2023-3-19 10:20
学习学习学习学习
作者: 玩味流星 时间: 2023-3-19 10:56
感谢分享，很给力！~
作者: 1623863129 时间: 2023-3-19 11:08
给分段1-4加索引速度会快点，但是会加大内存，想降低内存可以不存储句子内容，只存储句子序号
作者: q954987161 时间: 2023-3-19 13:45
牛逼牛逼，支持一波
作者: 蜗牛人生 时间: 2023-3-19 16:08
看看猛不猛
作者: 五杀 时间: 2023-3-19 16:50
6666666666666
作者: leiwawa001 时间: 2023-3-19 16:50
谢谢分享。
作者: 偶尔有点帅 时间: 2023-3-19 17:09
看着很厉害啊
作者: xmeimei 时间: 2023-3-19 19:37
我要精币
作者: 分享者 时间: 2023-3-19 19:45
多谢楼主分享。
作者: ppppzj 时间: 2023-3-19 19:45
感谢楼主的分享
作者: 萧敬腾 时间: 2023-3-19 19:54
谢谢分享````
作者: by626 时间: 2023-3-19 22:20
nb和国内收费的有什么区别
作者: by626 时间: 2023-3-19 22:35
缺文件运行不了。ExuiKrnln.dll
作者: 绝不放弃 时间: 2023-3-20 00:46
感谢
作者: 18072699966 时间: 2023-3-20 04:11
支持开源~！感谢分享
作者: yechunlin 时间: 2023-3-20 07:52
谢谢分享
作者: lzx964753100 时间: 2023-3-20 08:16
真是个人才
作者: guoge110 时间: 2023-3-20 09:22
点好评回血，支持作者继续更新
| 欢迎光临 精易论坛 (https://125.confly.eu.org/) |
Powered by Discuz! X3.4 |