Alb*_*ert 15 database indexing search fuzzy-search
我是那个地区的新手,我很想知道最先进的是什么以及我可以在哪里阅读它.
让我们假设我只有一个键/值存储,并且我以某种方式定义了一些距离(key1,key2)(不确定它是否必须是度量,即三角不等式是否必须始终保持).
我想要的主要是一个搜索(键)功能,它返回所有带有键的项目,直到搜索键一定距离.也许距离限制是可配置的.也许这也只是一个懒惰的迭代器.也许还有一个计数限制,一个项目(键,值)在返回集合中有一些概率P,其中P = 1 /距离(键,搜索键)左右(即,完美匹配肯定会是在集合和近似匹配中至少具有高概率).
一个示例应用是MusicBrainz中的指纹匹配.他们使用AcoustId指纹并定义了这个比较功能.他们使用PostgreSQL GIN索引,我猜(虽然我还没有完全理解/读取acoustid服务器代码)GIN部分匹配算法,但我还没有完全理解这是我要求的以及它是如何工作的.
对于文本,到目前为止我发现的是使用一些语音算法来根据发音简化单词.一个例子是在这里.这主要是为了将搜索空间缩小到更小的空间.然而,这有一些限制,例如它在较小的空间中仍然必须是完美的匹配.
但无论如何,我也在寻找更通用的解决方案,如果存在的话.
Luk*_*ský 11
没有(快速)通用解决方案,每个应用程序都需要不同的方法.
这两个例子都没有实际进行传统的最近邻搜索.AcoustID(我是作者)只是寻找完全匹配,但它搜索了大量的哈希值,希望它们中的一些匹配.语音搜索示例使用metaphone将单词转换为其语音表示,并且仅查找完全匹配.
您会发现,如果您拥有大量数据,那么使用大型哈希表的精确搜索是您唯一可以实际执行的操作.那么问题就变成了如何将模糊匹配转换为精确搜索.
一种常见的方法是使用局部敏感散列(LSH)和智能散列方法,但正如您在两个示例中所看到的,有时您可以使用更简单的方法.
顺便说一下,你正在寻找专门用于文本搜索的方法,最简单的方法就是将你的输入分成N-gram并将其编入索引.根据您的距离函数的定义方式,这可能会为您提供正确的候选匹配而无需太多工作.
我建议您看看FLANN 快速近似最近邻居。大数据中的模糊搜索也称为近似最近邻居。
该库为您提供不同的度量标准，例如欧几里得，汉明和不同的聚类方法：例如LSH或k-means。
搜索始终分为两个阶段。首先，向系统提供数据以训练算法，这可能会浪费时间，具体取决于您的数据。我使用LSH在不到一分钟的时间内成功地将1300万个数据集群了。
然后是搜索阶段，这是非常快的。您可以指定最大距离和/或最大邻居数。
正如Lukas所说，没有一个好的通用解决方案，每个域都有其诀窍，可以利用您使用的数据的内部属性使其更快或更找到更好的方法。
Shazam使用具有几何投影的特殊技术来快速找到您的歌曲。在计算机视觉中，我们经常使用BOW：单词袋，最初出现在文本检索中。
如果您可以将数据显示为图形，则可以使用其他方法，例如使用光谱图理论进行近似匹配。
让我们知道