大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
对于web网页去重的应用，如抄袭、镜像等，通过将网页表示为字符k-grams（或者k-shingles）的集合，把网页去重的问题转化为找到这些集合的交集。使用传统的方法存储这些巨大的集合以及计算它们之间的相似性显然是不够的，为此，对集合按某种方式进行压缩，利用压缩后的集合推断原来集合的相似性。
Jaccard相似性：只关注集合之间的交集大小。
集合S和T的Jaccard相似性定义如下：
比如S = { a, b, c, d } and T = { c, d, e, f } , 那么SIM(S, T )= 2/6。
k-Shingles
一篇文档可以看成是一个字符串，文档的k-shingle为在该文档中长度为k的所有子串。任意一篇文档都可以表示为k-shingles的集合，比如“A document is a string of characters”这句话的所有3-shingles为{ ”A d”, ”do”, ”doc”, ”ocu”, ”cum”, ”ume”, ”men”, ”ent”, . . . , ”ers” }。如果k非常小，那么k个字符的序列会出现在大多数的文档中，如k=1，许多文档都有相同的字符，几乎所有的文档都有很高的相似性。如果k应该足够大，那么对于给定的shingle出现在不同的文档中的概率是非常低的。比如这两个单词“ document”和“monument”：
SIM( { d, o, c, u, m, e, n, t } , { m, o,n, u, m, e, n, t } ) = 6/8
SIM( { doc, ocu, cum, ume, men, ent } ,{mon, onu, num, ume, men, ent } ) = 3/9
对于电子邮件的语料库，k=5就足够了，因为在电子邮件中出现的英文字母和空白字符有27个，那么就会有275 = 14 348 907 shingles，一般电子邮件的长度不会超过14 million个字符，所以k=5是一个合理的值。
Hashing Shingles
不使用子串直接作为shingles，而是使用hash函数将长度为k的字符串映射到哈希桶中，哈希桶的编号作为shingle，则表示文档的集合转化为含有哈希桶编号的集合。一篇文档的9-shingle可以映射到[0,232 – 1]。如果使用4-shingles，许多4字节的序列在一般的文档中是找不到的，不同的shingles数量大约有204=160 000，远小于232。
Minhash技术
由于shingles的集合非常大，即使把它们映射hash成4字节，所需要的空间仍然是一篇文档所占空间的4倍。对于million级别的文档，就不能将所有shingle集合加载到内存。对于占用空间大集合，我们将其替换为占用空间较小的签名（signatures）表示，并且signatures在一定程度上保留集合的相似性信息。
集合的特征矩阵
矩阵的列对应集合，行对应从文档中（或者universal set）获取到的元素，如果r行是c列的集合元素，就将矩阵的r行c列设置为1，否则为0。例如，universal set ：{ a, b, c, d, e }，S1 = { a, d } , S2 = { c } , S3 = {b, d, e } , S4 = { a, c, d } ，特征矩阵如下：
我们想要的signatures是通过对特征矩阵的一系列minhash计算所得到的，任何一列的minhash值为经过置换后第一个为1的元素对应行号（行号从0开始）。有点拗口，我们对上面的特征矩阵变换顺序（ beadc ），得到新的特征矩阵：
上图中特征矩阵的minhash值：h(S1) = 2 (a)， h(S2) =4 (c)， h(S3) = 0 (b) 和h(S4) = 2(a)。
Minhash和Jaccard相似性有重要的联系：如果两个集合S1和S2的Jaccard相似性是一样的，那么以很高的概率保证它们的minhash值也是相等的。
计算signatures的步骤：
1> 对特征矩阵M做n次随机置换；
2> 根据这些置换确定minhash函数h1，h2，… ,hn；
3> 用列表示集合S，构建S的minhash的signature，(h1(S), h2 (S), . . . , hn (S))；
4> 有上述步骤即可构建M的signature矩阵，即M的第i列被替换为第i列的minhash signature。
注意：signature矩阵和特征矩阵M有相同的列数，但是只有n行，要比M矩阵小的多。
显然对一个很大的特征矩阵做置换是不可行的，但是可以通过随机hash函数模拟随机置换效果，将行号映射到桶的编号。具体方案为：随机选择n个hash函数h1,h2,…,hn，SIG(i,c)为signature矩阵的元素，是由第i个hash函数和M的第c列确定：
SIG(i, c) = min { hi(r) : forsuch r that c has 1 in row r }
举例说明：
计算hash值（置换顺序）：
根据公式SIG(i, c) = min { hi(r) : forsuch r that c has 1 in row r }，计算signature：
通过signature矩阵估计Jaccard相似性：
SIM(S1, S2) = 0 SIM(S1, S3) = 1/2 SIM(S1, S4) = 1
而实际的相似性为：
SIM(S1, S2) = 0 SIM(S1, S3) = 1/4 SIM(S1, S4) = 2/3
参考资料
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/226853.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...