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

获得图片的simhash

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

1
2
3
4
5
6
7
8
9
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的效果。可以看我写的这个

数据库优化

  • 来个示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
--  创建表
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以上版本)

1
2
3
4
git clone .......
cd bktree
USE_PGXS=1 make
USE_PGXS=1 make install

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

  • 使用流程
1
2
3
4
5
6
7
8
9
10
11
12
13
-- 启用扩展
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)

世界真美妙┑( ̄Д  ̄)┍

参考资料

海量数据,海明(simhash)距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践
bit_count function in PostgreSQL