20

我是那个领域的新手，我想知道最先进的技术是什么以及我可以在哪里阅读它。

假设我只有一个键/值存储，并且以某种方式定义了一些距离（key1，key2）（不确定它是否必须是度量，即三角形不等式是否必须始终保持）。

我想要的主要是一个 search(key) 函数，它返回所有带有键的项目到搜索键一定距离。也许距离限制是可配置的。也许这也只是一个惰性迭代器。也许也可以有一个计数限制，并且一个项目（键，值）在返回的集合中具有一定的概率 P，其中 P = 1/距离（键，搜索键）左右（即，完美匹配肯定是在集合和紧密匹配中至少有很高的概率）。

一个示例应用程序是MusicBrainz中的指纹匹配。他们使用AcoustId指纹并定义了这个比较函数。他们使用 PostgreSQL GIN 索引，我猜（虽然我还没有完全理解/阅读 acoustid-server 代码）GIN 部​​分匹配算法，但我还没有完全理解这是否是我所要求的以及它是如何工作的。

对于文本，到目前为止我发现的是使用一些语音算法来根据单词的发音来简化单词。一个例子是here。这主要是将搜索空间分解为更小的空间。然而，这有几个限制，例如它必须在较小的空间中仍然是完美的匹配。

但无论如何，我也在寻找更通用的解决方案，如果存在的话。

4

3 回答 3

15

没有（快速）通用解决方案，每个应用程序都需要不同的方法。

这两个示例实际上都没有进行传统的最近邻搜索。AcoustID（我是作者）只是在寻找精确匹配，但它会搜索大量哈希值，希望其中一些匹配。语音搜索示例使用变音位将单词转换为其语音表示，并且也只寻找完全匹配。

您会发现，如果您有大量数据，则使用巨大的哈希表进行精确搜索是您唯一可以实际做的事情。那么问题就变成了如何将模糊匹配转换为精确搜索。

一种常见的方法是将局部敏感散列(LSH) 与智能散列方法一起使用，但正如您在两个示例中看到的那样，有时您可以使用更简单的方法。

顺便说一句，您正在寻找专门用于文本搜索的最简单方法，您可以将输入拆分为N-gram并将其编入索引。根据您的距离函数的定义方式，这可能会为您提供正确的候选匹配，而无需太多工作。

于 2012-11-23T09:00:05.763 回答
8

我建议你看看 FLANN Fast Approximate Nearest Neighbors。大数据中的模糊搜索也称为近似最近邻。

该库为您提供不同的度量，例如 Euclidian、Hamming 和不同的聚类方法：例如 LSH 或 k-means。

搜索总是分两个阶段。首先，您向系统提供数据以训练算法，这可能会很耗时，具体取决于您的数据。我在不到一分钟的时间内成功地聚集了 1300 万个数据（使用 LSH）。

然后是搜索阶段，非常快。您可以指定最大距离和/或最大邻居数。

正如 Lukas 所说，没有好的通用解决方案，每个域都会有自己的技巧来提高速度或找到更好的方法来使用您使用的数据的内部属性。

Shazam 使用具有几何投影的特殊技术来快速找到您的歌曲。在计算机视觉中我们经常使用 BOW：Bag of words，它最初出现在文本检索中。

如果您可以将数据视为图形，那么还有其他方法可以使用谱图理论进行近似匹配。

让我们知道。

于 2012-11-23T09:23:17.653 回答
2

取决于您的键/值是什么样的，Levenshtein 算法（也称为 Edit-Distance）可以提供帮助。它计算修改一个字符串以获得另一个字符串所需的最少编辑操作数。

于 2014-04-02T16:29:25.280 回答