问题标签 [bk-tree]

我目前正在实施BK-Tree来制作拼写检查器。我正在使用的字典非常大（数百万字），这就是为什么我根本无法承受任何低效率。但是，我知道我编写的查找函数（可以说是整个程序中最重要的部分）可以做得更好。我希望能找到一些同样的帮助。这是我写的查找：

我知道我不必要地多次运行循环，并且我们可以修剪搜索空间以加快查找速度。我只是不确定如何最好地做到这一点。

以下是我编写 BK-Tree 的尝试，对于150000它需要的 word 文件8 seconds

有什么办法可以减少这个时间。

以下是我的代码

以下是我想要做的。两个词W1和W2是朋友，如果Levenshtein distance这些词是 1。我也应该找到朋友的所有朋友。我试图用 Bk-Tree 做同样的事情。它适用于小型字典（字典每行仅包含一个单词），但对于较大的字典，它会严重减慢并且运行一个多小时仍然没有结果。

以下是我到目前为止的代码

关于提高速度的任何评论，或任何其他合适的数据结构。

假设以下是我的字典。

我试图找到答案social network是。aa5

我正在 Cython 中实现 BK-Tree。

一百万个项目，搜索时间太长了！大约 30 秒 :(

这是我的 Cython 代码：

距离.h

例子：

这棵树开始通过 256 位哈希搜索重复图像。

如何优化此findInTree功能？

我正在研究使用编辑距离算法在名称数据库中实现模糊搜索。

我发现了一种数据结构，据说可以通过分而治之的方法帮助加快这一进程——Burkhard-Keller Trees。问题是我找不到关于这种特定类型树的太多信息。

如果我用任意节点填充我的 BK-tree，我有多大可能遇到平衡问题？

如果我可能或可能对 BK-Trees 有平衡问题，有没有办法在这种树建成后平衡它？

正确平衡 BK-tree 的算法是什么样的？

到目前为止我的想法：

似乎子节点在距离上是不同的，所以我不能简单地旋转树中的给定节点而不重新校准它下面的整个树。但是，如果我能找到一个最佳的新根节点，这可能正是我应该做的。不过，我不确定如何找到最佳的新根节点。

我还将尝试一些方法，看看是否可以通过从一棵空树开始并插入预分布数据来获得一个相当平衡的树。

• 从按字母顺序排列的列表开始，然后从中间排队。（我不确定这是一个好主意，因为按字母排序与按编辑距离排序不同）。
• 完全洗牌的数据。（这在很大程度上依赖于运气来偶然选择一个“不那么糟糕”的根。它可能会严重失败并且可能在概率上保证是次优的）。
• 从列表中的任意单词开始，然后按照与该项目的编辑距离对其余项目进行排序。然后从中间排队。（我觉得这会很昂贵，并且仍然做得很差，因为它不会计算所有单词之间的度量空间连接 - 只是每个单词和一个参考单词）。
• 使用任何方法构建初始树，将其展平（基本上就像前序遍历），然后从中间排队等待新树。（这也会很昂贵，而且我认为它可能仍然表现不佳，因为它不会提前计算所有单词之间的度量空间连接，并且只会得到不同且仍然不均匀的分布）。
• 按名称频率排序，首先插入最流行的，抛弃平衡树的概念。（这可能是最有意义的，因为我的数据分布不均，而且我不会输入纯随机词）。

仅供参考，我目前并不担心名称同义词问题（Bill vs William）。我会分开处理，我认为完全不同的策略会适用。

阅读这篇关于 BK Trees 的帖子，我发现以下代码段有点令人困惑：

“假设我们有两个参数，查询，我们在搜索中使用的字符串，以及字符串可以与查询的最大距离并且仍然返回。假设我们采用任意字符串，测试并将其与查询进行比较. 称结果距离为 d。因为我们知道三角不等式成立，所以我们所有的结果必须最多有距离 d+n，至少距离测试有 dn。

我可以直观地看到，如果某些东西d与我正在搜索的单词相去甚远，并且我对n错误有容忍度，那么我至少需要d-n与我所在的词保持距离来“扭转”这些差异。同样，我最多可以有，d+n因为在“反转”差异之后，我可以引入更多差异。

我很困惑如何使用三角不等式来得到这个。如果我们让 d(test, query) = d 和 d(query, found) <= n 那么通过不等式：

我们怎样才能找到

I have seen many different implementations of BK Trees in many different languages, and literally none of them seem to include a way to remove nodes from the tree.

Even the original article where BK Trees were first introduced does not provide a meaningful insight about node deletion, as the authors merely suggest to mark the node to be deleted so that it is ignored:

The deletion of a key in Structures 1 [the BK Tree] and 2 follows a process similar to that above, with special consideration for the case in which the key to be deleted is the representative x° [root key]. In this case, the key cannot simply be deleted, as it is essential for the structure information. Instead an extra bit must be used for each key which denotes whether the key actually corresponds to a record or not. The search algorithm is modified correspondingly to ignore keys which do not correspond to records. This involves testing the extra bit in the Update procedure.

While it may be theoretically possible to properly delete a node in a BK Tree, is it possible to do so in linear/sublinear time?

BK树（Burkhard-Keller 树）与模糊字符串搜索（例如拼写检查、单词推荐）相关联。并且所有的 BK 树搜索算法都与这里解释的相同。例如，如果我搜索 "aeek"，目的是返回"seek" 和 "peek" 。

现在，我的问题是，我正在尝试使用这种模糊字符串搜索算法从给定的字典中搜索所有相似的项目。例如，给定一个单词“seek”，我想在字典中查找所有相似的单词，例如“peek”、“geek”、“seat”等。但是我发现每个人都使用的 BK 树搜索算法并不是为此而设计的。

看看我的样本测试结果here。我发现如果喂词顺序不同，字典会有所不同，因此搜索结果也会有所不同。

我想要的是，使用我上面的示例测试，给定四本 Python 书籍中的任何一本，一个SearchAll函数将始终返回这四本 Python 书籍，而不管字典的构建顺序或搜索完成的顺序。

但是，我尝试了很多方法，但都失败了（例如，这是其中之一）。现在我举手寻求帮助。一个伪代码或通用算法描述就可以了。谢谢。

我正在尝试使用 python 中的BK-tree数据结构来存储具有约 100 亿个条目（1e10）的语料库，以实现快速模糊搜索引擎。

一旦我将超过 1000 万 ( 1e7) 个值添加到单个 BK 树中，我开始看到查询性能显着下降。

我正在考虑将语料库存储到一千棵 BK 树的森林中并并行查询它们。

这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK-tree，我还能做些什么。

我使用pybktree.py并且我的查询旨在查找编辑距离内的所有条目d。

是否有一些架构或数据库可以让我存储这些树？

注意：我没有用完内存，而是树开始效率低下（大概每个节点都有太多子节点）。