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和海明距離