上期文章介绍 dHash 算法，我们便可以计算一个图片的哈希了。那么我们该如何通过一堆图片的哈希值找到相似的图片呢？本期就来聊聊这个问题。
汉明距离
对于两个哈希值，我们如何量化它们“相似”的程度呢？在上一期我们已经引入了 汉明距离 的概念，这就是答案了。我们不妨看看它的定义。
在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
对于二进制串，简单一点来说就是逐位比较两个串，统计差异的个数。举个例子来说，计算 10101011 和 11011101 的汉明距离，方法如下所示：
1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 1
^ ^ ^ ^ ^
（"^"所指的位置为不同的地方）
因此，汉明距离为 5 。
如果你不明白为什么图片的相似度可以用哈希值的汉明距离来衡量，请结合本系列的上一篇文章，看看图片哈希值的生成过程。我们处理后的图片一律是灰度化的 9x8 图片，处理后的图片如果有差异，举个例子来说，图片A、B都是处理后的图片，A的第一个像素比第二个像素亮，B反之。那么A哈希值的第一位就是1，B哈希值的第一位就是0，它们汉明距离就至少是 1 了，因为它们的哈希值至少有一处不匹配。
注意，以下的哈希值无论是用十六进制表示还是变成其他编码，我们都用它的原始二进制值来计算汉明距离，这也是考虑到哈希值的生成过程。一定要先搞懂通过汉明距离衡量两个图片相似度的原理。
快速检索相近哈希值：分段比较
有了以上方法我们就可以实现朴素的比较了，也就是两两比较。对于 n 个哈希值，我们需要比较 \(\frac{1}{2} n(n - 1)\) 次，对于海量的图片来说，这显然是不可接受的。因为汉明距离本身的特性，我们无法通过二分查找之类的方式快速查找。
原理
这里给出一个简单易懂的思路。对于长度为 m 的哈希值（记作 h ），我们想要找到与其汉明距离不高于 k 的所有哈希值。首先对于所有哈希值，我们有一步预操作：将其分为长度相等的 k 段，分开储存。在查找时，我们首先只关注第 1 段，找到这一段与 h 的第 1 段哈希值不相同的所有哈希值，把这些哈希值的集合记作 a[1] ；然后只关注第 2 段，找到这一段与 h 的第 2 段哈希值不相同的所有哈希值，把这些哈希值的集合记作 a[2] 。以此类推，我们得到了 k 个集合：a[1]、a[2]... 直到 a[k]。求得这几个集合的交集，这样的话我们最终想要的哈希值，全部都在这个集合的补集中了。
乍一看是有点复杂，我们详细讲讲这其中的原理。我们先回到比较第 1 段的这一步。什么时候两个哈希值的第 1 段是不相同的呢？很自然，此时它们的第 1 段至少有一位不同。比较第 2 段，也是如此。那么什么时候两个哈希值的第 1 段和第 2 段均不同呢？第 1 段至少有一位不同，第 2 段也是如此，此时整个哈希值至少有 2 位不同，也就是说汉明距离至少为 2 。那么从第 1 段到第 k 段都有不同的时候，就是哈希值的汉明距离至少有 k 的时候。
注意一下，最终的哈希值集合，与我们求得的集合是后者包含前者的关系。这是因为，“从第 1 段到第 k 段，每段都有至少一位不同” 和 “汉明距离至少为 k”，前者是后者的充分不必要条件，因为某一段可以包含不止一位的不同。
等一下！对于不同的 k ，难道还要重新分段存储一次吗？还有，我们怎么能保证 m 一定能被 k 整除呢？其实 k 是一个固定的值，取 \(\dfrac{m}{4}\) 或者 \(\dfrac{m}{8}\) 就可以满足大部分的查询需求了，我们只需要在快速检索的集合中使用朴素方法进行比较即可。
性能分析
在哈希值随机分布的情况下，可以推算出筛选后的数据占比为 \(1 - (1 - 2 ^ {-\frac{m}{k}}) ^ k\)。比如说，长度为 64 bit 的哈希值，差异程度不高于 25 % (k = 16)，则快速检索后的数据规模占比为原来的 0.64 。
其实快速检索的方法对于数量级没有优化，都是 \(O(n^2)\)，只是优化了常数而已。
最后
文章结尾略有一点草率，以后再完善了。至少，把这个系列（一共就两篇文章）完结掉了。接下来一年由于学业繁忙，更新频率也会略有下降吧。
