标签: bk-tree

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

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

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

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

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

到目前为止我的想法:

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

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

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

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

我已经在许多 不同的 语言中看到了 BK 树的许多不同实现，实际上它们似乎都没有包含从树中删除节点的方法。

即使最初介绍 BK 树的原始文章也没有提供关于节点删除的有意义的见解，因为作者只是建议标记要删除的节点，以便将其忽略：

删除结构1[BK树]和2中的键遵循与上述类似的过程，特别考虑要删除的键是代表x°[根键]的情况。在这种情况下，不能简单地删除密钥，因为它对于结构信息是必不可少的。相反，每个键必须使用一个额外的位来表示该键是否实际上对应于一条记录。相应地修改搜索算法以忽略与记录不对应的键。这涉及测试更新过程中的额外位。

虽然理论上可以正确删除 BK 树中的节点，但是否可以在线性/亚线性时间内这样做？

我正在尝试使用python 中的BK 树数据结构来存储一个包含约 100 亿个条目 ( 1e10)的语料库，以实现快速模糊搜索引擎。

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

我想将语料库存储到一千个 BK 树的森林中并并行查询它们。

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

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

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

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

以下是我想要做的.两个词W1和W2是朋友,如果Levenshtein distance这些话是:1.我应该找朋友的所有朋友也.我试图用Bk-Tree做同样的事情.它适用于小型字典(字典每行只包含一个单词)但是对于较大的字典,它会大幅减速并且运行一个多小时仍然没有结果.

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

#include <string>
#include <vector>
#include <queue>
#include <fstream>  
#include <iostream>  
#include <algorithm>

class BkTree {
    public:
        BkTree();
        ~BkTree();
        void insert(std::string m_item);
        void get_friends(std::string center, std::deque<std::string>& friends);
    private:
        size_t EditDistance( const std::string &s, const std::string &t );
        struct Node {
            std::string m_item;
            size_t m_distToParent;
            Node *m_firstChild;
            Node *m_nextSibling;
            Node(std::string x, size_t dist);        
            bool visited;
            ~Node();
        };
        Node *m_root;
        int   m_size;
    protected:
};

BkTree::BkTree() {
    m_root = NULL; 
    m_size = 0;
}

BkTree::~BkTree() …