在.NET中实现Trie是一个合理的方法？ [英] What would be a sensible way to implement a Trie in .NET?

问题描述

我将 trie 背后的概念。但是在实现方面我有些困惑。

最明显的方式可以考虑构造一个 Trie 类型将是一个 Trie 维护内部字典< char，Trie> 。事实上，我实际上是以这种方式写的，而它的作品，但是...这似乎是过分的。我的印象是，一个特洛伊应该是轻量级的，并且为每个节点单独使用 Dictionary< char，Trie> 对我来说看起来并不轻巧

有没有更合适的方法来实现我失踪的这个结构？

---

更新：好的！基于Jon和leppie的非常有用的输入，这是迄今为止我已经提出的：

（1）我有 Trie 类型，其类型为 Trie.INodeCollection 的私人 _nodes 成员。 p>

（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; 
内部readonly Trie _trie; 
 
 public SingleNode（char key，Trie trie）
 {/*...*/} 
 
 // Add返回一个SmallNodeCollection。 
} 
 
 class SmallNodeCollection：INodeCollection 
 {
 const int MaximumSize = 8; //？ 
 
内部只读列表< KeyValuePair< char，Trie>> _节点
 
 public SmallNodeCollection（SingleNode node，char key，Trie trie）
 {/*...*/} 
 
 //添加添加到列表中并返回当前实例，直到MaximumSize，
 //之后它返回一个LargeNodeCollection。 
} 
 
 class LargeNodeCollection：INodeCollection 
 {
 private readonly Dictionary< char，Trie> _节点
 
 public LargeNodeCollection（SmallNodeCollection nodes，char key，Trie trie）
 {/*...*/} 
 
 //添加添加到字典并返回当前实例。 
} 
  

（4）当一个 Trie 首先构建，其 _nodes 成员是 null 。第一次调用添加创建一个 SingleNode ，后续调用添加从那里去，根据上述步骤。

这是否有意义？这样的感觉就像一种改进，它有点减少了一个 Trie 的蓬松（节点不再是完整的 Dictionary< char，Trie> 对象，直到他们有足够数量的孩子）。然而，它也变得更加复杂。太复杂了吗？我采取了一条复杂的路线来实现应该是直截了当的东西吗？

解决方案

嗯，你需要每个节点有东西 实现 IDictionary< char，Trie> 。您可以编写自己的自定义实现，根据它有多少个子节点来改变其内部结构：

• 对于单个子节点，只需使用一个 char 和 Trie


• 对于一小部分，使用列表< Tuple< char，Trie>> 或 LinkedList< Tuple< char，Trie>>


• 对于大量使用字典< char，Trie>

（刚刚看到leppie的答案，这是他谈论的那种混合方式，我相信。）

I get the concept behind a trie. But I get a little confused when it comes to implementation.

The most obvious way I could think to structure a Trie type would be to have a Trie maintain an internal Dictionary<char, Trie>. I have in fact written one this way, and it works, but... this seems like overkill. My impression is that a trie should be lightweight, and having a separate Dictionary<char, Trie> for every node does not seem very lightweight to me.

Is there a more appropriate way to implement this structure that I'm missing?

---

UPDATE: OK! Based on the very helpful input from Jon and leppie, this is what I've come up with so far:

(1) I have the Trie type, which has a private _nodes member of type Trie.INodeCollection.

(2) The Trie.INodeCollection interface has the following members:

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

(3) There are three implementations of this interface:

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) When a Trie is first constructed, its _nodes member is null. The first call to Add creates a SingleNode, and subsequent calls to Add go from there, according to the steps described above.

Does this make sense? This feels like an improvement in the sense that it somewhat reduces the "bulkiness" of a Trie (nodes are no longer full-blown Dictionary<char, Trie> objects until they have a sufficient number of children). However, it has also become significantly more complex. Is it too convoluted? Have I taken a complicated route to achieve something that should've been straightforward?

解决方案

Well, you need each node to have something which effectively implements IDictionary<char, Trie>. You could write your own custom implementation which varies its internal structure based on how many subnodes it has:

• For a single subnode, use just a char and a Trie
• For a small number, use a List<Tuple<char, Trie>> or a LinkedList<Tuple<char,Trie>>
• For a large number, use a Dictionary<char, Trie>

(Having just seen leppie's answer, this is the kind of hybrid approach he talks about, I believe.)

这篇关于在.NET中实现Trie是一个合理的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！