百万量级的汉明距离的数据有没有什么快速计算接近的方法呢？

[phpfpm]

目前有近 100w 图片需要判重，挑了几个 hash 算法，正在跑 hamming code，都是 128bit 的 binary

这些图片都是经过 md5 与判重之后的图片了，所以需要找出来一些汉明距离接近的肉眼观察一下

所以要找到一些距离是 0,1,2,3 的图片组。

当然了，挨个计算一次(1M * 1M = 1T)

好像似乎，也不是很长时间吧，还勉强能接受，跑几天跑完了

有什么能再快一些的算法吗？

目前有一台机器(9400f+1660s)可以跑一点机器学习，勉强够看。

[douglas1997]

先算出图像指纹，在进行比对？我觉得算法慢是因为直接算一对一对图像的汉明距离，这个才是费时间的，而不是 1M*1M 。

比较简单直接的策略，可以考虑：

- 图像降采样
- 取 128Bit 的其中 8Bit/16Bit 作为比对的样本数据
- 生成图像指纹
- 多进程

[mcfog]

简单的削减一下数量级吧，比如按 bit1 的位数分组，只在邻接的 k 组之间比较。或者先按前 k 位分组在组内找，然后按后 k 位分组在组内找

[newdongyuwei]

图片的话 phash，dhash 比较靠谱吧

[momocraft]

排序後逐個比對可以嗎? (你的問題好像可以接受實際接近但漏掉的, 即 true negative)

[ipwx]

你需要的是，能够用向量空间的欧几里得距离表示图片相似度的某个模型。

因为欧几里得距离下，可以用 KD-tree 进行相似向量查找。整个数据集两两找一遍是 N log N 的。

[momocraft]

可能會漏掉非常多, 排序會導致實際只比較 LSB 附近的 bit

[ifzzzh]

locality-sensitive hashing 了解一下

[also24]

之前做过类似需求… 也是困扰在这个地方

[liukangxu]

看看 Google 是怎么做的： https://www2007.org/papers/paper215.pdf

[phpfpm]

@douglas1997 128bit 已经是图像指纹了，不是两个 1M 比指纹，是 1M 个 128bit 的 hash 比距离

[phpfpm]

@newdongyuwei 已经在跑 p,dhash 了

确实 dhash 好一些，还挑了几个别的算法。
全量跑一遍 1M*5 个 hash 算法得两三天(主要是资源在 nas 上 io 慢机器也不快）


@momocraft

排序肯定不行，排序相当于只有前缀分组，会漏掉特别多
@ipwx
对，有这玩意么
其实细想一下，汉明距离就是 n-dimission 的距离，不过 nlgn 的算法仅限于 2 维来着？

[phpfpm]

@ifzzzh
@liukangxu
我看下这俩算法，不过我估计学不会……

[also24]

想起来之前做的一个简单优化：
统计 phash 中 1 的个数，然后只搜索对比 1 的数量相近的内容。

假如我们需要汉明距离小于等于 6，那 1 的数量差也不应该大于 6 才对。

[liukangxu]

@phpfpm 看 Google 这篇论文就够了，和你的场景基本一致，解法也很简单

[phpfpm]

@all

算了 25k of 720k 的摘要 hash，用 dhash 就能找到约 0.5k 的 dup，相当于汉明距离=0

这个已经足够 make sense 了~

汉明距离 1+的以后慢慢算，可以结合几种不同的 hash 去重~

[phpfpm]

@also24 嗯 可以按照 1 的个数将分组缩小 128/dist 倍，计算量也减少这么多。
@liukangxu 感谢！

[ipwx]

@phpfpm emmm 其实 kd-tree 是 kN log N，k 是维度。所以 k 不大的情况下，也差不多是 N log N 了。但是它处理的是 特征向量，不是汉明码。汉明码是 0-1 binary 数据，反而不好处理。特征向量是实数向量，反而好处理一些。

产生图片特征向量，其实应该还是个 research topic 。我搞深度学习，但是不搞图片压缩，不太清楚那种算法比较成熟。你要让我想一下哪些方向有可能，然后进一步进入这个领域研究，我可能做得到。但现阶段给不了你意见。

[aec4d]

ficapy.com/2018/03/04/Postgresql_use_bktree_hamming/ 以前做过类似的，BK 树可以优化

[imn1]

如果只是百万级汉明不需要几天啊，我觉得#1 说得对，你是否每次都算一遍？
你应该缓存 hash 值的
然后建议分段，如果有分类别什么的，那将大大降低循环次数

windows 有个软件 Similar Images，32bit，可以缓存 hash，作者应该弃坑了，好几年没更新，百万级也就小时级别（不过一次跑百万可能会崩，只能分段）
我自己写的 python 也不用那么久，只是估计，没试过百万，不过我是 hash 和匹配分开（整理时顺便 hash 入库，目前约 50M 张），然后匹配是家常便饭，经常跑小量（千张到万张）匹配，主要是入库时做去重，已经整理入库的就不需要互相比较了

说说算法，常见的 hash 有这几种
cv2.img_hash_PHash
cv2.img_hash_AverageHash
cv2.img_hash_RadialVarianceHash
cv2.img_hash_MarrHildrethHash
cv2.img_hash_ColorMomentHash
cv2.img_hash_BlockMeanHash
cv2 就是 opencv，BlockMean 最快，但极其不准，基本弃了，RadialVariance/ColorMoment 较慢，但还是有点用，ahash/phash 速度适中，MarrHildrethHash 我很少用，主要是搞不清它什么场合更佳

我个人的经验是，aHahs/pHash 中其中一个匹配（ OR ），ColorMomentHash/RadialVarianceHash 中其中一个匹配（ OR ），这两组 AND 的话，基本就确定重复了 —— 指没有漏判，然后找出的结果中只有很少是错判，错判不到千分之一（分母是全体，包含不重复的）
不过临界值还是要自己调，aHash/pHash/ColorMomentHash 我都是用 3，RadialVarianceHash 我用 0.95 ，全部都比网上代码样例的建议值宽松很多，单独一个算法用这个临界值的话误判会更大，但我组合起来用误判就很小了，这样比单独一个 hash 使用更严格临界值结果还好 —— 原理是图片质量不高的话，应该宽松些，这样不会漏掉，但很多误判，然后用组合降低误判。如果图片质量很高，例如全部都是没有 PS 的摄影作品（ raw 或近似 raw ）的话，可以适当调高临界值，甚至只用一种算法也够了

还有一种模式匹配算法，不过只适合小图找大图（就是大图里面的一部分），或者有裁切的图找原图，不适合找相似的图，此处不详说了

[phpfpm]

@imn1 非常感谢这么详细的回答！

其实我还没开始计算百万级的汉明距离(o(n^2))，因为汉明码还没有预处理完——数据在 nas 上得先下载下来再算。
好吧，刚才打点看了一下，不是 io 的问题，就是 hash 算的慢（算 hash 呢，还没比呢）

服务器是一台 thinkpad 的，i5 4200u(1.6G~2.6G)
单线程跑满 hash 一个 100k 的图片大概需要 200ms （单线程），其他开销<5ms(数据库，网络，本地临时文件写）

算法（采用了 ah,dh, PercepiahHash，另外一个包的 ph 和 dh ），都是 php 的，算了 5 个 hash 。

我不太清楚其他语言算这个是不是能快一些，反正服务器也比较渣，之后跑判重肯定换个环境了，只是数据都在一个工程比较好管理。


等 hash 跑完我先用 dist=0 （完全匹配，基于数据库算下增量数据）简单提供一个服务，之后再慢慢跑 dist=1,2,3 的情况。

毛菇如果把历史数据都读取到内存当中算一趟的时间应该在可接受的范围内吧……