最近有一个项目需要用到simhash.获取图片的hash值并保存到数据库。在生成新的hash的时候和数据库进行比对。达到去重的效果。假如图片达到了一定数量级，那么每次查询会进行全表扫描，效率是比较低下的，而数据库默认的一些索引又无法达到这个需求，后来看到了BK树。记录一下

使用Python的库imageHash 运算后会得到64bit长度的结果(最后使用了hex编码导致结果看起来很长)。如果两张图片的bit进行异或后不同的地方越小。说明两张图片越相似。度量这2个bit不相似程度被称之为汉明距离

这个距离它又满足以下性质(被称为Levenshtein)

  1. d(x, y) = 0 当且仅当 x=y （Levenshtein距离为0 <==> 字符串相等）
  2. d(x, y) = d(y, x) （从x变到y的最少步数就是从y变到x的最少步数）
  3. d(x, y) + d(y, z) >= d(x, z) （从x变到z所需的步数不会超过x先变成y再变成z的步数）

BK树

为了加速查找, 构建了这样一种树结构。

  1. 任选一个节点当做根节点
  2. 插入节点的时候和根节点对比得到距离。如果该距离不存在则新建一个节点作为根节点的子节点。如果节点存在则获得节点作为根节点进行递归操作

第二步的意义在于任何一个节点下面的元素对于该节点的距离都是相等的。构建就达到了这个效果。别的啥事没做。

查找过程。查找的原理主要依靠第三条性质d(x, y) + d(y, z) >= d(x, z) .
假设我们有这样一个查询要求。需要查找字符串target距离不大于n的所有结果。

1
2
3
4
设root为x, target为y
d(root, target) + d(target, element) >= d(root, element)
d(target, element)的取值范围是[0, n]
得到d(root, element) 的最大值是 n + d(root, target)

因此我们根据这个不等式实现了剪枝的效果。对于满足条件的元素。将其设置为根元素。递归得到所有满足条件的元素

VP树

VP树和BK树原理差不多。优点是当需要查询的距离N更大的时候效率更高(具体原理我还不太了解。写的时候发现很多时候它的效率甚至是不及BK树的)。

BK树可以看出是一个多叉树。每个节点下面可以有多个节点。VP树不同，它是一个二叉树。根据我的需求。简单起见。每一个节点我设置了相同的阈值。距离小于阈值则放在左边，大于则放在右边。

查找的时候还挺尴尬的。根据上面说的d(root, element) <= n + d(root, target)。当节点的阈值小于这个值的时候左右子节点都需要遍历。当节点阈值大于的时候就只需要遍历左边(达到剪枝的效果)

注意: 以上我都只考虑了添加，没有考虑修改和删除的事情。

Python版本代码实现如下

参考资料

编辑距离、拼写检查与度量空间：一个有趣的数据结构
VP Tree