PostgreSQL扩展之smlar

这篇文章主要讲smlar的一则实际应用，快速检索海明距离，什么是海明距离下面做下简单介绍。

- SimHash是什么？
SimHash是Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling 》中提到的一种指纹生成算法或者叫指纹提取算法，被Google广泛应用在亿级的网页去重的Job中，作为locality sensitive hash（局部敏感哈希）的一种，其主要思想是降维，什么是降维？ 举个通俗点的例子，一篇若干数量的文本内容，经过simhash降维后，可能仅仅得到一个长度为32或64位的二进制由01组成的字符串，这一点非常相似我们的身份证，试想一下，如果你要在中国13亿+的茫茫人海中寻找一个人，如果你不知道这个人的身份证，你可能要提供姓名 ，住址， 身高，体重，性别，等等维度的因素来确定是否为某个人，从这个例子已经能看出来，如果有一个一维的核心条件身份证，那么查询则是非常快速的，如果没有一维的身份证条件，可能综合其他几个非核心的维度，也能确定一个人，但是这种查询则就比较慢了，而通过我们的SimHash算法，则就像是给每个人生成了一个身份证，使复杂的事物，能够通过降维来简化。

- 算法原理
介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步：

1. 分词
   把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。

2. hash
   通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。

3. 加权
   通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。

4. 合并
   把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4±5 -4+5 4±5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。

5. 降维
   把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

原理图：

我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。
通过simhash计算结果为：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过比较差异的位数就可以得到两串文本的差异，差异的位数，称之为“海明距离”，通常认为海明距离<3的是高度相似的文本。

- 海明距离定义
两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。在一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。

- 海明距离的应用场景
经过SimHash算法提取来的指纹（Simhash对长文本500字+比较适用，短文本可能偏差较大，具体需要根据实际场景测试），最后使用海明距离，求相似，在google的论文给出的数据中，64位的签名，在海明距离为3的情况下，可认为两篇文档是相似的或者是重复的，当然这个值只是参考值，针对自己的应用可能有不同的测试取值，我们业务使用到的是比较试题题干+试题选项来快速检索相似题。到这里相似度问题基本解决，但是按这个思路，在海量数据几百亿的数量下，效率问题还是没有解决的，因为数据是不断添加进来的，不可能每来一条数据，都要和全库的数据做一次比较，按照这种思路，处理速度会越来越慢，线性增长。针对这个问题在Google的论文中也提出了对应的思路，根据抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。道理很简单，但在把这应用到现实问题中，可是能发挥巨大作用的，这也就是数学的奥妙之处。针对海量数据的去重效率，我们可以将64位指纹，切分为4份16位的数据块，根据抽屉原理在海明距离为3的情况，如果两个文档相似，那么它必有一个块的数据是相等的，然后将4份数据通过K-V数据库或倒排索引存储起来K为16位截断指纹，V为K相等时剩余的48位指纹集合，查询时候，精确匹配这个指纹的4个16位截断，如此，假设样本库，有2^{34条数据（171亿数据），假设数据均匀分布，则每个16位（16个01数字随机组成的组合为2}16个）倒排返回的最大数量为：2^34/216=2^(34-16)=262144个候选结果，4个16位截断索引，总的结果为：4*262144=1048576，约为100多万，通过这样一来的降维处理，原来需要比较171亿次，现在只需要比较100万次即可得到结果，这样以来大大提升了计算效率。

具体到我们自己的使用场景，如何在数据库中使用这种高效的检索？通过PostgreSQL的smlar扩展实现，smlar用于实现高效的相似度查找，但是不能直接使用，我们可以利用对64位指纹进行切分（下面实例：切分为4片，每份16位进行测试），然后再通过相似度来收敛数据，已达到快速检索的目的，下面介绍下smlar的使用：

- 安装smlar

git clone git://sigaev.ru/smlar
cd smlar
USE_PGXS=1 make
USE_PGXS=1 make install
复制

- 使用介绍

test=# create extension smlar;
CREATE EXTENSION
复制

- 测试

--hmval字段为SimHash，hmarr字段为把SimHash切分为4片的数组
test=# CREATE TABLE test (id INT, hmval BIT(64), hmarr TEXT[]);
CREATE TABLE

--生成200万测试数据
test=# INSERT INTO TEST (id, hmval, hmarr)
test-#     SELECT id,
test-#            val::bit(64),
test-#            regexp_split_to_array('1_' || substring(val, 1, 16) || ',2_' ||
test(#                                  substring(val, 17, 16) || ',3_' ||
test(#                                  substring(val, 33, 16) || ',4_' ||
test(#                                  substring(val, 49, 16), ',')
test-#       FROM (SELECT id,
test(#                    (sqrt(random())::NUMERIC * 9223372036854775807 * 2 - 9223372036854775807::NUMERIC)::int8::bit(64)::text AS val
test(#               FROM generate_series(1, 2000000) t(id)) t;
INSERT 0 2000000

--查询海明距离小于3的数据，不切分，不建索引需要近3秒
test=# SELECT * FROM test WHERE LENGTH(REPLACE(BITXOR(BIT'0101101011001111001110111011111001000011100001011000000111010111', hmval)::TEXT,'0','')) < 3;
 id |                              hmval                               |                                     hmarr                                     
----+------------------------------------------------------------------+-------------------------------------------------------------------------------
  8 | 0101101011001111001110111011111001000011100001011000000111010100 | {1_0101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010100}
(1 row)

Time: 2842.908 ms (00:02.843)

--创建索引
test=# CREATE INDEX idx_hmarr_test ON test USING GIN(hmarr _text_sml_ops );
CREATE INDEX

--设置smlar参数，查询至少需要2个切分的块一样
test=# set smlar.type = overlap;
SET
test=# set smlar.threshold = 2;
SET

--通过切分，使用数组相似性加持索引，收敛数据，查询不到1毫秒
test=# SELECT *,
test-#        smlar( hmarr, '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}')
test-#   FROM test
test-#  WHERE hmarr % '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}' --数据收敛，查询至少需要2个切分的块一样
test-#    AND LENGTH(REPLACE(BITXOR(BIT'1101101011001111001110111011111001000011100001011000000111010101', hmval)::TEXT, '0', '')) < 3; --海明距离小于3
 id |                              hmval                               |                                     hmarr                                     | smlar 
----+------------------------------------------------------------------+-------------------------------------------------------------------------------+-------
  8 | 0101101011001111001110111011111001000011100001011000000111010100 | {1_0101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010100} |     2
(1 row)

Time: 0.994 ms

--执行计划
test=# EXPLAIN ANALYZE
test-# SELECT *,
test-#        smlar( hmarr, '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}')
test-#   FROM test
test-#  WHERE hmarr % '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}' --数据收敛，查询至少需要2个切分的块一样
test-#    AND LENGTH(REPLACE(BITXOR(BIT'1101101011001111001110111011111001000011100001011000000111010101', hmval)::TEXT, '0', '')) < 3; --海明距离小于3
                                                                       QUERY PLAN                                                                       
--------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=49.17..3584.63 rows=667 width=138) (actual time=0.156..0.157 rows=1 loops=1)
   Recheck Cond: (hmarr % '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}'::text[])
   Filter: (length(replace((bitxor('1101101011001111001110111011111001000011100001011000000111010101'::"bit", hmval))::text, '0'::text, ''::text)) < 3)
   Heap Blocks: exact=1
   ->  Bitmap Index Scan on idx_hmarr_test  (cost=0.00..49.00 rows=2000 width=0) (actual time=0.130..0.130 rows=1 loops=1)
         Index Cond: (hmarr % '{1_1101101011001111,2_0011101110111110,3_0100001110000101,4_1000000111010101}'::text[])
 Planning Time: 0.120 ms
 Execution Time: 0.193 ms
(8 rows)

Time: 0.993 ms

复制

SimHash数据的切分，可以使用应用程序切分好存入数据库，也可以通过触发器自动切分。
PostgreSQL通过smlar插件，使用GIN索引，数据快速收敛，二重过滤，200万的数据量，检索时间控制在1毫秒以内，

参考：
https://github.com/jirutka/smlar
https://developer.aliyun.com/article/159575