我们假设我只有一个键/值存储,并且我有一定距离(key1,key2)以某种方式定义(不知道它是否必须是一个度量,即如果三角不等式必须始终保持).
我想要的主要是一个搜索(键)功能,它返回我所有的项目与键到一定距离的搜索键.也许该距离限制是可配置的.也许这也只是一个懒惰的迭代器.也许也可以有一个计数限制,一个项目(关键字,值)在返回的集合中有一些概率P,其中P = 1 /距离(键,搜索键)等等(即,完美匹配肯定是在设置和关闭匹配中至少具有很高的概率).
一个例子应用是MusicBrainz中的指纹匹配.他们使用AcoustId指纹,并定义了this compare function.他们使用Postgresql GIN索引,我猜(尽管我还没有完全理解/读取acoustid-server代码)GIN Partial Match Algorithm,我完全理解这是我所要求的和它的工作原理.
对于文本,我到目前为止发现的是使用一些phonetic algorithm来简化基于他们的发音的单词.一个例子是here.这主要是将搜索空间分解成较小的空间.然而,这具有若干限制.它仍然是在较小的空间完美匹配.
但无论如何,我也在寻找一个更通用的解决方案,如果存在的话.
解决方法
这两个例子都没有实际做传统的最近邻搜索. AcoustID(我是作者)只是在寻找精确的匹配,但它搜索了非常多的散列,希望其中一些可以匹配.语音搜索示例使用Metaphone来将单词转换成其语音表示,并且也只是寻找精确匹配.
你会发现,如果你有大量的数据,使用巨大的哈希表的精确搜索是唯一可以实际做的.那么问题就是如何将你的模糊匹配转换成精确的搜索.
一个常见的方法是使用locality-sensitive hashing(LSH)的智能散列方法,但是您可以在两个示例中看到,有时您可以使用更简单的方法来消除这种情况.
Btw,您正在寻找专门的文本搜索,最简单的方法可以将您的输入分成N-grams并对其进行索引.根据您的距离功能的定义,这可能会给您正确的候选人匹配,而不需要太多的工作.
