您當前位置：首頁 > php開源 > php教程 > Trie樹的詳解及應用

Trie樹的詳解及應用

來源：程序員人生發(fā)布時間：2015-01-21 08:28:39 閱讀次數(shù)：3508次

Trie樹，又稱單詞查找樹或鍵樹，是1種樹形結構，是1種哈希樹的變種。典型利用是用于統(tǒng)計和排序大量的字符串（但不但限于字符串），所以常常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較，查詢效力比哈希表高。Trie的核心思想是空間換時間。利用字符串的公共前綴來下降查詢時間的開消以到達提高效力的目的。

　　Trie 的強大的地方就在于它的時間復雜度。它的插入和查詢時間復雜度都為 O(k) ，其中 k 為 key 的長度，與 Trie 中保存了多少個元素無關。Hash 表號稱是 O(1) 的，但在計算 hash 的時候就肯定會是 O(k) ，而且還有碰撞之類的問題；Trie 的缺點是空間消耗很高。

Trie樹特性：

1）根節(jié)點不包括字符，除根節(jié)點外每個節(jié)點都只包括1個字符。

2）從根節(jié)點到某1節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應的字符串。

3）每一個節(jié)點的所有子節(jié)點包括的字符都不相同。

4）如果字符的種數(shù)為n，則每一個結點的出度為n，這也是空間換時間的體現(xiàn)，浪費了很多的空間。

5）插入查找的復雜度為O(n)，n為字符串長度。

基本思想（以字母樹為例）：
1、插入進程
對1個單詞，從根開始，沿著單詞的各個字母所對應的樹中的節(jié)點分支向下走，直到單詞遍歷完，將最后的節(jié)點標記為紅色，表示該單詞已插入Trie樹。
2、查詢進程
一樣的，從根開始依照單詞的字母順序向下遍歷trie樹，1旦發(fā)現(xiàn)某個節(jié)點標記不存在或單詞遍歷完成而最后的節(jié)點未標記為紅色，則表示該單詞不存在，若最后的節(jié)點標記為紅色，表示該單詞存在。

字典樹的數(shù)據(jù)結構：
    利用串構建1個字典樹，這個字典樹保存了串的公共前綴信息，因此可以下降查詢操作的復雜度。
    下面以英文單詞構建的字典樹為例，這棵Trie樹中每一個結點包括26個孩子結點，由于總共有26個英文字母(假定單詞都是小寫字母組成)。
    則可聲明包括Trie樹的結點信息的結構體:

[cpp] view
 plaincopy

typedef struct Trie_node  

{  

    int count;                    // 統(tǒng)計單詞前綴出現(xiàn)的次數(shù)  

    struct Trie_node* next[26];   // 指向各個子樹的指針  

    bool exist;                   // 標記該結點處是不是構成單詞    

}TrieNode , *Trie;

其中next是1個指針數(shù)組，寄存著指向各個孩子結點的指針。
如給出字符串"abc","ab","bd","dda"，根據(jù)該字符串序列構建1棵Trie樹。則構建的樹以下:

Trie樹的根結點不包括任何信息，第1個字符串為"abc"，第1個字母為'a'，因此根結點中數(shù)組next下標為'a'⑼7的值不為NULL，其他同理，構建的Trie樹如圖所示，紅色結點表示在該處可以構成1個單詞。很明顯，如果要查找單詞"abc"是不是存在，查找長度則為O(len)，len為要查找的字符串的長度。而若采取1般的逐一匹配查找，則查找長度為O(len*n)，n為字符串的個數(shù)。明顯基于Trie樹的查找效力要高很多。
如上圖中：Trie樹中存在的就是abc、ab、bd、dda4個單詞。在實際的問題中可以將標記色彩的標志位改成數(shù)量count等其他符合題目要求的變量。

已知n個由小寫字母構成的平均長度為10的單詞，判斷其中是不是存在某個串為另外一個串的前綴子串。

下面對照3種方法：

1、最容易想到的：即從字符串集中從頭往后搜，看每一個字符串是不是為字符串集中某個字符串的前綴，復雜度為O(n^2)。
2、使用hash：我們用hash存下所有字符串的所有的前綴子串。建立存有子串hash的復雜度為O(n*len)。查詢的復雜度為O(n)* O(1)= O(n)。

3、使用Trie：由于當查詢如字符串abc是不是為某個字符串的前綴時，明顯以b、c、d....等不是以a開頭的字符串就不用查找了，這樣迅速縮小查找的范圍和提高查找的針對性。所以建立Trie的復雜度為O(n*len)，而建立+查詢在trie中是可以同時履行的，建立的進程也就能夠成為查詢的進程，hash就不能實現(xiàn)這個功能。所以總的復雜度為O(n*len)，實際查詢的復雜度只是O(len)。

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

Trie樹的詳解及應用