C#TrieTree介绍及实现方法.docx

C#TrieTree介绍及实现方法

TrieTree简单的说是一种多叉树，每个节点保存一个字符，这么做的好处是当我们要做NGram比对时，只需要直接从树的根节点开始沿着某个树叉遍历下去，就能完成比对。下面小编为大家整理了C#TrieTree介绍及实现方法，希望能帮到大家！在自然语言处理（NLP）研究中，NGram是最基本但也是最有用的一种比对方式，这里的N是需要比对的字符串的长度，而今天我介绍的TrieTree，正是和NGram密切相关的一种数据结构，有人称之为字典树。TrieTree简单的说是一种多叉树，每个节点保存一个字符，这么做的好处是当我们要做NGram比对时，只需要直接从树的根节点开始沿着某个树叉遍历下去，就能完成比对；如果没找到，停止本次遍历。这话讲得有些抽象，我们来看一个实际的例子。假设我们现在词库里面有以下一些词：上海市上海滩上海人上海公司北京北斗星杨柳杨浦区如图所示：挂在根节点上的字有上、北、杨，如果我们现在对“上海市杨浦区”这个词做3gram就有上海市、海市杨、市杨浦、杨浦区，现在我们要知道哪些词是能够被这个字典识别的，通常我们可以用NGram来做分词。有了这颗树，我们只需要依次取每个字符，从根开始进行比对，比如上海市，我们能够匹配上->海->市，这个路径，所以匹配；比如海市杨，由于没有“海”字挂在根节点上，所以停止；市杨浦也无法匹配；最终匹配杨浦区，得到杨->浦->区这个路径，匹配。最终我们可以把“上海市杨浦区”切分为上海市|杨浦区。尽管TrieTree要比普通字符串数组节省很多时间，但这并不是没有代价的，因为你要先根据字典构建这棵树，这个代价并不低，当然对于某个应用来说一旦TrieTree构建完成就可以重复使用，所以针对大规模比对来说，性能提升还是很客观的。下面是TrieTree的C#实现。复制代码代码如下:publicclassTrieTree{TrieNode_root=null;privateTrieTree(){_root=newTrieNode(char.MaxValue,0);charCount=0;}staticTrieTree_instance=null;publicstaticTrieTreeGetInstance(){if(_instance==null){_instance=newTrieTree();}return_instance;}publicTrieNodeRoot{get{return_root;}}publicvoidAddWord(charch){TrieNodenewnode=_root.AddChild(ch);newnode.IncreaseFrequency();newnode.WordEnded=true;}intcharCount;publicvoidAddWord(stringword){if(word.Length==1){AddWord(word[0]);charCount++;}else{char[]chars=word.ToCharArray();TrieNodenode=_root;charCount+=chars.Length;for(inti=0;i<chars.Length;i++){TrieNodenewnode=node.AddChild(chars[i]);newnode.IncreaseFrequency();node=newnode;}node.WordEnded=true;}}publicintGetFrequency(charch){TrieNodematchedNode=_root.Children.FirstOrDefault(n=>n.Character==ch);if(matchedNode==null){return0;}returnmatchedNode.Frequency;}publicintGetFrequency(stringword){if(word.Length==1){returnGetFrequency(word[0]);}else{char[]chars=word.ToCharArray();TrieNodenode=_root;for(inti=0;i<chars.Length;i++){if(node.Children==null)return0;TrieNodematchednode=node.Children.FirstOrDefault(n=>n.Character==chars[i]);if(matchednode==null){return0;}node=matchednode;}if(node.WordEnded==true)ret