如何平衡BK树,是否有必要？

Question

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

我发现了一个数据结构,据说可以通过分而治之的方法来帮助加快速度--Burkhard-Keller Trees.问题是我找不到关于这种特定类型树的非常多的信息.

如果我用任意节点填充我的BK树,我有多大可能有平衡问题？

如果我可能或可能与BK-Trees有平衡问题,有没有办法在构建之后平衡这样一棵树？

算法在适当平衡BK树时会是什么样子？

到目前为止我的想法:

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

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

• 从按字母顺序排序的列表开始,然后从中间排队.(我不确定这是一个好主意,因为按字母顺序排序与编辑距离的排序不同).
• 完全洗牌的数据.(这很大程度上依赖于运气来挑选一个"不那么糟糕"的根源.它可能会严重失败并且可能在概率上保证不是最佳的).
• 从列表中的任意单词开始,按照与该项目的编辑距离对其余项目进行排序.然后从中间排队.(我觉得这将是昂贵的,并且仍然做得很差,因为它不会计算所有单词之间的度量空间连接 - 只是每个单词和单个参考单词).
• 使用任何方法构建初始树,将其展平(基本上类似于预订遍历),并从中间排队以获得新树.(这也将是昂贵的,我认为它可能仍然很差,因为它不会提前计算所有单词之间的度量空间连接,并且将简单地获得不同且仍然不均匀的分布).
• 按名称频率排序,插入最受欢迎的第一个,并抛弃平衡树的概念.(这可能是最有意义的,因为我的数据不是均匀分布的,我不会有纯粹的随机单词进来).

仅供参考,我目前还不担心名称 - 同义词问题(Bill vs William).我将单独处理,我认为完全不同的策略将适用.

Answer 1

文章中有一个 lisp 示例： http: //cliki.net/bk-tree。关于不平衡树，我认为数据结构和方法似乎足够复杂，而且作者没有提到不平衡树。当您遇到不平衡树时，也许它不适合您？