在业务中我们经常会遇到查重的需求,例如给定一个文本字符串,判断在已有的文档中,是否存在与其相似的。
想要实现这类功能的方式有很多种,一种高效的方式是先利用 SinHash 将数据降维压缩成一串哈希值,再利用海明距离(Hamming Distance) 来比较两者之间的相似度。
SinHash 是一种局部敏感性哈希算法,特别适合在海量数据下的场景使用。
恰好在 ClickHouse 中现在已经内置了 MinHash 和 海明距离的相关函数,相关PR在此:
https://github.com/ClickHouse/ClickHouse/pull/7649。
接下来就找个例子来体验一下吧。
准备4个文本字符串,用 SimHash 函数计算它们的哈希值:
SELECT
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。') AS sh1,
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。') AS sh2,
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个,原理上相当于伪随机数产生算法。') AS sh3,
ngramSimHash('SimHash本身属于一种局部敏感哈希算法,它产生的Hash签名在一定程度上可以表征原内容的相似度。') AS sh4
Query id: 7cf4a1d1-266f-4638-a75c-88ab1d93dbdf
┌──────sh1─┬──────sh2─┬──────sh3─┬───────sh4─┐
│ 20645847 │ 20645847 │ 54200087 │ 957490773 │
└──────────┴──────────┴──────────┴───────────┘
1 rows in set. Elapsed: 0.004 sec.
从哈希值直观的来看,sh1 和 sh2 是两段完全相同的文本,而 sh3 和 sh4 与 sh1 是有差异的,但是直接通过哈希值我们并不能判断它们的相似程度,这个时候就需要利用海明距离了。
使用 bitHammingDistance 函数计算哈希值之间的差异距离:
SELECT
bitHammingDistance(sh1, sh2) AS `1and2`,
bitHammingDistance(sh1, sh3) AS `1and3`,
bitHammingDistance(sh1, sh4) AS `1and4`
FROM
(
SELECT
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。') AS sh1,
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。') AS sh2,
ngramSimHash('传统的hash算法只负责将原始内容尽量均匀随机地映射为一个,原理上相当于伪随机数产生算法。') AS sh3,
ngramSimHash('SimHash本身属于一种局部敏感哈希算法,它产生的Hash签名在一定程度上可以表征原内容的相似度。') AS sh4
)
Query id: c5b24238-cf85-4eb0-a77c-0b82a888a439
┌─1and2─┬─1and3─┬─1and4─┐
│ 0 │ 3 │ 10 │
└───────┴───────┴───────┘
1 rows in set. Elapsed: 0.004 sec.
从结果可得知:
好了,这次的分享就到这里吧,原创不易,如果这篇文章对你有帮助,欢迎 点赞、转发、在看 三连击
欢迎大家扫码关注我的公众号和视频号:
本文分享自 ClickHouse的秘密基地 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!