快捷導(dǎo)航

C# TrieTree介紹及實(shí)現(xiàn)方法

更新時(shí)間：2013年04月28日 15:12:34 作者：

C# TrieTree介紹及實(shí)現(xiàn)方法，需要的朋友可以參考一下

在自然語(yǔ)言處理（NLP）研究中，NGram是最基本但也是最有用的一種比對(duì)方式，這里的N是需要比對(duì)的字符串的長(zhǎng)度，而今天我介紹的TrieTree，正是和NGram密切相關(guān)的一種數(shù)據(jù)結(jié)構(gòu)，有人稱之為字典樹。TrieTree簡(jiǎn)單的說(shuō)是一種多叉樹，每個(gè)節(jié)點(diǎn)保存一個(gè)字符，這么做的好處是當(dāng)我們要做NGram比對(duì)時(shí)，只需要直接從樹的根節(jié)點(diǎn)開始沿著某個(gè)樹叉遍歷下去，就能完成比對(duì)；如果沒(méi)找到，停止本次遍歷。這話講得有些抽象，我們來(lái)看一個(gè)實(shí)際的例子。

假設(shè)我們現(xiàn)在詞庫(kù)里面有以下一些詞：

上海市
上海灘
上海人
上海公司
北京
北斗星
楊柳
楊浦區(qū)

如圖所示：掛在根節(jié)點(diǎn)上的字有上、北、楊，

如果我們現(xiàn)在對(duì)“上海市楊浦區(qū)”這個(gè)詞做3gram就有上海市、海市楊、市楊浦、楊浦區(qū)，現(xiàn)在我們要知道哪些詞是能夠被這個(gè)字典識(shí)別的，通常我們可以用NGram來(lái)做分詞。有了這顆樹，我們只需要依次取每個(gè)字符，從根開始進(jìn)行比對(duì)，比如上海市，我們能夠匹配上->海->市，這個(gè)路徑，所以匹配；比如海市楊，由于沒(méi)有“?！弊謷煸诟?jié)點(diǎn)上，所以停止；市楊浦也無(wú)法匹配；最終匹配楊浦區(qū)，得到楊->浦->區(qū) 這個(gè)路徑，匹配。

最終我們可以把“上海市楊浦區(qū)”切分為上海市|楊浦區(qū)。

盡管TrieTree要比普通字符串?dāng)?shù)組節(jié)省很多時(shí)間，但這并不是沒(méi)有代價(jià)的，因?yàn)槟阋雀鶕?jù)字典構(gòu)建這棵樹，這個(gè)代價(jià)并不低，當(dāng)然對(duì)于某個(gè)應(yīng)用來(lái)說(shuō)一旦TrieTree構(gòu)建完成就可以重復(fù)使用，所以針對(duì)大規(guī)模比對(duì)來(lái)說(shuō)，性能提升還是很客觀的。

下面是TrieTree的C#實(shí)現(xiàn)。

復(fù)制代碼代碼如下:

   public class TrieTree    
   {        
   TrieNode _root = null;  
   private TrieTree()     
   {           
   _root = new TrieNode(char.MaxValue,0);  
   charCount = 0;   
   }       
   static TrieTree _instance = null; 
   public static TrieTree GetInstance()   
   {            
   if (_instance == null)        
   {             
   _instance = new TrieTree();       
   }           
   return _instance;   
   }        
   public TrieNode Root   
   {           
   get { return _root; 
   }   
   }        
   public void AddWord(char ch) 
   {           
TrieNode newnode=_root.AddChild(ch);   
newnode.IncreaseFrequency();           
newnode.WordEnded = true;      
}        int charCount;    
public void AddWord(string word)   
{          
if (word.Length == 1)     
{               
AddWord(word[0]);     
charCount++;       
}         
else    
{                 
char[] chars=word.ToCharArray();     
TrieNode node = _root;           
charCount += chars.Length;      
for (int i = 0; i < chars.Length; i++)  
{                    
TrieNode newnode=node.AddChild(chars[i]);    
newnode.IncreaseFrequency();           
node = newnode;           
}           
node.WordEnded = true;  
}       
}       
public int GetFrequency(char ch)   
{           
TrieNode matchedNode = _root.Children.FirstOrDefault(n => n.Character == ch);  
if (matchedNode == null)      
{               
return 0;        
}           
return matchedNode.Frequency;  
}       
public int GetFrequency(string word)
{        
if (word.Length == 1) 
{              
return GetFrequency(word[0]); 
}            
else      
{            
char[] chars = word.ToCharArray(); 
TrieNode node = _root;        
for (int i = 0; i < chars.Length; i++)   
{                 
if (node.Children == null)   
return 0;              
TrieNode matchednode = node.Children.FirstOrDefault(n => n.Character == chars[i]);
if (matchednode == null)          
{                      
return 0;         
}                  
node = matchednode;    
}              
if (node.WordEnded == true)        
return node.Frequency;       
else                   
return -1;           
}      
}   
}

這里我們使用了單例模式，因?yàn)門rieTree類似緩存，不需要重復(fù)創(chuàng)建。下面是TreeNode的實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

   public class TrieNode    
   {       
   public TrieNode(char ch,int depth)
   {           
   this.Character=ch; 
   this._depth=depth;
   }       
   public char Character; 
   int _depth;        
   public int Depth   
   {            
   get{return _depth;
   }      
   }     
   TrieNode _parent=null;
   public TrieNode Parent     
   {          
   get { 
   return _parent;
   }          
   set { _parent = value;
   } 
   }       
   public bool WordEnded = false;  
   HashSet<TrieNode> _children=null;  
   public HashSet<TrieNode> Children 
   {           
   get { 
   return _children;
   }       
   }        
   public TrieNode GetChildNode(char ch) 
   {            
   if (_children != null)    
   return _children.FirstOrDefault(n => n.Character == ch);  
   else               
   return null;      
   }       
   public TrieNode AddChild(char ch) 
   {           
   TrieNode matchedNode=null;      
   if (_children != null)      
   {               
   matchedNode = _children.FirstOrDefault(n => n.Character == ch);  
   }           
   if (matchedNode != null)   
   //found the char in the list   
   {                
   //matchedNode.IncreaseFrequency();      
   return matchedNode;         
   }           
   else          
   {  
   //not found       
   TrieNode node = new TrieNode(ch, this.Depth + 1);     
   node.Parent = this;      
   //node.IncreaseFrequency();            
   if (_children == null)               
   _children = new HashSet<TrieNode>();   
   _children.Add(node);              
   return node;          
   }       
   }       
   int _frequency = 0;       
   public int Frequency    
   {         
   get { return _frequency;
   }        
   }       
   public void IncreaseFrequency()      
   {          
   _frequency++;   
   }      
   public string GetWord() 
   {             
   TrieNode tmp=this;     
   string result = string.Empty;  
   while(tmp.Parent!=null) //until root node  
   {                
   result = tmp.Character + result;   
   tmp = tmp.Parent;     
   }            
   return result;     
   }        
   public override string ToString()
   {          
   return Convert.ToString(this.Character);
   }    
   }