C#TrieTree介紹及實現方法

TrieTree簡單的説是一種多叉樹，每個節點保存一個字符，這麼做的好處是當我們要做NGram比對時，只需要直接從樹的根節點開始沿着某個樹叉遍歷下去，就能完成比對。下面小編為大家整理了C#TrieTree介紹及實現方法，希望能幫到大家！

在自然語言處理（NLP）研究中，NGram是最基本但也是最有用的一種比對方式，這裏的N是需要比對的字符串的長度，而今天我介紹的TrieTree，正是和NGram密切相關的一種數據結構，有人稱之為字典樹。TrieTree簡單的説是一種多叉樹，每個節點保存一個字符，這麼做的好處是當我們要做NGram比對時，只需要直接從樹的根節點開始沿着某個樹叉遍歷下去，就能完成比對；如果沒找到，停止本次遍歷。這話講得有些抽象，我們來看一個實際的例子。

假設我們現在詞庫裏面有以下一些詞：

上海市

上海灘

上海人

上海公司

北京

北斗星

楊柳

楊浦區

如圖所示：掛在根節點上的字有上、北、楊，

如果我們現在對“上海市楊浦區”這個詞做3gram就有上海市、海市楊、市楊浦、楊浦區，現在我們要知道哪些詞是能夠被這個字典識別的.，通常我們可以用NGram來做分詞。有了這顆樹，我們只需要依次取每個字符，從根開始進行比對，比如上海市，我們能夠匹配 上->海->市，這個路徑，所以匹配；比如海市楊，由於沒有“海”字掛在根節點上，所以停止；市楊浦也無法匹配；最終匹配楊浦區，得到 楊->浦->區 這個路徑，匹配。

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

儘管TrieTree要比普通字符串數組節省很多時間，但這並不是沒有代價的，因為你要先根據字典構建這棵樹，這個代價並不低，當然對於某個應用來説一旦TrieTree構建完成就可以重複使用，所以針對大規模比對來説，性能提升還是很客觀的。

下面是TrieTree的C#實現。

複製代碼 代碼如下:

public class TrieTree

{

TrieNode _root = null;

private TrieTree()

{

_root = new TrieNode(alue,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=_hild(ch);

easeFrequency();

Ended = true;

} int charCount;

public void AddWord(string word)

{

if (th == 1)

{

AddWord(word[0]);

charCount++;

}

else

{

char[] chars=arArray();

TrieNode node = _root;

charCount += th;

for (int i = 0; i < th; i++)

{

TrieNode newnode=hild(chars[i]);

easeFrequency();

node = newnode;

}

Ended = true;

}

}

public int GetFrequency(char ch)

{

TrieNode matchedNode = _tOrDefault(n => acter == ch);

if (matchedNode == null)

{

return 0;

}

return uency;

}

public int GetFrequency(string word)

{

if (th == 1)

{

return GetFrequency(word[0]);

}

else

{

char[] chars = arArray();

TrieNode node = _root;

for (int i = 0; i < th; i++)

{

if (dren == null)

return 0;

TrieNode matchednode = tOrDefault(n => acter == chars[i]);

if (matchednode == null)

{

return 0;

}

node = matchednode;

}

if (Ended == true)

return uency;

else

return -1;

}

}

}

這裏我們使用了單例模式，因為TrieTree類似緩存，不需要重複創建。下面是TreeNode的實現：

複製代碼 代碼如下:

public class TrieNode

{

public TrieNode(char ch,int depth)

{

acter=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 _tOrDefault(n => acter == ch);

else

return null;

}

public TrieNode AddChild(char ch)

{

TrieNode matchedNode=null;

if (_children != null)

{

matchedNode = _tOrDefault(n => acter == ch);

}

if (matchedNode != null)

//found the char in the list

{

//easeFrequency();

return matchedNode;

}

else

{

//not found

TrieNode node = new TrieNode(ch, h + 1);

nt = this;

//easeFrequency();

if (_children == null)

_children = new HashSet();

_(node);

return node;

}

}

int _frequency = 0;

public int Frequency

{

get { return _frequency;

}

}

public void IncreaseFrequency()

{

_frequency++;

}

public string GetWord()

{

TrieNode tmp=this;

string result = y;

while(nt!=null) //until root node

{

result = acter + result;

tmp = nt;

}

return result;

}

public override string ToString()

{

return ring(acter);

}

}