目錄

一.引言

二.Tire 樹簡(jiǎn)介

1.樹 Tree

2.二叉搜索樹 Binary Search Tree

3.字典樹 Trie Tree

3.1 基本概念

3.2 額外信息

3.3?結(jié)點(diǎn)實(shí)現(xiàn)

3.4 查找與存儲(chǔ)

三.Trie 樹應(yīng)用

1.應(yīng)用場(chǎng)景

2.Java / Scala 實(shí)現(xiàn)

2.1?Pom 依賴

2.2?關(guān)鍵詞匹配

四.總結(jié)

---

一.引言

Trie 樹即字典樹，又稱為單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，常用于統(tǒng)計(jì)，排序和保存大量的字符串，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。

◆ 優(yōu)點(diǎn) -?利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹高。

◆ 思想?- 其核心思想是空間換時(shí)間，通過(guò)拆分字符串并存儲(chǔ)換取查詢的高效率

二.Tire 樹簡(jiǎn)介

1.樹 Tree

上面是最常見的樹的形態(tài)，其擁有根節(jié)點(diǎn) root，有左右的 sub-tree 子樹，每個(gè)父結(jié)點(diǎn) Parent Node 可能擁有子節(jié)點(diǎn) Child Node，也有可能沒(méi)有子節(jié)點(diǎn)，此時(shí)為 None。Siblings 代表同級(jí)的兄弟姐妹節(jié)點(diǎn)，Level 代表樹的深度即層數(shù)。

2.二叉搜索樹 Binary Search Tree

二叉搜索樹（Binary Search Tree，簡(jiǎn)稱 BST），又被稱為二叉查找樹、排序二叉樹，是指一個(gè)空樹或者具備下列性質(zhì)的二叉樹：

◆?若任意節(jié)點(diǎn)的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于它的根節(jié)點(diǎn)的值。

◆?若任意節(jié)點(diǎn)的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于它的根節(jié)點(diǎn)的值。 ?

◆?任意節(jié)點(diǎn)的左、右子樹也分別為二叉搜索樹。 ?

◆?沒(méi)有鍵值相等的節(jié)點(diǎn)（即相同的元素只能出現(xiàn)一次）。

其具備以下特性:

◆?中序遍歷 - 對(duì) BST 進(jìn)行中序遍歷會(huì)得到一個(gè)有序的序列。這是因?yàn)樵谥行虮闅v的過(guò)程中，先訪問(wèn)左子節(jié)點(diǎn)（較小），再訪問(wèn)當(dāng)前節(jié)點(diǎn)，最后訪問(wèn)右子節(jié)點(diǎn)（較大）。

◆?查找效率 - 在 BST 中查找一個(gè)元素的平均時(shí)間復(fù)雜度和樹的深度有關(guān)，理想情況下，即 BST 是平衡的時(shí)候，時(shí)間復(fù)雜度是 O(log n)，其中 n 是樹中節(jié)點(diǎn)的數(shù)量。但是在最壞情況下，如樹完全不平衡（退化成鏈表），查找時(shí)間復(fù)雜度退化為O(n)。

◆?插入和刪除操作 - 插入和刪除也有可能改變樹的結(jié)構(gòu)。BST 的插入操作是指在滿足上述性質(zhì)的情況下，將一個(gè)新節(jié)點(diǎn)插入到樹中。刪除操作則可能涉及到重新調(diào)整樹的結(jié)構(gòu)，以保持二叉搜索樹的性質(zhì)。

3.字典樹 Trie Tree

3.1 基本概念

注意這里 Trie 樹不是二叉樹，而是一顆多叉樹，具體分多少叉要根據(jù)我們的實(shí)際場(chǎng)景來(lái)定。例如我們 Trie 樹要存儲(chǔ)所有英文單詞，那理論上每一個(gè)父結(jié)點(diǎn) Parent Node 要分 26 個(gè)子節(jié)點(diǎn) Child Node，因?yàn)橛⑽挠?26 個(gè)英文字母。Trie 樹具備如下基本性質(zhì):

◆ 結(jié)構(gòu)本身不存儲(chǔ)完整單詞，而是存儲(chǔ)每個(gè)細(xì)粒度的拆分項(xiàng)，例如單詞搜索則存儲(chǔ)字母

◆ 結(jié)從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，將路徑上的字符相連，為該結(jié)點(diǎn)對(duì)應(yīng)的字符串

◆ 每個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)路徑代表的字符都不相同，這里其實(shí)代表沒(méi)有重復(fù)字符串結(jié)點(diǎn)

3.2 額外信息

每個(gè) Node 結(jié)點(diǎn)除了存儲(chǔ)對(duì)應(yīng)的字符外，其還可以具備其自己的屬性，最簡(jiǎn)單的，上面的示例中給出了對(duì)應(yīng)字符串的出現(xiàn)頻次，這可以作為搜索推薦的參考依據(jù)，如果是代碼，其額外信息可以作為一個(gè) Class 存在，內(nèi)部包含該節(jié)點(diǎn)多個(gè)屬性，例如字符串對(duì)應(yīng)的領(lǐng)域、頻率、長(zhǎng)度、適用范圍等等。?說(shuō)到詞頻，也讓我們想起來(lái) Word2vec 里用到的霍夫曼樹，其在構(gòu)造編碼時(shí)也考慮了詞頻的因素，使得詞頻高的詞可以盡可能快的找到。

3.3?結(jié)點(diǎn)實(shí)現(xiàn)

這里對(duì)于每個(gè) Node 而言，結(jié)點(diǎn)就不存在 Left 和 Right 的概念了，而是直接對(duì)應(yīng)下一個(gè)可能的字符串，選定哪個(gè)字符串，就到下一個(gè)字符串對(duì)應(yīng)的 Node 上。如果我們認(rèn)為是簡(jiǎn)單單詞且不區(qū)分大小寫，我們可以認(rèn)為每個(gè) Node 最多有 26 個(gè)分叉結(jié)點(diǎn)，但如果有更多字符或特殊符號(hào)的加入，那么多叉樹會(huì)有更多的分叉。如果一個(gè)結(jié)點(diǎn)指向 null 代表其沒(méi)有兒子結(jié)點(diǎn)，此時(shí)連接其路徑上的字符即可得到該結(jié)點(diǎn)對(duì)應(yīng)的字符串表示。

3.4 查找與存儲(chǔ)

◆ 存儲(chǔ)

假設(shè)是上面提到的英文單詞查找，且不區(qū)分大小寫，此時(shí)最壞的情況為 26 叉樹，每分叉一次，一個(gè)結(jié)點(diǎn)就多 26 個(gè)叉，這樣的指數(shù)分叉對(duì)于存儲(chǔ)空間還是有很大的消耗。

◆ 查找

相比于存儲(chǔ)的消耗，查找的速度會(huì)快很多，因?yàn)椴檎业拇螖?shù)是和單詞的字符量匹配的，常見的英文單詞字符量在 10 左右，那我們只需要 10 次的常數(shù)時(shí)間就可以查到，以 you 為例，只需要 3 步就可以找到。但如果是用二分查找等方法，由于整個(gè)字典集的數(shù)量 n 特別大，即使排好序也是 Log(n) 的查找效率，會(huì)比 Trie 樹查找次數(shù)多很多。這也體現(xiàn)了我們開頭說(shuō)的 Trie 樹的核心思想: 空間換時(shí)間。其實(shí)這個(gè)概念不光是 Trie 樹，很多算法都會(huì)用到這個(gè)思想，將時(shí)間復(fù)雜度降低，空見復(fù)雜度提升。

三.Trie 樹應(yīng)用

1.應(yīng)用場(chǎng)景

因?yàn)?Trie 樹公共前綴的使用， 所以它十分適合搜索與輸入法拓展等領(lǐng)域，當(dāng)我們輸入了前面的公共前綴，其可以根據(jù)詞頻很容易的給出后面的候選。?實(shí)際場(chǎng)景中應(yīng)用較多的是 Aho-Corasick 算法，其適用于確定性的、完全匹配的字符串搜索場(chǎng)景，它能夠高效地檢測(cè)出預(yù)定義的關(guān)鍵詞是否在給定文本中出現(xiàn)。針對(duì)每一次輸入，算法都能找出所有存在的關(guān)鍵詞匹配。

2.Java / Scala 實(shí)現(xiàn)

2.1?Pom 依賴

        <!-- https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick --><dependency><groupId>org.ahocorasick</groupId><artifactId>ahocorasick</artifactId><version>0.6.3</version></dependency>

2.2?關(guān)鍵詞匹配

import org.ahocorasick.trie.{Emit, Token, Trie}// 初始化并構(gòu)建Trieval trie = Trie.builder().addKeyword("hers").addKeyword("his").addKeyword("she").addKeyword("he").build()// 搜索文本val text = "she sells sea shells by the sea shore"// 執(zhí)行搜索val tokens: java.util.Collection[Token] = trie.tokenize(text)// 注意這里使用Java轉(zhuǎn)Scala的集合轉(zhuǎn)換import scala.collection.JavaConverters._for (token <- tokens.asScala) {if (token.isMatch) {// 打印匹配的詞條和位置println(s"Found match: ${token.getFragment} at position ${token.getEmit.getStart}")}}

- addKeyword 用于添加關(guān)鍵詞到 Trie 樹中

- text 為代分析的文本

- tokenize 方法分析文本進(jìn)行關(guān)鍵詞匹配

- isMatch getFragment 獲取命中的關(guān)鍵詞，getEmit.getStart 與 getEnd 用于獲取 Fragment 片段在 text 中的起始位置

實(shí)戰(zhàn)場(chǎng)景下，Builder 過(guò)程中會(huì)添加一個(gè)很大的字典內(nèi)容構(gòu)造 Trie 樹，隨后應(yīng)用 Trie 樹進(jìn)行文本的關(guān)鍵詞匹配，判斷目標(biāo)文本是否命中字典中給定的關(guān)鍵字。

四.總結(jié)

上面就是 Trie 樹的簡(jiǎn)單介紹與應(yīng)用。如果想要開發(fā)類似 Google 的關(guān)鍵詞搜索推薦系統(tǒng)要比使用簡(jiǎn)單的 Aho-Corasick 算法要復(fù)雜得多，并且可能需要依賴機(jī)器學(xué)習(xí)和大數(shù)據(jù)處理技術(shù)。 如果你只是想實(shí)現(xiàn)一個(gè)簡(jiǎn)單版本的搜索推薦系統(tǒng)，可以考慮一些基礎(chǔ)的模糊匹配算法或使用現(xiàn)有的搜索引擎庫(kù)，比如 Elasticsearch，它內(nèi)置了自動(dòng)補(bǔ)全和模糊匹配的功能，同時(shí) Elasticsearch 也能夠通過(guò)集群分布式架構(gòu)來(lái)處理大規(guī)模數(shù)據(jù)集，非常適用于構(gòu)建搜索推薦系統(tǒng)。