??Trie Tree 實際上是一種前綴樹丸卷。在自然語言處理中我們經(jīng)常需要進行詞的匹配蔚出、查詢等等操作汹粤。Trie Tree 實際就是對所有單詞的前綴進行合并射亏。例如 banana 和ban 實際上其存在共同前綴ban阀溶。Trie Tree的首要就是合并這些前綴從而達到高效匹配與統(tǒng)計。
基本簡介
如上所示Trie實際上是一個多路查找樹鸦泳，每個節(jié)點都有可能是一個潛在的單詞银锻。每個節(jié)點的定義我們可以簡略定義如下：
struct Node
{
Node* children[26]
}
cnt 表示該單詞出現(xiàn)次數(shù)，如果0表示在該節(jié)點沒有單詞做鹰。children為指向下一集節(jié)點的指針击纬。
func insert(root, string, value):
node = root
index_last_char = None
for index_char, char in enumerate(string):
if char in node.children:
node = node.children[char]
else:
index_last_char = index_char
break
if index_last_char is not None:
for char in string[index_last_char:]:
node.children[char] = Node()
node = node.children[char]
node.value = value
func find(node, key):
for char in key:
if char in node.children:
node = node.children[char]
else:
return None
return node.value
如上為trie的插入和search的偽代碼實現(xiàn)，很是簡單钾麸。不過前面說過了更振，性能、空間饭尝、往往都是矛盾肯腕。上述實現(xiàn)也不例外，其也就停留在學(xué)習(xí)入門教學(xué)的程度钥平。上圖我們已經(jīng)看到節(jié)點 at 和ate因為只有單個子節(jié)點實際上是可以合并為ate一個.這也就是所謂的路徑壓縮实撒。有興趣的可以看下radix Tree實際上就是一種路徑壓縮。
應(yīng)用舉例
-
字符串檢索涉瘾，詞頻統(tǒng)計知态，搜索引擎的熱門查詢
事先將已知的一些字符串（字典）的有關(guān)信息保存到trie樹里，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率立叛。舉例：
1负敏、有一個1G大小的一個文件，里面每一行是一個詞秘蛇，詞的大小不超過16字節(jié)其做，內(nèi)存限制大小是1M顶考。返回頻數(shù)最高的100個詞。
2妖泄、給出N 個單詞組成的熟詞表驹沿，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞浮庐。
3甚负、給出一個詞典，其中的單詞為不良單詞审残。單詞均為小寫字母梭域。再給出一段文本，文本的每一行也由小寫字母構(gòu)成搅轿。判斷文本中是否含有任何不良單詞病涨。例如，若rob是不良單詞璧坟，那么文本problem含有不良單詞既穆。
4、1000萬字符串雀鹃，其中有些是重復(fù)的幻工，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串黎茎。請怎么設(shè)計和實現(xiàn)囊颅？
5、一個文本文件傅瞻，大約有一萬行踢代，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞嗅骄，請給出思想胳挎，給出時間復(fù)雜度分析。
6溺森、尋找熱門查詢：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來慕爬，每個查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個記錄儿惫，這些查詢串的重復(fù)讀比較高澡罚，雖然總數(shù)是1千萬，但是如果去除重復(fù)和肾请，不超過3百萬個。一個查詢串的重復(fù)度越高更胖，說明查詢它的用戶越多铛铁，也就越熱門隔显。請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G(京東筆試題簡答題與此類似)饵逐。
(1) 請描述你解決這個問題的思路括眠；
(2) 請給出主要的處理流程，算法倍权，以及算法的復(fù)雜度掷豺。
-
字符串最長公共前綴
Trie樹利用多個字符串的公共前綴來節(jié)省存儲空間，反之薄声，當(dāng)我們把大量字符串存儲到一棵trie樹上時当船，我們可以快速得到某些字符串的公共前綴。舉例：- 給出N 個小寫英文字母串默辨，以及Q 個詢問德频，即詢問某兩個串的最長公共前綴的長度是多少. 解決方案：
首先對所有的串建立其對應(yīng)的字母樹。此時發(fā)現(xiàn)缩幸，對于兩個串的最長公共前綴的長度即它們所在結(jié)點的公共祖先個數(shù)壹置，于是，問題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（Least Common Ancestor表谊，簡稱LCA）問題钞护。
- 給出N 個小寫英文字母串默辨，以及Q 個詢問德频，即詢問某兩個串的最長公共前綴的長度是多少. 解決方案：
-
排序
Trie樹是一棵多叉樹，只要先序遍歷整棵樹爆办，輸出相應(yīng)的字符串便是按字典序排序的結(jié)果难咕。舉例：給你N 個互不相同的僅由一個單詞構(gòu)成的英文名，讓你將它們按字典序從小到大排序輸出押逼。
作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)
如后綴樹步藕，AC自動機等。
上述問題一般都可以使用或者借助Trie來實現(xiàn)挑格。具體怎么處理大家自己可以慢慢思考
