局部敏感哈希介绍

传统的Hash当源数据有些许的变化的时候生成的哈希值差异也非常的大, 比如:

1
2
3
4
5
6
7
8
9
10
func main() {
s1 := []byte("你好世界")
s2 := []byte("你好,世界")
hash1 := md5.Sum(s1)
hash2 := md5.Sum(s2)
fmt.Println(hex.EncodeToString(hash1[:]))
fmt.Println(hex.EncodeToString(hash2[:]))
}

s1的哈希值是65396ee4aad0b4f17aacd1c6112ee364、s2的哈希值是27444ee2d245c3e8e11ed8b9b035c43b,源数据仅仅是一个逗号的区别,但是哈希值完全不一样。这是我们使用Hash的常见的场景,输出的哈希值经常被称为消息摘要(message digest)或摘要(digest)。

局部敏感哈希(Locality-sensitive hashing, 简称LSH)则不同, LSH则希望相似的源数据计算出来的哈希值越相近越好。
LSH经常用在判重、文章摘要、聚类、相似搜索、近邻查找等场景, 用来减少高维度的数据的维度,相近的数据放在同一个桶中。 比如大规模异常滥用检测:基于局部敏感哈希算法——来自Uber Engineering的实践

阅读全文

<转> 基数估计算法概览

转自淘宝张洋的基数估计算法概览
翻译自Damn Cool Algorithms: Cardinality Estimation.
在淘宝的应用考虑参考 基数估计算法在大数据场景下的应用.

假如你有一个巨大的含有重复数据项数据集,这个数据集过于庞大以至于无法全部放到内存中处理。现在你想知道这个数据集里有多少不同的元素,但是数据集没有排好序,而且对如此大的一个数据集进行排序和计数几乎是不可行的。你要如何估计数据集中有多少不同的数据项?很多应用场景都涉及这个问题,例如设计数据库的查询策略:一个良好的数据库查询策略不但和总的数据量有关,同时也依赖于数据中不同数据项的数量。

我建议在继续阅读本文前你可以稍微是思考一下这个问题,因为接下来我们要谈的算法相当有创意,而且实在是不怎么直观。

阅读全文