有没有将近似的 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 距离无论是在线查找还是聚类都是一堆算法数据结构可以用。

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

[shengchen11]

java 的话重写 hashCode 方法应该可以吧，调用 super.hashCode ，再加上自己的逻辑

[3dwelcome]

@binux 我 google 查了一下，那么多图片相似度算法，最后一步都是计算汉明距离，

楼主的主楼诉求，貌似就是为了省略掉这最后一步。N x N (n=十万), 数量不大，也不算很小了。

理论上可以通过一些 floor 技巧实现。

比如图片 1 的 hash 是 3.5 ，1.2 ...
图片 2 的 hash 是 3.45, 1.02...

都 floor 后，都变成了 3, 1, ...整型，那么当数字变成字符串文件名后，两者就是匹配的。

[wakiki]

典型的 X-Y 问题，上面还讨论得这么起劲：
1 ）楼主想要「图片查重」
2 ）楼主以为「近似的 hash 认为是相同 hash 的 hashset 」是解决「图片查重」的方法
3 ）但是楼主不知道「近似的 hash 认为是相同 hash 的 hashset 」应该怎么做
4 ）于是楼主来 V2 问 「近似的 hash 认为是相同 hash 的 hashset 」 应该怎么做？

不是应该甩给楼主图像相似度算法么

[ryd994]

@3dwelcome 那 2.99 和 3.0 呢？
凭什么 2.1 和 2.9 就相似，2.99 和 3.0 就不相似？

[ipwx]

@3dwelcome 这种时候当然要看大 postgresql

https://wiki.postgresql.org/wiki/What%27s_new_in_PostgreSQL_9.1#K-Nearest-Neighbor_Indexing
https://github.com/fake-name/pg-spgist_hamming/

[3dwelcome]

@ryd994 你说的对，是有点问题。

于是这问题又变成了如何对 float 进行 hash 处理，如何把 2.99 和 3.00 计算成同一个 hash 值。

hmm.. 算了，我表示放弃追贴了。越飘越远。

[3dwelcome]

@ryd994 我上面提到的 floor 的技巧，严格意义上来说，应该叫松散四叉树算法（ loose quadtree ）。

就是 2.99 既能归属到[1,2]这个区域，又能归属到[2,3]，同时占了两个区域，就叫 loose 。

有那么一点点类似 25 楼的 vptree/bktree 理念，不过还是很复杂。

[ipwx]

@3dwelcome 那就 kd-tree

[ipwx]

@3dwelcome https://www.2ndquadrant.com/en/blog/postgresql-12-implementing-k-nearest-neighbor-space-partitioned-generalized-search-tree-indexes/

[skies457]

image embedding?

[ruanimal]

simhash

[binux]

@3dwelcome 实际图片去重用不到那么大的范围，大部分图片相似 hash 的摘要已经是相似图片 hash 相同了，更何况很多算法可以调整精度，你试试就知道了。

[LeeReamond]

@binux 朋友你真的认真看主题了吗？主题询问的是近似字符串去重算法，而不是图片摘要算法，提到图片无非是为了进一步解释背景而已，你在这里叫嚷说有很多成熟算法，如果你很熟悉，不屑于参与这种低级讨论，请直接发关键字或文章链接，而不是反复地发“有很多，为什么你不用”。如果你认为相同图片经过合适算法的摘要本身就是相同的，那只能说既然是感知哈希，无非是精度问题

@yfugibr aaaaa 变成 bbbbb 的问题是输入顺序导致的，排序后应该问题不大

[zoudm]

Locality-sensitive hashing?

[binux]

@LeeReamond 你到底是在问近似 hash 去重还是近似字符串去重？
有问题就直接问，不要你以为 Y 是解决 X 的方法就去问 Y 。

[3dwelcome]

@binux 花了点时间，看了一下 github 上的 pHash 算法( https://github.com/starkdg/phash)，还是有不少问题。

第一，dct 里均值计算( https://github.com/starkdg/phash/blob/master/src/pHash.cpp#L267)，应该排除掉第一个浮点，这个值代表图片能量的总和，也就是全局明暗，而不是图片细节描述。
那个 pHash 算法，就 float median = subsec.median();求均值，然后 if (current_pixel > median) hash |= 0x01;这样计算并不精确。

第二，dct 的特性，是左上角高能量，代表低频信号。右下角低能量，代表高频信号。一般丢弃右下角是没问题的，JPEG DCT 都是用 zig-zag 序列来处理。
而 pHash 算法，还是简单暴力用了一个 8x8 的正方形，完全有改进的余地。

第三，dct 的 image hash, 是可以做成不用计算汉明距离，直接靠字符串匹配，来高速适配的。
前提是输出的 hash 字符串，必须根据重要性来排序，可以末尾丢弃。举个例子比如 hash 是 CDEF ，那么 CD 就是要比 EF 重要，光匹配 CD 前缀也是可以的。可惜 pHash 的 8x8 正方形做不到这点，必须改成 zig-zag 序列输出。

第四，只要有超高速 hashset 识别算法，就能进行视频内容识别了。

[binux]

@3dwelcome 不做算法研究真没必要死磕一个算法。好不好用，哪个好用拿样例测一下就知道了，毕竟实际使用中也不会要同时对抗模糊裁切缩放...啊。

[LeeReamond]

@binux 建议重修义务教育语文，本帖标题为“有没有将近似的 hash 认为是相同 hash 的 hashset ？”，一般认为 hash 是字符串结构，标题含义为，传统 hashset 精确匹配，如何应对不精确匹配的情况，不知道你在杠什么。另外实际使用中图片去重就是要对抗模糊剪裁缩放。实际使用场景就是互联网上的图片来源，相同图片会被各种裁剪 /调整比例 /反复压缩，我不知道你是哪里的实际使用经验，去重时不需要考虑这些问题。


@3dwelcome 老哥你是楼里唯一一个一直在认真回我的，我最后给你更新一下我的解决办法。首先我使用的 phash 算法没有进行 dct ，而是直接用 rgb 模式下的三平面的向量变化，也就是单个平面里面 8*8 向量的增加或减少来形成 hash 。我对我自己的场景做了一些小修改，因为我的图片大多为电脑或手机屏幕适配，通常为 16:9 或者 9 比 16 的近似比例，我把 8*8 稍微扩大了一些。

关于近似去重，最后采用的是多年前谷歌的近似 simhash 搜索的简化方法，需要储存结构做对应优化。其原理是，如果要求一个长度为 64 （或任意）的 binary ，与另一个等长 binary 的汉明距离小于 3 （意味着他们之间有 0 处或 1/2/3 处不同），那么只需要将 64 平均分割为 4 段，即使出现 3 处不同，4 段中的某一段一定完全相同。同理，如果要求距离小于 20 ，则平均分割为 21 段。将其转化为完全相同问题后，可以利用 hash 结构的索引能力，原先需要遍历十万次对比，现在只需要进行 4 次索引，挑选出完全相同的集合的并集，他们之中有可能存在不符合需求的结果，但符合需求的（汉明距离小于 3 ）一定在其中，在此基础上进行完全搜索，即可精准定位。

使用这个方法后，原先的 100k 数量级对象总共需要进行 5 亿次遍历（加上我的向量数量为 800+，总计需要 4000 亿次向量相等计算），可以优化到非常低的水平，我目前的数据集大小是可以 1s 内出结果的，优化之前速度非常慢。

[binux]

@LeeReamond
> 一般认为 hash 是字符串结构
没人这么认为，hash 一般是定长 binary ，比较也是按位比较的，当然和字符串不同了。
而且你说了是电脑手机壁纸，那它最多裁剪边框，或者从电脑比例裁剪成手机比例（它们还算不算重复还另说呢），不会出现裁出个人头的情况，你选一个利用 image feature 产生 hash 的算法不就完了。

壁纸去重我 8 年前就做过了，从自己写图片特征提取做 hash 再像你一样 hash 距离去重，到最后找一个合适的 hash 算法就够了。
8 年前还没有那么多实现好的库可以用呢。