在.NET中实现Trie的合理方法是什么？

Question

我得到了一个trie背后的概念.但是在实施方面我有点困惑.

我认为构建Trie类型最明显的方法是Trie维护内部Dictionary<char, Trie>.事实上,我已经用这种方式编写了一个,并且它可以工作,但是......这看起来有点过分了.我的印象是trie应该是轻量级的,并且每个节点都有一个单独的Dictionary<char, Trie>对我来说似乎不是很轻量级.

有没有更合适的方法来实现我缺少的这种结构？

---

更新:好的!基于Jon和leppie的非常有用的输入,这是我到目前为止所提出的:

(1)我有Trie类型,它有一个_nodes类型的私有成员Trie.INodeCollection.

(2)Trie.INodeCollection界面有以下成员:

interface INodeCollection
{
    bool TryGetNode(char key, out Trie node);
    INodeCollection Add(char key, Trie node);
    IEnumerable<Trie> GetNodes();
}

(3)此接口有三种实现方式:

class SingleNode : INodeCollection
{
    internal readonly char _key;
    internal readonly Trie _trie;

    public SingleNode(char key, Trie trie)
    { /*...*/ }

    // Add returns a SmallNodeCollection.
}

class SmallNodeCollection : INodeCollection
{
    const int MaximumSize = 8; // ?

    internal readonly List<KeyValuePair<char, Trie>> _nodes;

    public SmallNodeCollection(SingleNode node, char key, Trie trie)
    { /*...*/ }

    // Add adds to the list and returns the current instance until MaximumSize,
    // after which point it returns a LargeNodeCollection.
}

class LargeNodeCollection : INodeCollection
{
    private readonly Dictionary<char, Trie> _nodes;

    public LargeNodeCollection(SmallNodeCollection nodes, char key, Trie trie)
    { /*...*/ }

    // Add adds to the dictionary and returns the current instance.
}

(4)Trie首次构建a时,其_nodes成员为null.根据上述步骤,第一次调用Add创建一个SingleNode以及随后的调用Add.

这有意义吗？这感觉就像是一种改进,它在一定程度上减少了Trie(节点不再是完整的Dictionary<char, Trie>对象,直到它们有足够数量的子节点)的"庞大" .然而,它也变得更加复杂.它太复杂了吗？我是否采取了一条复杂的路线来实现应该直截了当的事情？

Answer 1

好吧，您需要每个节点都有一些可以有效实现IDictionary<char, Trie>. 您可以编写自己的自定义实现，该实现根据其具有的子节点数量来改变其内部结构：

• 对于单个子节点，仅使用 achar和 aTrie
• 对于较小的数字，请使用 aList<Tuple<char, Trie>>或 aLinkedList<Tuple<char,Trie>>
• 对于大量数据，请使用Dictionary<char, Trie>

（刚刚看到leppie的回答，我相信这就是他所说的混合方法。）