- 相關(guān)推薦
C#TrieTree介紹及實(shí)現(xiàn)方法
TrieTree簡單的說是一種多叉樹，每個(gè)節(jié)點(diǎn)保存一個(gè)字符，這么做的好處是當(dāng)我們要做NGram比對時(shí)，只需要直接從樹的根節(jié)點(diǎn)開始沿著某個(gè)樹叉遍歷下去，就能完成比對。下面小編為大家整理了C#TrieTree介紹及實(shí)現(xiàn)方法，希望能幫到大家！
在自然語言處理（NLP）研究中，NGram是最基本但也是最有用的一種比對方式，這里的N是需要比對的字符串的長度，而今天我介紹的TrieTree，正是和NGram密切相關(guān)的一種數(shù)據(jù)結(jié)構(gòu)，有人稱之為字典樹。TrieTree簡單的說是一種多叉樹，每個(gè)節(jié)點(diǎn)保存一個(gè)字符，這么做的好處是當(dāng)我們要做NGram比對時(shí)，只需要直接從樹的根節(jié)點(diǎn)開始沿著某個(gè)樹叉遍歷下去，就能完成比對；如果沒找到，停止本次遍歷。這話講得有些抽象，我們來看一個(gè)實(shí)際的例子。
假設(shè)我們現(xiàn)在詞庫里面有以下一些詞：
上海市
上海灘
上海人
上海公司
北京
北斗星
楊柳
楊浦區(qū)
如圖所示：掛在根節(jié)點(diǎn)上的字有上、北、楊，
如果我們現(xiàn)在對“上海市楊浦區(qū)”這個(gè)詞做3gram就有上海市、海市楊、市楊浦、楊浦區(qū)，現(xiàn)在我們要知道哪些詞是能夠被這個(gè)字典識別的，通常我們可以用NGram來做分詞。有了這顆樹，我們只需要依次取每個(gè)字符，從根開始進(jìn)行比對，比如上海市，我們能夠匹配 上->海->市，這個(gè)路徑，所以匹配；比如海市楊，由于沒有“�！弊謷煸诟�(jié)點(diǎn)上，所以停止；市楊浦也無法匹配；最終匹配楊浦區(qū)，得到 楊->浦->區(qū) 這個(gè)路徑，匹配。
最終我們可以把“上海市楊浦區(qū)”切分為 上海市|楊浦區(qū)。
盡管TrieTree要比普通字符串?dāng)?shù)組節(jié)省很多時(shí)間，但這并不是沒有代價(jià)的，因?yàn)槟阋雀鶕?jù)字典構(gòu)建這棵樹，這個(gè)代價(jià)并不低，當(dāng)然對于某個(gè)應(yīng)用來說一旦TrieTree構(gòu)建完成就可以重復(fù)使用，所以針對大規(guī)模比對來說，性能提升還是很客觀的。
下面是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_children=null;
public HashSetChildren
{
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();
_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);
}
}
【C#TrieTree介紹及實(shí)現(xiàn)方法】相關(guān)文章：
java算法實(shí)現(xiàn)排列組合的方法介紹09-23
JAVA實(shí)現(xiàn)生成GUID的方法06-02