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

[phpfpm]

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

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

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

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

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

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

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

[phpfpm]

@imn1 我尝试了一下算 hash dup 的算力。
必要的缓存优化我做了，hash 全部读取到内存没有 io 问题。

计算 5(个算法）*200 个 src*10k 个目标的汉明距离大概需要 1 分钟
i5 4200U@1.6G 睿频到 2.2 的单核

如果目标上升到 1M(100 倍），5*200 这组需要的时间将会上升到 100 分钟

当然换一个好点的 cpu 提升 10 倍也就顶天了，10 分钟算 200 个（因为前面的 target 少）

1M=200*5000, 算均值是 5 分钟一批，需要 25000 分钟，大概 400 个小时。

[phpfpm]

@also24 又做了一个优化，比较 distance 之前算下 bit count 的差值，超过阈值就不算了。
这样又可以快一点点。

[imn1]

@phpfpm #21
有点没看明白
你的程序是 compare(pic1, pic2)，在里面 hash 然后比较，这样的么？
这样 compare(pic1, pic3)的话，pic1 不是又要重新 hash 一次？

应该转成两个步骤
hash1=img_hash(pic1)
hash2=img_hash(pic2)
hash3=img_hash(pic3)
……
然后入库
用数据库的值 compare(hash1, hash2)，这个不需要多次 hash 了

[phpfpm]

@imn1 处理的已经是针对 hash，而不是图片了。

踩了一个语言的坑，有一些代码写的还不够 dry，目前已经优化到计算
5*200*25k 个 distance 用 10s 了。

[lizytalk]

lsh 可以么？

[phpfpm]

@lizytalk lsh 是分段的，会降低敏感度，因为图片无法分段。

[imn1]

@phpfpm
呃，我想起 RadialVariance/ColorMoment 是用在什么场合较佳了
aHash/pHash/dHash 对于有较大水印的图判断不准，多数为 False，但这两个能判断出是相似的图(True)

[also24]

@phpfpm #22
对，我说的 1 的数量其实就是 bit count
不过大部分环境下都有对 bit count 方法做了优化的原生方法，刚才忘了说了……

上次搞这个事儿大概是 4 年前了，所以忘了好多细节 =。=

[imn1]

@phpfpm
还有一个是旋转的图也能判别，我忘了是哪个，不过网络图片这个问题不常见，摄影的才比较多

[phpfpm]

@also24 我直接硬数的，反正 n^2 的算法里面的 n 次 bit 计算怎么搞都不差太多……
但是优点确实是能省好多 distance
毛估，distance 计算数量减少百分之 90，但是多算了 n 次绝对值相减，里外里效率提升 50%这样

ext_gmp 的 distance 已经很省时间了

[phpfpm]

@imn1 世界上最好的语言对 OpenCV 的封装不好。。。
当然 php74 之后就有 ffp 了，拭目以待吧~

[phpfpm]

@imn1 更正一下，FFI

我的场景这个判重已经足够了，稍后算一下几个 hash 算法的 dist 的权重，做一个新的阈值。

[yuruizhe]

@phpfpm
有个不成熟的想法，设置一个“绝对距离”的概念
绝对距离=0{0000}
绝对距离=1{0001，0010，0100，1000}
绝对距离=2{0011，0101，0110，...}
...
1.反正每个组内的元素，两两汉明距离都为 2 或 4 或 6 或...
2.在两个临近组间找汉明距离为 1 的两个点
依次类推...
（脑袋一拍，没有验证，不要怼我）

[JCZ2MkKb5S8ZX9pq]

自己本機上處理過，hash 之後丟數據庫了，重複的加數組最後再摘出來。
然後 hash 前分精度，先 8x8 過掉一些，重複的部分再提高精度 hash 。
1Mx1M 這個應該是不必的。

[phpfpm]

@yuruizhe 没毛病，空间换时间。
你空间给小了和 1-count 预处理效果差不多
给大了……你给不起。。
128bit 不小的。。。

[vchar2ex]

https://github.com/idealo/imagededup 这里 phash, dhash 有现成的，可以测试一下看看效果如何

[phpfpm]

@vchar2ex 我已经找到实现了，我的问题不是如何算 hash，而是如何降低复杂度快速去找。

[NcAtN]

VideoComparerWin 这个是视频查重的..你看下原理 可以用来图片么 还是这个工具直接带图片查重 忘记了

[yuruizhe]

@phpfpm
不是真正的分配 2^128 那么多的空间，我的意思是分箱，把哈希码分组存在 subset 里，如果 element 在 subset_1 中，就去 subset_0 与 subset_2 里寻找与 element 的汉明距离为 1 的其他 element

[tzm41]

我想法感觉跟楼上几位相似。楼主的问题是要求 L1 nearest neighbors，数据是 128-dim binary 。近似加快的方法就是做一个 L2 embedding，感觉应该是 Johnson-Lindenstrauss 之类的。