（1）什么是海明距離兩個碼字的對應比特取值不同的比特數(shù)稱為這兩個碼字的海明距離。在一個有效編碼集中,任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。舉例如下：10101和00110從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。

（2）海明距離的幾何意義n位的碼字可以用n維空間的超立方體的一個頂點來表示。兩個碼字之間的海明距離就是超立方體兩個頂點之間的一條邊，而且是這兩個頂點之間的最短距離。

（3）海明距離的應用場景用于編碼的檢錯和糾錯經過SimHash算法提取來的指紋（Simhash對長文本500字+比較適用，短文本可能偏差較大，具體需要根據(jù)實際場景測試），最后使用海明距離，求相似，在google的論文給出的數(shù)據(jù)中，64位的簽名，在海明距離為3的情況下，可認為兩篇文檔是相似的或者是重復的，當然這個值只是參考值，針對自己的應用可能又不同的測試取值

到這里相似度問題基本解決，但是按這個思路，在海量數(shù)據(jù)幾百億的數(shù)量下，效率問題還是沒有解決的，因為數(shù)據(jù)是不斷添加進來的，不可能每來一條數(shù)據(jù)，都要和全庫的數(shù)據(jù)做一次比較，按照這種思路，處理速度會越來越慢，線性增長。

針對海量數(shù)據(jù)的去重效率，我們可以將64位指紋，切分為4份16位的數(shù)據(jù)塊，根據(jù)抽屜原理在海明距離為3的情況，如果兩個文檔相似，那么它必有一個塊的數(shù)據(jù)是相等的。

那么數(shù)據(jù)庫是否支持這種高效率的檢索呢？

反正PostgreSQL是支持的，通過黑科技smlar插件。

一、需求

二、架構設計

在PostgreSQL中，從海量數(shù)據(jù)中，搜索海明距離小于N的數(shù)據(jù)，有多種設計手段。每種方法的能耗比都不一樣，讀者可以按需選擇。

1 暴力計算

1、單機多核并行計算，暴力掃描。采用阿里云RDS PostgreSQL 10提供的多核并行能力，暴力掃描。2、多機多核并行計算，暴力掃描。采用阿里云HybridDB for PostgreSQL提供的多級并行計算能力，暴力掃描。3、利用GPU、FPGA加速暴力運算。PostgreSQL提供了擴展接口，可以利用GPU，FPGA的能力對數(shù)據(jù)進行計算。4、利用CPU向量計算指令，暴力計算。PostgreSQL提供了擴展接口，可以利用CPU向量計算指令的能力加速計算。

2 索引

索引是高效的做法，例如PostgreSQL smlar插件，在阿里的導購平臺就有使用，用于實時導購文的海量相似度查詢。如果要讓smlar加速海明距離的搜索，需要采用更科學的方法，比如切片。直接使用位置，會有問題，因為smlar的第一道工序是塊級收斂，而海明碼是bit64的編碼，在一個數(shù)據(jù)塊中，有若干條記錄，任何位置都可能同時出現(xiàn)0和1，任何數(shù)據(jù)塊都包含0和1，因此無法完成第一道過濾。我們可以采用切片，減少這種可能性。例如每2個BIT一片，或者每4個BIT一片，或者更多。通常海明距離大于3的，就沒有什么相關性了。

三、DEMO與性能

1 暴力計算1、全掃，并行掃描創(chuàng)建測試表

四、技術點

1、阿里云RDS PostgreSQL smlar插件，使用GIN索引，塊級收斂，二重過濾。0.2毫秒的響應速度，1000萬數(shù)據(jù)中，檢索海明距離2以內的記錄。

2、阿里云RDS PostgreSQL 10，使用多核并行，暴力掃描，1000萬數(shù)據(jù)，檢索海明距離為N以內的數(shù)據(jù)，約450毫秒。

3、阿里云HybridDB for PostgreSQL，使用多機并行，橫向擴展計算能力，也可以做到暴力掃描。根據(jù)實際的節(jié)點數(shù)計算查詢效率。

五、云端產品

阿里云 RDS PostgreSQL：https://www.aliyun.com/product/rds/postgresql

阿里云 HybridDB for PostgreSQL：https://www.aliyun.com/product/gpdb

六、類似場景、案例

《電商內容去重\內容篩選應用(實時識別轉載\盜圖\侵權?) - 文本、圖片集、商品集、數(shù)組相似判定的優(yōu)化和索引技術》：https://github.com/digoal/blog/blob/master/201701/20170112_02.md

《基于 阿里云 RDS PostgreSQL 打造實時用戶畫像推薦系統(tǒng)》:https://github.com/digoal/blog/blob/master/201610/20161021_01.md

七、小結

采用阿里云RDS PostgreSQL的SMLAR插件，對千萬量級的simhash數(shù)據(jù)檢索相似文本，（更多數(shù)據(jù)量的測試后續(xù)提供，響應速度應該在毫秒級），相比沒有索引的情況，性能從23秒提升到了0.2毫秒。提升了11.48萬倍。

總結

以上是生活随笔為你收集整理的海量数据,海明距离高效检索(smlar)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。