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

[LeeReamond]

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

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

新建一个 hashset ，不往里面添加重复的 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 年前还没有那么多实现好的库可以用呢。