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

你现在看到的是我的技术笔记系列文章，已发表的文章如下，回复数字可查看：

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

即使采取Hash的方式，一份文档所有的Hash数据量也大于文档的量。根据前一节所述，如果生成4字节的Hash，存储也要扩大4倍。于是引入了签名，引入签名的代价是丢失一部分精准性，但是可以极大地减少存储。

1.集合的矩阵表达方式

采用矩阵来表达元素的个数。在矩阵中，行为每一个元素，列为每一个集合。矩阵中元素为1的代表该列的集合包括该行的元素。0代表不包括。形成如下的矩阵：

2.Minhash

一个Minhash函数h其实就是对矩阵的行进行置换操作（permutation），置换完了后，对每一列从上往下数，第1个非零的值对应的行，即该列集合生成的Minhash值。本图中，h(S_1)=a,h(S_2)=c……以此类推。

3.Minhash与Jaccard相似性

如果一个Hash函数对于两个不同的集合，生成了相同的结果，这个概率与两个集合的Jaccard相似性的值相等。

Jaccard相似性的计算公式就是两个集合交集的势除以两个集合并集的势。

一个概率的结果与一个相似性的结果相等，这二者有什么关系呢？

我的理解在于Hash函数的置换随机性的定义。即对矩阵的行的置换是随机的，所以旦凡存在Hash相等的情况，其概率就已经与Jaccard相似性算出的值相等了。

把随机性引入就会有一些很有意思的事情，这个思想在密码学里也比较普遍，比如素性检测，比如零知识证明。

4.Minhash的签名与计算

对于一个集合S，如果存在n个不同的Hash函数，可以构成一个向量[h(S_1),h(S_2),…,h(S_n)]，这个定义成该集合的Minhash签名。那如果有多个集合，就可以构成签名矩阵。

在实际计算时做了一次转换，不直接对行做N次置换，而是直接选取N个Hash函数对所有行处理。将每一个Hash函数作用在集合的每一个元素上，选取最小的值，作为该Hash函数在该元素上的输出值。

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

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

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

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

scalerstalk [at] gmail [dot] com

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