【愚公系列】2021年11月 C#版 資料結構與算法解析(Trie樹)

/// <summary>
/// trie中的鍵通常是字元串，但也可以是其它的結構。trie的算法可以很容易地修改為處理其它結構的有序序列，比如一串數字或者形狀的排列。比如，bitwise trie中的鍵是一串比特，可以用于表示整數或者記憶體位址。
///使用Trie往往是為了實作單詞查找或者統計頻率.
/// </summary>
public class TNode
{
    public Dictionary<char, TNode> Childs { get; set; }
    public bool EndOfWrod { get; set; }
}

public class Trie
{
    private TNode _root = new TNode();

    public void Add(string word)
    {
        var currentNode = _root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!currentNode.Childs.ContainsKey(word[i]))
            {
                currentNode.Childs.Add(word[i], new TNode());
            }
            currentNode = currentNode.Childs[word[i]];
        }
        currentNode.EndOfWrod = true;
    }

    public bool Contains(string word)
    {
        return GetLastNode(word).EndOfWrod;
    }

    public bool StartWith(string preFix)
    {
        return GetLastNode(preFix) != null;
    }

    private TNode GetLastNode(string word)
    {
        var currentNode = _root;
        for (int i = 0; i < word.Length; i++)
        {
            if (!currentNode.Childs.ContainsKey(word[i]))
            {
                return null;
            }
            currentNode = currentNode.Childs[word[i]];
        }
        return currentNode;
    }
}      

Trie樹又叫“字典樹”，是一種在字元串計算中極為常見的資料結構。在介紹Trie樹的具體結構之前，我們首先要搞明白的就是Trie樹究竟是用來解決哪一類問題的，為什麼這類問題可以用Trie樹高效的解決。

我們為什麼用Trie樹

1. 節約字元串的存儲空間

假設現在我們需要對海量字元串建構字典。所謂字典就是一個集合，這個集合包含了所有不重複的字元串，字典在對文本資料做資訊檢索系統時的作用我想毋庸贅述了。那麼現在就出現了一個問題，那就是字典對存儲空間的消耗過大。而當這些字元串中存在大量的串擁有重複的字首時，這種消耗就顯得過于浪費了。比如:“ababc”,“ababd”,“ababrf”,“abab…”,…，這些字元串幾乎都擁有公共字首”abab”。 我們直接的想法是，能不能通過一種存儲結構節約存儲成本，使得所有擁有重複字首的串對于公共字首隻存儲一遍。這種存儲的應用場景如果是對DNA序列的存儲，那麼出現重複字首的可能性更大，空間需求也就更為強烈。

2. 字元串檢索

檢索一個字元串是否屬于某個詞典時，我們目前一般有兩種思路：

線性周遊詞典，計算複雜度O(n)，n為詞典長度；

利用hash表，預先處理字元串集合。這樣再搜尋運算時，計算複雜度O(1)。但是hash計算可能存在碰撞問題，一般的解決辦法比如對某個hash值所代表的字元串實施二次檢索，則計算時間也會上來。而且，hash雖說是一種高效算法，其計算效率比直接字元比對還是要略高的。

是以，能不能設計一種高效的資料結構幫助解決字元串檢索的問題？

3. 字元串公共字首問題

這裡有兩個非常典型的例子：

求取已知的n個字元串的最長公共字首，樸素方法的時間複雜度為O(nt)，t為最長公共字首的長度；

給定字元串a，求取a在某n個字元串中和哪些串擁有公共字首

對于問題(2)，除了樸素的比較法之外，我們還可以采取對每個字元串的所有字首計算hash值的方法，這樣一來，計算所有字首hash值複雜度O(n∗len)，len為字元串的平均長度，查詢的複雜度為O(n)。雖然降低了查詢複雜度，但是計算hash值顯然費時費力。

Trie樹的構造

1. 結構

Trie樹是如圖所示的一棵多叉樹。其中存儲的字元串集合為:

{“a”,“aa”,“ab”,“ac”,“aab”,“aac”,“bc”,“bd”,“bca”,“bcc”}