c#版字典树测试

Question

今天下午闲着没事，用c#写了个字典树,结果没有想到中间出了很多问题...
因为内容有点多，专门写到博客了...
字典树连接希望大家觉得值得讨论的，仔细看下。帮我解惑！谢谢了，如果分不够,我在开帖散分！

Answer 1

节省空间，或计数应该只是字典树比较偏门的应用（其实用后缀树可能效果更好），Trie树（加上类似于KMP的适配回溯，就叫Trie图了）主要功能还是在于多模式匹配下，能够提供线性的效率，可以用于搜索分词。

Answer 2

加上类似于KMP的适配回溯，就叫Trie图了 =>
加上类似于KMP的失配回溯，就叫Trie图了

Answer 3

占用内存的问题可能是LZ算的有点小问题！const
private const int alignConst = 3;  
private const int charPtrAlignConst = 1;  
申请3*10^7 string[]应该不会出问题，反正我这里可以。22b的问题应该不算大问题，我以前写的Trie用的是Dictionary，也没仔细用平摊算过，估计单节点占用更大，用List也许稍好一点点，不过Trie本就不是用来省内存的。

Answer 4

唉，最基本的数据结构概念，怎么来重复呢？随便搜个（第一个）结果吧：http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx对于稍微大型一些的应用，它不会把数据放在树内，而只会放数据的引用（例如只是数据在磁盘块上的位置信息）。

Answer 5

呵呵，建议推广，有实例不呀？发到www.shilidata.com上啦，可以拿积分哦。

Answer 6

LZ一下子给了这么多分，受之有愧，给LZ提一些小建议吧！TrieNode 最好加上\\失配时回溯到的节点
public TrieNode FailNode { get; set; }\\是否为叶子节点
public bool IsLeaf { get; set; }附一段用BFS建立失配节点的程序，具体用途可以参看AC自动机其他代码就不献丑了，LZ写的挺好的。        public void BuildFailNode()
        {
            Queue<TrieNode> bfsQueue = new Queue<TrieNode>();
            bfsQueue.Enqueue(Root);
            TrieNode node;            while (bfsQueue.Count > 0)
            {
                node = bfsQueue.Dequeue();                if (!node.ParentNode.Equals(Root) && node.ParentNode.FailNode.ChildNodes.ContainsKey(node.Key))
                    node.FailNode = node.ParentNode.FailNode.ChildNodes[node.Key];
                else
                    node.FailNode = Root;                foreach (TrieNode child in node.ChildNodes.Values)
                    bfsQueue.Enqueue(child);
            }
        }

Answer 7

http://www.cnblogs.com/dullwolf/archive/2011/04/15/2017479.html我也写了一个，是利用的哈希来存储子节点。
期望是哈希比链表查找快一点。
你看看
我这个主要是实现Like搜索（前缀模糊搜索），最终结果只比C#本身的IndexOf快了一两百毫秒，却消耗了大量内存。纠结中。