去哪找做網(wǎng)站的客戶網(wǎng)絡(luò)營(yíng)銷推廣
目錄
一.引言
二.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)。