有没有将近似的 hash 认为是相同 hash 的 hashset？

[LeeReamond]

如题，十万张图片查重，每个图片生成一个 100 位的 hash 。

想要实现的效果是设计一个阈值，比如 100 位里 hamming distance 小于 10 的就认为是同一张图。

新建一个 hashset ，不往里面添加重复的 hash ，相似的认为是同一个。

十万的数量级不是很大，直接遍历的话也不会算很久，但是类似的需求有什么算法可以实现不做多余运算吗？

[jdhao]

?那你自己写个逻辑不就行了吗？

[binux]

跟你说了已经有很多图片相似 hash 的算法了，你还要问一个 Y 问题。

[loadingimg]

推荐个库： https://github.com/idealo/imagededup/

[3dwelcome]

这问题有点复杂，因为已经生成 hash 了，问题的本质是如何对 hash 值组成的字符串，做模糊匹配。

我个人想法是，先遍历十万数组，把 100 位做 bit 出现概率分析，去掉最低频率的 36 位。最后形成十万数量级的 64 位完美 hash ，直接丢掉 hashtable 进行一一匹配，处理速度会非常快。

匹配成功后，再进行二次 hamming distance 的严格配对。

[zcf0508]

https: //github. com/JohannesBuchner/imagehash

https: //segmentfault. com/a/1190000021236326

相似度算法用建单的汉明距离或者余弦相似度都可以，阈值你自己设置。

[3dwelcome]

举个例子，怎么对

hello world
healo world
heelo world

这三个字符串做模糊 hash ，并且让 hash 值的结果完全一致？

[zxCoder]

怎么定义相似的 hash

[3dwelcome]

@zxCoder "怎么定义相似的 hash"

6 楼就是相似的 hash 案例。两个字符串错一个或者两个英文，hash 结果是一样的，但错三个以上，hash 就不一样了。

[yfugibr]

@3dwelcome #8

aaaaa
aaaab
aaabb
aabbb
abbbb
bbbbb

这样的话相邻两个都是相同的 hash ，所以 aaaaa 和 bbbbb 也是相同 hash 了

[3dwelcome]

@yfugibr 应该还是有这种算法，做字符串大量的模糊匹配。比如 word 里，英文单词拼写纠错，就是模糊查找英文字典的一个典型应用。

就是还没想明白，具体算法应该怎么写。

[shylockhg]

hash 算法就是要吧输入均匀分布到输出空间里面，这种情况还算什么相似性；不是南辕北辙么

[lithiumii]

图片去重用 perceptual hash 呀，就是为了去重极度相似但不完全一致的图片而生的

[3dwelcome]

@shylockhg “不是南辕北辙么”有这种算法的，英文里叫 fuzzy hashing ，最初是比较两个文件的相似性。

比如两个源代码文件，内容能达到 99%的相似度，fuzzy hashing 的结果就是高度一致的。

hash 的本质，就是把多余的数据给扔掉，剩下的均匀分布到输出空间里。至于把数据哪一部分给怎么扔掉，就是这个技术的核心，需要对源数据进行分析处理。比如源代码预处理，就可以把注释全部扔掉，这是次要的信息。

按信息的重要程度排序，反复对数据处理，重复扔掉几次次要信息后，最终计算的 hash ，这就是模糊 hash 算法了。

[ruxuan1306]

哈希有雪崩效应，输入变一个比特输出会面目全非，你这种需要使用能够将相似图像映射为相似哈希值的专用函数。

一个思路是，直接使用别人在大规模图像数据集上预训练的图像分类模型作为这个专用函数，将这个模型最后一个隐藏层的输出作为该图像的哈希值，然后每个图像哈希值之间的欧氏距离就可以表示相似度。

[3dwelcome]

by the way, JPEG 压缩算法，也是把高频信息作为次要信息扔掉后，达到压缩图片数据的目的。

把图片压缩到极致后，也能变相达到图片模糊 hash 的目的。

[ruxuan1306]

@3dwelcome #15 确实，本质上就是找到一种特征提取方法，比如直接统一缩放为 32*32 ，相似的图像这时肯定这个 32*32 的缩略图也相似，这个缩略图就可以作为特征（哈希值）。

[binux]

我不知道这个问题有什么好讨论的，无论是图片相似 hash ，fuzzy match 还是 hash 的定义都已经有很多现成的研究，算法，数据结构了。
用就完了啊！最多你说某个算法不适合你的场景，那你测一下不就好了。怎么着？你对前任的成果看都不看一眼就打算自己发明一个吗？

[GrayXu]

@binux +1 ，这问题的题干乍看还看不太懂，原来要的是个 LSH 。。

[3dwelcome]

@binux 好像是没有这种算法，楼主的意思，是想把 hash 作为文件名。

如果多个图片是相似的，那么文件名就会冲突，最终磁盘只能保存一个图片。

目前开源的算法，都是给两个图片，求他们的相似值。但这个相似值又不能作为文件名，给保存下来。

[binux]

@3dwelcome 怎么没有，前面都说了好几个了。直接搜“图片相似 hash”就可以。
你要搞 hash 距离无论是在线查找还是聚类都是一堆算法数据结构可以用。

这么常见的需求别小看计算机科学了。