我正在研究使用编辑距离算法在名称数据库中实现模糊搜索。
我发现了一种数据结构，据说可以通过分而治之的方法帮助加快这一进程——Burkhard-Keller Trees。问题是我找不到关于这种特定类型树的太多信息。
如果我用任意节点填充我的 BK-tree，我有多大可能遇到平衡问题？
如果我可能或可能对 BK-Trees 有平衡问题，有没有办法在这种树建成后平衡它？
正确平衡 BK-tree 的算法是什么样的？
到目前为止我的想法：
似乎子节点在距离上是不同的，所以我不能简单地旋转树中的给定节点而不重新校准它下面的整个树。但是，如果我能找到一个最佳的新根节点，这可能正是我应该做的。不过，我不确定如何找到最佳的新根节点。
我还将尝试一些方法，看看是否可以通过从一棵空树开始并插入预分布数据来获得一个相当平衡的树。
- 从按字母顺序排列的列表开始，然后从中间排队。（我不确定这是一个好主意，因为按字母排序与按编辑距离排序不同）。
- 完全洗牌的数据。（这在很大程度上依赖于运气来偶然选择一个“不那么糟糕”的根。它可能会严重失败并且可能在概率上保证是次优的）。
- 从列表中的任意单词开始，然后按照与该项目的编辑距离对其余项目进行排序。然后从中间排队。（我觉得这会很昂贵，并且仍然做得很差，因为它不会计算所有单词之间的度量空间连接 - 只是每个单词和一个参考单词）。
- 使用任何方法构建初始树，将其展平（基本上就像前序遍历），然后从中间排队等待新树。（这也会很昂贵，而且我认为它可能仍然表现不佳，因为它不会提前计算所有单词之间的度量空间连接，并且只会得到不同且仍然不均匀的分布）。
- 按名称频率排序，首先插入最流行的，抛弃平衡树的概念。（这可能是最有意义的，因为我的数据分布不均，而且我不会输入纯随机词）。
仅供参考，我目前并不担心名称同义词问题（Bill vs William）。我会分开处理，我认为完全不同的策略会适用。