如何在大數據中進行模糊搜索

Question

我對這個領域很陌生，我主要想知道最新的技術以及我可以在哪裏讀到它。

讓我們假設我只有一個鍵/值存儲，並且我有一些距離（key1，key2）以某種方式定義（不確定它是否必須是度量標準，即三角不等式必須始終保持）。

我想要的主要是一個搜索（鍵）功能，它將所有項目返回到與搜索鍵相距一定距離的鍵。也許這個距離限制是可配置的。也許這也只是一個懶惰的迭代器。也許還可以有一個計數限制和一個項目（鍵，值）在返回的集合中有一定的概率P，其中P = 1 /距離（鍵，搜索鍵）左右（即完美匹配當然是在設定和關閉匹配中至少有很高的概率）。

---

一個示例應用是MusicBrainz中的指紋匹配。他們使用AcoustId指紋並定義了this compare function。他們使用PostgreSQL的GIN索引，我猜（儘管我還沒有完全理解/讀取acoustid-server代碼）GIN Partial Match Algorithm，但我還沒有完全理解這是我所要求的以及它是如何工作的。

---

對於文本，什麼到目前爲止，我所發現的是使用一些phonetic algorithm簡化基於其發音的詞語。一個例子是here。這主要是爲了將搜索空間分解到更小的空間。然而，這具有幾個限制，例如它仍然是小空間的完美搭配。

但無論如何，我也在尋找更通用的解決方案，如果存在的話。

Answer 1

沒有（快速）通用解決方案，每個應用程序都需要不同的方法。

這兩個例子都沒有實際做傳統的最近鄰居搜索。 AcoustID（我是作者）只是在尋找確切的匹配，但它搜索的哈希數量非常多，希望其中的一些匹配。語音搜索示例使用metaphone將單詞轉換爲他們的語音表示，並且也只查找完全匹配。

你會發現，如果你有很多數據，使用巨大的散列表進行精確搜索是你實際可以做的唯一的事情。那麼問題就變成了如何將模糊匹配轉換爲精確搜索。

通常的做法是使用locality-sensitive hashing（LSH）和智能哈希方法，但正如您在兩個示例中看到的那樣，有時您可以使用更簡單的方法逃脫。

順便說一句，你正在尋找專門的文本搜索，最簡單的方法，你可以做到這一點拆分輸入N-grams並索引這些。根據你的距離函數的定義，這可能會給你正確的候選人比賽，而不需要太多的工作。

Answer 2

我建議你看看FLANN Fast Approximate Nearest Neighbors。大數據中的模糊搜索也稱爲近似最近鄰居。

該庫爲您提供了不同的度量，例如Euclidian，Hamming和不同的聚類方法：例如LSH或k-means。

搜索總是分兩個階段進行。首先給系統提供數據以訓練算法，這可能會耗費時間，具體取決於您的數據。 雖然（使用LSH），但我在不到一分鐘的時間內成功地羣集了13百萬個數據。

然後進入搜索階段，這是非常快的。您可以指定最大距離和/或最大鄰居數量。

正如Lukas所說，沒有一個好的通用解決方案，每個域都有它的技巧來使它更快，或者使用你使用的數據的內在屬性找到更好的方法。

Shazam使用特殊的技術與幾何投影來快速找到您的歌曲。在計算機視覺中，我們經常使用BOW：Bag，它最初出現在文本檢索中。

如果你可以看到你的數據爲一個圖表，還有其他一些近似匹配方法，例如使用光譜圖理論。

讓我們知道。

Answer 3

取決於您的鍵/值是什麼樣，Levenshtein算法（也稱爲編輯距離）可以提供幫助。它計算修改一個字符串以獲取另一個字符串所需的編輯操作的最少數量。

• http://en.wikipedia.org/wiki/Levenshtein_distance
• http://www.levenshtein.net/