代码之家 › 专栏 › 技术社区 › Dan Tao

在.NET中实现Trie的明智方法是什么?

trie implementation dictionary data-structures .net

8

Dan Tao · 技术社区 · 14 年前

我明白了 trie . 但在实现方面我有点困惑。

我能想到的最明显的方法 Trie 类型应该是有一个保持内部 Dictionary<char, Trie> . 事实上,我是这样写的,而且 ,但是。。。这看起来太过分了。我的印象是trie应该是轻量级的,并且有一个单独的 字典<char,Trie> 每个节点

有没有更合适的方法来实现我所缺少的这个结构?

更新 :好的!根据Jon和leppie提供的非常有用的信息,到目前为止我得出了以下结论:

特里亚 _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.
}

特里亚 首先,它的 _节点 成员是 null Add 创建 SingleNode 添加 按照上述步骤从那里开始。

有点减少“笨重”的 特里亚 (节点不再是完全成熟的对象,直到它们有足够数量的子对象)。然而,它也变得更加复杂。是不是太复杂了?我是不是走了一条复杂的道路去实现一些本该直截了当的事情?

4 回复 | 直到 14 年前

1

4

Jon Skeet 14 年前

有效地 工具 IDictionary<char, Trie> . 您可以编写自己的自定义实现,该实现根据其子节点的数量改变其内部结构:

char Trie
对于较小的数字,使用 List<Tuple<char, Trie>> LinkedList<Tuple<char,Trie>>
对于较大的数字,请使用 Dictionary<char, Trie>

(刚刚看到莱皮的答案,我相信这就是他所说的那种混合方法。)

2

3

Damien_The_Unbeliever 14 年前

如果您的字符来自一个有限的集合(例如,只有大写拉丁字母),那么您可以存储一个26个元素的数组,并且每次查找都是

Trie next = store[c-'A']

3

Andras Zoltan 14 年前

在我看来,将它实现为一个字典,并不是实现一个Trie,而是实现一个字典字典。

当我实现了一个trie时,我已经按照Damien\u the \u unsiverse建议的方法来实现了它(+1):

public class TrieNode
{
  TrieNode[] Children = new TrieNode[no_of_chars];
}

这在理想情况下要求您的trie只支持由 no_of_chars

当您需要添加/删除/检查节点是否存在时,您可以执行以下操作:

public TrieNode GetNode(char c)
{
  //mapping function - could be a lookup table, or simple arithmetic
  int index = GetIndex(c);
  //TODO: deal with the situation where 'c' is not supported by the map
  return Children[index];
}

ref TrieNode 这样节点就可以按需更新,并自动放入父节点的 Children 在正确的地方。

我接受了密码 from here

我想你会对TSTs感到惊喜;一旦我实现了一个TSTs,我就完全放弃了尝试。

4

2

leppie 14 年前

有几种方法,但使用单个链接列表可能是最简单和轻量级的。

我会做一些测试,看看每个节点有多少子节点。如果不多(比如说20或更少),链接列表方法应该比哈希表更快。您还可以根据子节点的数量来执行混合方法。