golang中的局部敏感哈希介绍

by · 2019年03月05日 · 1508 Words · ~4min reading time | Improve on

String similarity https://github.com/rfguri/bowsim

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

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 的实践

学术定义 Locality sensitive hashing 总是不那么容易让人理解，本文也不试图从学术的角度去介绍 LSH, 而是介绍一个特定的 LSH 算法：simhash。

通用的 LSH 会基于某个点与点之间的某种距离判定相似性，相近的点距离接近，也就是说，我们可以通过计算距离来比较对象的相似性。距离之间的测量可以分为两大类：

欧几里得距离 (Euclidean): 基于空间中的点计算距离
- 普通的欧几里得距离
- 曼哈顿距离 (Manhattan distance)
- 闵可夫斯基距离 (Minkowski Distance)
非欧几里得距离: 不是根据空间中的位置，而是根据点的属性计算距离
- 杰卡德距离 (Jaccard distance): 1 - 杰卡德相似系数
- 余弦距离 (Cosine distance)
- 编辑距离 (Edit distance)
- 汉明距离 (Hamming Distance)

当然还有一些距离的计算公式，比如切比雪夫距离 (Chebyshev Distance)、马氏距离 (Mahalanobis distance)、Pearson 距离等。
这些计算距离的方法会应用在不同的场景中，有时候也会使用不同的距离计算方法进行比较。

不同的 LSH 会使用不同距离计算方法：

HyperplaneLSH 使用余弦距离
Super-Bit Locality-Sensitive Hashing 使用汉明距离
Min Hash 使用杰卡德相似系数
Min-wise independent permutations
Nilsimsa Hash
Random projection

simhash 是 Google 的爬虫用来文档去重。 simhash 最牛逼的一点就是将一个文档，最后转换成一个 64 位的字节，然后判断重复只需要判断他们的特征字的距离是不是小于 n（根据经验这个 n 一般取值为 3），就可以判断两个文档是否相似。这大大简化了文档相似性的比较。

Simhash 由 Moses Charikar, google 2006 年做了 minhash 和 simhash 的大规模数据的比较，2007 年 Google 说使用 simhash 用作爬虫去重，使用 minhash 做新闻个性化。

simhash 的计算也很简单，

首先抽取文档的关键字，比如前 10 个关键字，以及它们的权重 (feature, weight), 记录为 [(feature1, weight1), (feature1,weight2), ..., (featuren,weightn)]
计算 feature 的 hash 值，记为 [(hash(feature1), weight1), (hash(feature1),weight2), ..., (hash(featuren),weightn)], 如图，假设 hash 值的 bit 数为 6 位，图中第一个 feature1 的 hash 值为 100110, 权重位 weight1。
然后对这些值按位进行累加，如果这个位是 1, 则该位上加上他的权重 weight, 如果是 0，则减去 weight，最后生成一个 6 个数字，每个位上一个数字，例如上图中位 [13, 108, -22, -5, -32, 55]
将数值转换成 0,1 即可 [13, 108, -22, -5, -32, 55] -> 110001, 正值为 1, 负值为 0 即可

这样，就可以将一个文档映射成一个数字了，上图中使用 6bit, 你可以选择合适的大小，比如 64 比特，可以转化成一个 uint64 整数。

下一步就是根据 simhash 值计算两个文档的相似度，使用汉明距离计算，可以方便的使用 xor 操作。
123
A = 100111;B = 101010;hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;

这个例子中A和B的汉明距离为 3。

go 标准库中已经有快速计算一个整数的二进制形式中包含 1 个数的函数：bits.OnesCount64，使用 <> 中介绍的算法。

Go 有几个 simhash 的实现，比如 mfonda/simhash、AllenDang/simhash、simhash-lsh、safeie/simhash, 但是对于中文来说，还需要一个中文分词和抽取关键字的功能，这些库对中文不友好，中文文档的比较可以使用 yanyiwu/gosimhash 以及修改版 HaoyuHu/gosimhash。

不过我最后计算相似性使用的是 bowsim + jieba。

golang中的局部敏感哈希介绍

分类

标签云