postgresql , rum , tsvector , array , smlar , 相似度 , 内容去重 , 内容筛选 , 转载 , 盗图 , 侵权 , 内容过滤
同一个热点事件，可能有很多的媒体报道。
同一篇好的文章，可能被多人转载。
一个商品、或者同一堆商品，可能会被诸多广告平台、导购平台推送。
导购网站、新闻媒体、技术论坛、搜索引擎，充斥着各种李逵、李鬼。相似甚至内容完全相同的文章或者图片集等。
不涉及利益时，这些都不是大问题。一旦涉及利益，这些问题可能会困扰利益方。
比如
1. 导购网站，接收来自社会各界的推荐文章，推荐文章中会有诸多的商品，以及商品的体验、介绍性的内容。
为了避免内容相似或者相同的文章，通常需要请人审核推荐的内容，如果发现大部分商品与已发表的其他导购文章内容类似，可能被拒绝发表。
不过人为审核存在严重瓶颈，如果是机器审核，目前比较多见的可能是异步的批量审核（因为每接收一篇新的文章，都要和所有历史文章进行比较）。
2. 新闻媒体，同一个事件，避免多次被报道或者爆料。
还有好多类似的社会需求。
前面提到，每接收一篇新的文章，都要和所有历史文章进行比较，那么有什么技术能做到实时的内容相似度审核呢？
到postgresql的剑冢挑一柄绝世好剑吧。
1. 文本相似
通常需要算出每篇文章的关键词（比如平均每篇文章20个关键词），然后算出新提交文章的关键词（假设有若干个）
然后去根据比对新建文章关键词，与历史文章关键词，找到相似的文章。
<a href="https://github.com/digoal/blog/blob/master/201701/20170116_02.md">《postgresql结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 1 文本(关键词)分析理论基础 - tf(term frequency 词频)/idf(inverse document frequency 逆向文本频率)》</a>
<a href="https://github.com/digoal/blog/blob/master/201701/20170116_04.md">《postgresql结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 3 rum, smlar应用场景分析》</a>
<a href="https://github.com/digoal/blog/blob/master/201701/20170116_03.md">《postgresql结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 2 smlar插件详解》</a>
<a href="https://github.com/digoal/blog/blob/master/201608/20160817_01.md">《postgresql 文本数据分析实践之 - 相似度分析》</a>
优化的海量文本相似分析算法，例如
将关键词哈希（生成一个64位bit串），对bit位置为1的，关键词都有一个tfidf数值，对bit位为0的，设置为负tfidf, bit位为1的设置为正tfidf。一个关键词会生成64个正负值。
将所有关键词生成的64个正负值，每一个对应位置，例如，第一个bit，对应所有关键词的64个正负值中的第一个正负tfidf值。以此类推，最后会生成64个新的正负值。
对于新的64个正负值，大于0的改成1，小于等于0的改成0，那么就变成了64个0、1的bit串。
这个bit串就是根据这篇文章关键词算出来的指纹。
每篇文章都有这样的指纹，通过对比两篇文章的指纹（bit串），有多少个bit位置是不一样的，来判断相似性。
详见，海量数据相似度计算之simhash和海明距离
<a href="http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html">http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html</a>
2. 对于图像去重，则可以利用这篇文章的技术
<a href="https://github.com/digoal/blog/blob/master/201611/20161126_01.md">《postgresql 在视频、图片去重，图像搜索业务中的应用》</a>
<a href="https://github.com/digoal/blog/blob/master/201612/20161222_02.md">《从相似度算法谈起 - effective similarity search in postgresql》</a>
<a href="https://github.com/digoal/blog/blob/master/201607/20160726_01.md">《弱水三千,只取一瓢,当图像搜索遇见postgresql(haar wavelet)》</a>
3. 对于模糊查询、正则匹配、全文检索等，则可以参考这几篇文档
<a href="https://github.com/digoal/blog/blob/master/201612/20161231_01.md">《从难缠的模糊查询聊开 - postgresql独门绝招之一 gin , gist , sp-gist , rum 索引原理与技术背景》</a>
<a href="https://github.com/digoal/blog/blob/master/201610/20161019_01.md">《postgresql 全文检索加速 快到没有朋友 - rum索引接口(潘多拉魔盒)》</a>
4. 数组、图片集、关键词集合相似，可以参考这篇文档，也是本文要讲的重点
<a href="http://railsware.com/blog/2012/05/10/effective-similarity-search-in-postgresql/">http://railsware.com/blog/2012/05/10/effective-similarity-search-in-postgresql/</a>
下面来讲一个内容去重的案例。
某导购平台，平均每篇文章可能会有几十个被推荐的商品以及一些商品介绍内容。
例如你可以打开一个导购平台体验一下，一篇推荐玩具的导购文章，里面可能涉及几十个玩具类的商品。
<a href="http://post.smzdm.com/p/525280/">http://post.smzdm.com/p/525280/</a>
在历史推荐中，可能会堆积几千万甚至上亿的导购文章。
每篇文章可能有几十个被推荐的商品，整个被推荐的商品库可能有千万级。
而且一定会存在被多篇文章推荐的热点商品。
比如畅销品，或者某些商品的卖家通过推荐费来提高被推荐的频度等。我们假设在整个导购文章库中，存在1/5的热点商品。
下面将使用postgresql smlar插件，实现对导购文章的实时去重。
smlar插件的介绍请参考
<a href="http://www.pgcon.org/2012/schedule/attachments/252_smlar-2012.pdf">http://www.pgcon.org/2012/schedule/attachments/252_smlar-2012.pdf</a>
根据以上模型，构建测试库，一共6000万导购文章，设计1000万个商品，每篇导购文章11 - 50个商品，其中商品id 1-50万 的为热点商品被1000万篇文章推荐过。
1. 创建smlar插件，
2. 创建测试表
3. 插入5000万记录，要求如下
int8 取值范围1~1000万 ， 即历史上被推荐的商品有1000万个。
int8[] 数组长度 11 ~ 50 ， 即每篇导购文章，包含11到50个商品。
均匀分布。
插入测试数据的函数如下，调用一次插入40条记录。
使用pgbench调用以上函数，将生成5000万测试数据
4. 生成1000万热点商品的推荐数据
假设商品id范围在 1 ~ 50万 的为热点商品，被1000万篇文章推荐过。
修改以上函数
使用pgbench调用以上函数，生成1000万测试数据
总共生成了6000万推荐文章的数据(约18亿数组元素集)。
5. 创建gin索引，使用smlar提供的ops
6. 相似计算算法
smlar插件支持几种默认算法，同时支持自定义公式。
注意，全部指数组元素去重后的结果
n.i : 相交的元素个数(被比较的两数组会先去重)
n.a : 第一个数组的元素个数(去重后)
n.b : 第二个数组的元素个数(去重后)
默认算法如下
6.1 cosine
n.i / sqrt(n.a * n.b)
6.2 overlap
n.i
6.3 tfidf
较复杂，参考
设置方法
自定义公式以及用法
7. 测试性能
对于导购网站，一篇导购文章推荐了10个商品，结果其中有9个商品和另一篇导购文章中一样。这种判定为重复文章，审核不通过。
当然你可以设置为9，或者8或者更低，看运营的心情?
而对于一篇文章，10个商品，如果这10个商品是分别出现在已有导购文章的10篇文档各一个，那么可以通过审核。
以上例子指的是通过overlap的公式来判定相似性。
找出一部分已有记录，根据这些记录造一些进行判断
7.1 通过函数，简化sql
7.2 普通商品40个
高相似，4毫秒响应
低相似，4毫秒响应
不存在，4毫秒响应
7.3 热点商品10个,普通商品30个
高相似，6毫秒
低相似，6毫秒
不存在，6毫秒
7.4 热点商品40个
高相似，15毫秒
低相似，15毫秒
不存在，15毫秒
7.5 压测
普通商品35个，热点商品5个，overlap=35，压测
使用pgbench压测
压测结果，约9400 tps，cpu耗光。
8. 其他测试query
1. 创建优化，创建gin索引时，设置较大的maintenance_work_mem可以加快创建索引的速度
2. update, insert, delete优化
由于gin是元素展开索引，当插入一个条新数组，或者更新、删除某些记录时，可能会涉及多个gin条目的变更。因此gin索引的变更非常频繁。所以postgresql设计了一个pending list，允许异步的将pending list的信息更新到gin索引中。从而减少gin的频繁更新。提升dml效率。
<a href="https://www.postgresql.org/docs/9.6/static/gin-tips.html">https://www.postgresql.org/docs/9.6/static/gin-tips.html</a>
<a href="https://www.postgresql.org/docs/9.6/static/sql-createindex.html">https://www.postgresql.org/docs/9.6/static/sql-createindex.html</a>
3. 查询优化
由于pending list的存在，可能会影响一定的查询效率，因为pending list不是树结构的。
所以在dml和查询之间建议权衡利弊。
或者发现慢之后，执行一下vacuum，将pengding list合并到tree中。
<a href="https://github.com/digoal/blog/blob/master/201702/20170221_01.md">《postgresql gin 单列聚集索引 应用》</a>
<a href="https://github.com/digoal/blog/blob/master/201702/20170204_01.md">《postgresql gin索引实现原理》</a>
<a href="https://github.com/digoal/blog/blob/master/201702/20170203_01.md">《postgresql gin multi-key search 优化》</a>
<a href="https://github.com/digoal/blog/blob/master/201702/20170205_01.md">《宝剑赠英雄 - gin任意组合字段等效查询, 探探postgresql多列展开式b树》</a>
gin索引会构建一颗 "以商品id为key" 的b树，value则是由 "堆表行号ctid" 组成的 posting list或者posting tree。
在来了一篇新的导购文章时，根据导购文章涉及的商品ids，首先在树中进行搜索，每命中一个key则cnt++1，当cnt小于设置的smlar.threshold阈值时，说明不满足条件，直接返回空结果，不需要进入下一层搜索。
当大于等于设置的阈值时，进行下一层的搜索(即gin索引支持的通用bitmap scan搜索，分为bitmap index scan和bitmap heap scan两个阶段)
1. bitmap index scan阶段，从key对应的posting list或posting tree，取出ctid对应的heap page id(即堆表的页号)，比如 (1,1), (1,2), (1,5), (1000,32) 得到1, 1000。
1和1000分别对应一个cnt，计数。 例如 cnt[1]=1, cnt[1000]=1 。
遍历 "导购文章涉及的商品ids" 对应的所有key，heap page id对应的cnt[heap_page_id]++1
比如 ( 导购文章商品ids={1,3,101,198,798,10009} ) 最终得到 cnt[1]=2, cnt[35]=1, cnt[49]=3, cnt[101]=4, cnt[109]=2, cnt[1000]=2。
接下来，根据smlar.threshold，排除不符合条件的heap page id，比如smlar.threshold=3, 则heap page id=49,101 符合条件。
接下来，生成bitmap(每个bit位对应堆表的一页，所以bitmap的长度取决于表有多少页)，根据前面取得的满足条件的heap page id ： 49, 101， 将对应bit位设置为1，其他位为0。
然后进入bitmap heap scan阶段，
2. bitmap heap scan阶段，到bitmap中bit位=1的对应heap page（即49, 101）取出所有记录，然后根据sql提供的索引查询条件 用cpu去recheck。
1. 调整为overlap模式
2. 设置阈值=1，生成heap page对应的bitmap前，会使用阈值过滤不满足条件的heap page id。
2.1 查看heap blocks: exact=4011，说明满足条件的块有4011个。
2.2 看我前面的解释，后面的就很好理解了。
2.3 继续举例
2.4 当threshold=4时，在bitmap index scan阶段，组成的bitmap没有任何一个bit=1，所以bitmap heap scan阶段，扫描的page数=0。
如果你想查看行号或者heap page id的话，很简单
<a href="https://github.com/digoal/blog/blob/master/201702/20170221_02.md">《postgresql bitmapand, bitmapor, bitmap index scan, bitmap heap scan》</a>
至于效率，前面已经验证了。6000万（其中5000万普通，1000万热点），40个商品（其中5个热点，35个普通）的相似度实时判定，tps将近1万。
下次再细聊smlar的gin和gist实现。
1. 相似度
2. wavelet
3. rum
<a href="https://github.com/postgrespro/rum">https://github.com/postgrespro/rum</a>
距离(相似度)算法参考
src/rum_ts_utils.c
4. 数组(文本)相似度算法
5. knn with tf-idf based framework for text categorization
<a href="http://www.sciencedirect.com/science/article/pii/s1877705814003750">http://www.sciencedirect.com/science/article/pii/s1877705814003750</a>
6. 数据挖掘-基于贝叶斯算法及knn算法的newsgroup18828文本分类器的java实现（上）
<a href="http://blog.csdn.net/yangliuy/article/details/7400984">http://blog.csdn.net/yangliuy/article/details/7400984</a>
7. tf-idf与余弦相似性的应用（一）：自动提取关键词
<a href="http://www.ruanyifeng.com/blog/2013/03/tf-idf.html">http://www.ruanyifeng.com/blog/2013/03/tf-idf.html</a>
8. tf-idf与余弦相似性的应用（二）：找出相似文章
<a href="http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html">http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html</a>
9. tf-idf
<a href="http://baike.baidu.com/view/1228847.htm">http://baike.baidu.com/view/1228847.htm</a>
10. hll
<a href="https://research.neustar.biz/2013/02/04/open-source-release-postgresql-hll/">https://research.neustar.biz/2013/02/04/open-source-release-postgresql-hll/</a>
<a href="http://docs.pipelinedb.com/probabilistic.html#hyperloglog">http://docs.pipelinedb.com/probabilistic.html#hyperloglog</a>
<a href="https://www.citusdata.com/blog/2016/10/12/count-performance/">https://www.citusdata.com/blog/2016/10/12/count-performance/</a>
11. excluding 约束
<a href="https://www.postgresql.org/docs/9.6/static/sql-createtable.html">https://www.postgresql.org/docs/9.6/static/sql-createtable.html</a>
12. pg_trgm
<a href="https://www.postgresql.org/docs/9.6/static/pgtrgm.html">https://www.postgresql.org/docs/9.6/static/pgtrgm.html</a>
13. 中文分词
<a href="https://github.com/jaiminpan/pg_jieba.git">https://github.com/jaiminpan/pg_jieba.git</a>
14. 海量数据相似度计算之simhash和海明距离