搜索基础算法重大突破：20行代码解决20年瓶颈问题

正文

请到「今天看啥」查看全文

（https://en.wikipedia.org/wiki/MinHash）

也就是人们所熟知的 minhash，是第一个被应用在 Web 领域的去重算法。也正是在这一时期，像 Google 这样的搜索公司出现了。该算法将给定的页面作为输入，并生成一系列随机数字，如果两个页面很相似，那么它们的 minwise 哈希值就很有可能是一样的。于是这些数字就成为页面的指纹（fingerprint），而指纹匹配可以作为相似度的判定依据。

计算指纹可以让搜索变得更简单。我们为页面指纹建立索引，在内存里保存页面的引用，也就是页面的 minwise 哈希值或指纹。如果两个页面很相似，那它们的 minwise 哈希值很可能是一样的，这样就可以将两个页面的引用指向同一个页面位置（如下图所示），不需要进行两两比对。

基于指纹进行索引的方法后来被归纳为著名的局部敏感哈希（locality sensitive hashing，LSH）理论。

（https://en.wikipedia.org/wiki/Locality-sensitive_hashing）

该理论在近似搜索问题上扮演了重要角色。后来，计算指纹的方式直接被用在数据挖掘和机器学习中，用于缓解计算瓶颈。minwise 哈希因此成为无可争议的随机算法。

请到「今天看啥」查看全文