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