超经典，网页判重核心技术！（第25讲）

《架构师之路：架构设计中的100个知识点》 25.网页判重核心技术，LSH，minhash，分句

如何快速判断，1个网页是否属于1亿个网页中的重复网页？

答：预处理，每个网页用一个hash签名代替。问题就转化为，判断1个hash签名是否属于某个hash签名集合，复杂度就大大降低了。

有些网页，99%的内容一样，1%的内容不同（例如html标签），业务上也必须判断为相同的网页，此时要怎么办？

hash的原则是，两个网页哪怕只有1bit的差异，其hash值差别也非常大，它只适合用作完整性检查。

网页只有少量不同，也必须判断为相同的网页，本质上是相似性判断，如此一来，hash签名方案就行不通了。

有没有一种hash，内容越相似，hash值也越相似呢？

有。局部敏感哈希（Locality Sensitive Hash）LSH，就是这样一种hash。

局部敏感哈希，能不能举个例子？

minhash就是一种局部敏感哈希，它经常用来判断集合的相似性，它的思路为：使用相同的规则抽取集合中的少量元素，代表整个集合。

例如：可以用10个元素，代表一个10万个元素的集合，这里的本质就是一个hash。如果两个hash后的小集合重合度很高，我们也认为大集合的相似性很高。

举个例子：

待判定的网页为：

A={1, 7, 5, 9, 3, 11, 15, 13}

已有的网页库为：

B={10, 8, 2, 4, 6, 0, 1, 16}

C={100, 700, 500, 900, 300, 1100, 1500,1300}

D={1, 3, 10, 11, 12, 5, 8, 7}

假设集合的hash规则为：将集合内元素进行排序，取值最小的4个作为hash值。

画外音：这个过程有信息损失，是一个hash过程。

处理结果为：

hash(A)={1, 3, 5, 7}

hash(B)={0, 1, 2, 4}

hash(C)={100, 300, 500, 700}

hash(D)={1, 3, 5, 7}

判断结论：我们认为网页A与网页D哈希结果相同，可以认为原网页也相同，或者说最相似。

怎么把网页转化为集合？

分词，分词可以将网页转化为集合。

分词确实可以将网页转化为集合，但这样的集合可以用于网页去重吗？

分词不适合网页去重，网页分完词都是{你,我,他,的,地,得}，不具备区分性。

那要如何优化？

分句，标点符号会将网页分成很多句子，可以取最长的N个句子集合代表网页，作为网页的hash签名。

用这种hash方法来判断网页的重合度与相似度，不但速度快准确性高，还能大大降低工程的复杂度。

总结：

1. 普通hash，适用于完整性判断，不适合相似性判断；

2. 局部敏感哈希LSH，内容越相近，hash值也越相近；

3. minhash是一种LSH，常用来判断集合的相似性，其思路为：使用相同的规则抽取集合中的少量元素，作为集合的hash值。原集合约相近，hash值子集合也越相近；

4. 网页相似度判断，经常使用“分句”代替“分词”，来对网页进行哈希；

知其然，知其所以然。

思路比结论更重要。

补充阅读材料：

《LSH综述》

https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide

LSH入门介绍，5分钟搞定。