Postgresql
postgres中的快速漢明距離查詢
我有一個包含圖像感知散列的大型數據庫（16M 行）。
我希望能夠在合理的時間範圍內通過漢明距離搜尋行。
目前，據我正確理解這個問題，我認為這裡最好的選擇是實現BK-Tree的自定義 SP-GiST 實現，但這似乎需要做很多工作，而且我對實際操作仍然很模糊正確實施自定義索引的詳細資訊。計算漢明距離很容易處理，不過我確實知道 C。
基本上，這裡的適當方法是什麼？我需要能夠在雜湊的某個編輯距離內查詢匹配項。據我了解，具有相等長度的字元串的 Levenshtein 距離在功能上是漢明距離，因此至少有一些現有的支持我想要的東西，儘管沒有明確的方法可以從中創建索引（請記住，我正在查詢的值變化。我無法預先計算與固定值的距離，因為這只對那個值有用）。
雜湊目前儲存為包含雜湊的二進制 ASCII 編碼的 64 字元字元串（例如“10010101…”），但我可以很容易地將它們轉換為 int64。真正的問題是我需要能夠相對快速地查詢。
似乎可以通過 實現我想要的東西
pg_trgm，但我有點不清楚三元組匹配機制是如何工作的（特別是，它返回的相似性度量實際上代表什麼？看起來有點像編輯距離）。插入性能並不重要（計算每一行的雜湊值非常昂貴），所以我主要關心搜尋。
摩爾答案！
好的，我終於花時間編寫了一個自定義 PostgreSQL 索引擴展。我使用了SP-GiST 界面。
這是相當具有挑戰性的，主要是因為 Posgres很大。
無論如何，像往常一樣，它在github 上。
在性能方面，它目前比我對這個問題的另一個答案中的純記憶體實現慢約 2-3 倍，但使用起來更方便我會很高興地吃掉性能損失（實際上，它是 ~50 ms/query - 150 ms/query，仍然很小）。