欢迎关注ScalersTalk。IT人，搞技术，聊英语，玩口译，话学术，谈生活。学习成长，笔耕不辍。回复m查看文章列表，或者访问S君小站ScalersTalk.com

你现在看到的是技术系列文章，目前已经发表的文章如下，回复括号数字可阅读。

海量数据处理系列的前两篇：

[213]签名：集合的归纳描述

[207]海量数据相似性检测：文档的抽块处理(Shingling)

其他系列：

[152]清高与小我：谈技术人员的优越感(4)

[150]清高与小我：谈技术人员的优越感(3)

[149]清高与小我：谈技术人员的优越感(2)

[148]清高与小我：谈技术人员的优越感(1)

[112]扯点密码学：可证明安全随笔

1.Minhash的LSH

即使是有Minhash签名，如果要对一个文档的所有签名两两进行比较，也会是很大量的计算。于是想到的一个思路就是对所有签名再进行一次Hash，这种Hash有这么一个特点，对于相似的对象可以得出相同的输出。相当于对所有输出进行桶排序，在一个桶中的结果是比较相似的，于是全局性的计算量，在Hash之后，只要比较桶中数量的Hash值即可。

这里由于引入了Hash，就会有一个问题：存在两种可能，一个是把本来不应该在一个桶里的放在一个桶里，另一个是把本来应该在一个桶里的放在了不同的桶里。前者叫假阳性false positive，后者叫假阴性false negative。

对于签名矩阵，将其行划分成不同的带(band)，划分成b个带，每个带有r行。对每一个带选取一个Hash，Hash的输入是带内的每一列。所以如果这个带中，存在相同的列，会得到相同的Hash值。可以给每个band选用相同的Hash函数，也可以选用不同的Hash函数。

通过分带的方式可以看到，如果两个文档各对应band的相同的数目越多，文档相似程度越高。

2.分带技术分析

对于一对band，其Jaccard相似性，与某一对应行的值相同的概率，均为s.

进而可以计算出对于b个带，每个带有r行的矩阵，至少有一对以上相同的概率为1-(1-s^r)^b。这个结论比较容易得出。

对于一个band里至少有一行不相同的概率为1-s^r

对于所有band里各行均不相同的概率为(1-s^r)^b

对于所有band至少有一个band相同的概率为1-(1-s^r)^b

这于是变成了一个函数，常量是b和r，变量是s。构成了S型曲线，如下图。有一个临界值，也就是曲线最陡的区间，取值大约在(1/b)^(1/r)

3.相似文档的综合检测方法

这里总结一下前面各个模块提到的技术点，拼起来形成一个综合的相似文档的检测方法：

1.选定k，并且构造每个文档的k-Shingles。可选项，将每个k-Shingleshash运算到桶中

2.对文档-块(document-shingle)对进行排序，shingle

3.选择Minhash签名的长度n，并计算每个文档的签名矩阵

4.选择门限t，确认相似的门限值。确定b和r，根据上一节，t约为(1/b)^(1/r)。如果为了避免假阴性错误，(1/b)^(1/r)比t小一些；如果要加快速度，避免假阳性，(1/b)^(1/r)选择大一些

5.构造签名对，参照本篇中1的方法

6.检查签名对，计算相似性是否大于门限t

7.本项可选，如果签名相似性足够，可以检查文档，看是否真正相似。

回复“100小时”查看口译100小时训练计划；回复“十万字”查看十万字视译计划。

S君的口译100小时、十万字视译训练交流QQ群，欢迎加入（群号为231441722）

S君个人微信号，ScalersTalker欢迎添加。

如果你觉得S君的文章对你有用，欢迎捐助打赏 。支付宝账号是

scalerstalk [at] gmail [dot] com

想看更多相关文章，关注 ScalersTalk 回复任意小于标题括号中的三位数字查看。或者去我的站点 ScalersTalk.com 查看历史文章。