2

几个月前我读到了BK-trees (Burkhard-Keller-Trees)，据说这是一种保存你想通过distance-metrics再次读出的东西的好方法。因此，在每种情况下，您都想通过相似性检索某些东西。

然而，这些 BK 树对我来说似乎并不快。当我尝试一个实现并进行一些输出时，只要我允许更长的距离，它就必须在树中四处走动（我用 levenshtein 验证了它并允许最多 6 次编辑）。

最快的实现（如果它只是关于速度的话）当然是将每个条目的距离存储在一个表中并直接查找它们，但这是太多的开销。

因此，我在标题中添加了现实主义。需要更多内存是可以的，但实现应该仍然是现实的和可用的（我对这些技术的了解不够多，无法说出什么是现实，但我想有一些边界）。

有没有比 BK-trees 更快的东西，或者 BK 真的是山顶（还）？

设想

我没有真正的用例，但场景如下：我有 1 个 mio 条目，它们彼此之间有一定的距离（由距离函数定义）。现在我得到一个条目并想知道：

  • 哪 5 个条目与给定条目最匹配
  • 哪些其他条目（与数量无关）低于或等于给定阈值

数据库无所谓。

我猜最终最好的算法会同时匹配两者吗？

4

1 回答 1

1

另一个基于树的最近邻度量是http://en.wikipedia.org/wiki/Cover_tree。它声称是实用的，并且http://www.cs.waikato.ac.nz/ml/weka/已经接受了它，所以我确实是这样。然而，最近的邻居似乎很难准确地做到，对于树木，或其他任何东西，因为有许多关于近似最近邻居的建议，我认为如果不难的话，这将是相当愚蠢的。我可以在http://people.csail.mit.edu/indyk/edit.ps看到一个编辑距离。

进行近似最近邻搜索的另一种方法是希望最近邻将具有恰好出现在查询字符串中的连续字符部分。然后对于数据库中的所有字符串，将它们切成所有连续的 k 长子字符串，并构建一个可以用于完全匹配的表。然后对于您的查询字符串，考虑所有 k 长的连续子字符串，对它们进行精确匹配，并计算您通过精确搜索 k 长子字符串找到的数据库中所有字符串的编辑距离。

于 2012-07-02T03:54:54.627 回答