利用BK树优化汉明距离查询

上一篇介绍了BK树和VP树，并说明用它可以优化汉明距离的查询。用来处理重复图片的问题。本篇我们做出示例演示如何使用，最终的结果是100万条数据。相对于全表遍历的31秒下降到54毫秒。使用了正确的索引速度提升了五百多倍

获得图片的simhash

我们直接使用python的第三方库imagehash。代码如下

from PIL import Image
import imagehash

def get_phash(file_path):
    img = Image.open(file_path)
    phash = imagehash.phash(img).hash.flatten()
    phash_list = list(map(bool, phash))

    return sum((2 ** k) * v for k, v in enumerate(phash_list[1:][::-1]))

需要注意的是。默认得到的phash是一个经过hex编码的字符串。这样会很长，而我们需要保存到数据库的数据是一个bigint类型。因此我们直接获得64位的np.array，将它转换成数字。因为int64中第一位是符号位。后63位是补码。如果直接将64位都转成正整数，很有可能会保存出错。从最方便的角度来说我们可以去掉第一位(实际上我测试了好多个。发现第一位基本都是1)。这样转换得到的数字就能直接存储到数据库了。

如果真的要模拟转换成bigint的效果。可以看我写的这个

数据库优化

来个示例

--  创建表
create table if not exists int8tmp_2
(
	a bigint
);

-- 写入一百万条数据
INSERT INTO int8tmp_2 SELECT val
                      FROM (SELECT sqrt(random()) :: NUMERIC * 9223372036854775807 * 2 -
                                   9223372036854775807 :: NUMERIC AS val
                            FROM generate_series(1, 1000000)) t;
-- 创建一个查询函数
CREATE OR REPLACE FUNCTION bit_count(value BIGINT)
  RETURNS NUMERIC
AS $$ SELECT SUM((value >> bit) & 1)
      FROM generate_series(0, 63) bit $$
LANGUAGE SQL IMMUTABLE STRICT;

-- 查询
SELECT
  a,
  bit_count(a # 8192711222023195111) AS hd
FROM int8tmp_2
WHERE bit_count(a # 8192711222023195111) < 4
ORDER BY hd;    

-- 结果大概这样
-- [2018-03-04 11:06:56] 1 row retrieved starting from 1 in 25s 403ms (execution: 25s 383ms, fetching: 20ms)

使用BK树创建索引

我选择了这个扩展fake-name/pg-spgist_hamming. 安装的套路是这样的(只支持PG9.6以上版本)

git clone .......
cd bktree
USE_PGXS=1 make
USE_PGXS=1 make install

注意这个库同时提供了bktree和vptree,但是我没搞懂vptree,vptree的表现很奇怪,另外不能同时使用bktree和vptree。因为它们有一些重载的操作符重复了

使用流程

-- 启用扩展
CREATE EXTENSION bktree;
-- 创建
CREATE INDEX IF NOT EXISTS int8idx_2 ON int8tmp_2 USING spgist ( a bktree_ops );
-- 查询( <-> 运算符表示计算汉明距离, <@()表示符合汉明距离小于N)
SELECT
  a,
  a <-> 8192711222023195111 AS hd
FROM int8tmp_2
WHERE a <@ (8192711222023195111, 4)
ORDER BY hd;
-- 结果大概是这样的
[2018-03-04 11:18:25] 1 row retrieved starting from 1 in 44ms (execution: 31ms, fetching: 13ms)