一球订、引言
我最近用Google以來，不管是客戶端Chrome還是手機端Chrome旋讹，每次查找資料殖蚕，都只需要打幾個單詞就行，后面的在下拉框選就行沉迹，像下面這樣——
我起初感覺這個提示的實現(xiàn)睦疫，是智能算法中的預(yù)測功能——通過輸入的前幾個字符對后面的進行預(yù)測。
但是今天看了看專欄后鞭呕「蛴恍然大悟，也許算法的優(yōu)化真的有用到預(yù)測功能，但是它起初用到的不是瓦糕，而是我們上次說過的——字符串匹配底洗。
- 匹配的本質(zhì)是什么？針對于字符串呢咕娄？
匹配的本質(zhì)就是找相同的地方亥揖。
針對于字符串，我認(rèn)為就是在多個字符串中search公共的子串圣勒。注意：不是單個字符费变，而是前綴子串或后綴子串。
那么好圣贸，匹配解釋完了挚歧，大家可以猜一下，這個功能是用了什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的吁峻？
其實我們不需要知道這個數(shù)據(jù)結(jié)構(gòu)的名字滑负，只需要知道它的特點是什么。那么我們來問下自己——
- 這個數(shù)據(jù)結(jié)構(gòu)需要posses的特點是什么锡搜？
特點就是可以在一組字符串集合中快速查找某個字符串橙困。
那么有這種DS嗎？有的——Trie樹耕餐。
二凡傅、Trie樹的本質(zhì)
2.1 如何使用trie樹解決實際問題？
For example肠缔，我們有6個字符串夏跷，分別是: how, hi, her, hello, so, see。
既然是應(yīng)用Trie樹明未，We就把這6個字符串組織成屬于它們自己的Trie樹槽华，i.e.，查找的時候趟妥，在一個樹形結(jié)構(gòu)里面查找猫态。
我們來分析一下上圖——
- 根節(jié)點不包含任何信息
- 每個節(jié)點的內(nèi)容都表示一個字符串的字符
- 從根節(jié)點到紅色節(jié)點的一個path表示一個字符串。
那么我想問大家一個問題：
- 圖中的紅色節(jié)點均是葉子節(jié)點嗎披摄？
2.2 如何構(gòu)造Trie樹亲雪？
我上節(jié)有提到一句話，就是針對這6個字符串疚膊，構(gòu)造的是屬于它們自己的Trie樹义辕，什么意思呢？
構(gòu)造Trie樹的每一個step寓盗，都是往Trie里面插入一個字符串灌砖。當(dāng)6個字符串插入finish以后璧函，Trie就build好了。
2.3 如何在構(gòu)造好的Trie樹中查找基显？
首先問兩個questions,
- 在一棵樹中查找蘸吓，我們匹配的載體是什么？
用樹來存儲數(shù)據(jù)续镇，數(shù)據(jù)都放在節(jié)點中美澳，所以載體就是節(jié)點销部。
在Trie樹中摸航，節(jié)點存放的都是單個字符。
So, 如果我們要查找字符串"her"舅桩，
- 第一步: 將her分割成h, e, r
第二步: 從Trie樹的根節(jié)點開始match酱虎。
查找字符串示意圖1
好，her的最后一個字符r是紅色節(jié)點擂涛，那么如果所查找的字符串的最后一個字符不是紅色節(jié)點呢读串？
比如，查找he撒妈。
如果出現(xiàn)這種情況恢暖，我們就可以believe that這個字符串“he”是某個字符串的前綴子串，但是并不能完全匹配任何字符串狰右。
2.4 如何用代碼實現(xiàn)一棵Trie樹杰捂？
我們在實現(xiàn)Trie樹前，先考慮一下棋蚌，
- We實現(xiàn)的Trie樹嫁佳，都要做什么工作？
在我看來谷暮，兩個——
- 將一個又一個字符串插入到Trie樹中蒿往。2. 在Trie樹中查詢一個字符串。
那么接下來湿弦，
- 如何存儲一個Trie樹瓤漏？
Trie樹是一棵多叉樹。二叉樹的存儲中颊埃，一個節(jié)點的左右子節(jié)點是通過指針來存儲的蔬充。
那么對于多叉樹呢？我們can借助散列表的思想竟秫，通過一個下標(biāo)與字符一一映射的數(shù)組娃惯，沒錯，是數(shù)組肥败，來存儲子節(jié)點的pointer趾浅。
假設(shè)愕提，字符串中有a-z26個小寫字母，也就是26個字符皿哨。
We在下標(biāo)為0的位置浅侨，存儲指向子節(jié)點a的指針，
在下標(biāo)為1的位置证膨，存儲指向子節(jié)點b的指針如输，
...
...
...
在下標(biāo)為25的位置，存儲指向子節(jié)點z的指針央勒。
If, 某個字符的子節(jié)點不存在不见，我們就在對應(yīng)的下標(biāo)位置存儲null。
存儲完Trie樹后崔步，我們要做的就是查找了稳吮。
- 查找的準(zhǔn)則：通過待查找字符的ASCII碼值減去“a”的ASCII碼值，從而快速查找到匹配的子節(jié)點的指針井濒。
舉個栗子：d 的 ASCII 碼減去 a 的 ASCII 碼就是 3灶似，那子節(jié)點 d 的指針就存儲在數(shù)組中下標(biāo)為 3的位置中。
2.5 Trie樹的時間復(fù)雜度是多少瑞你？
構(gòu)建 Trie 樹的過程酪惭，需要掃描所有的字符串，時間復(fù)雜度是 O(n)（n 表示所有字符串的長度和）者甲。
每次查詢時春感，如果要查詢的字符串長度是 k，那我們只需要比對大約 k 個節(jié)點过牙，就能完成查詢操作甥厦。
也就是說，Trie樹的時度跟原本那組字符串的長度和個數(shù)沒有任何關(guān)系寇钉。所以說刀疙，構(gòu)建好 Trie 樹后，在其中查找字符串的時間復(fù)雜度是 O(k)扫倡，k 表示要查找的字符串的長度谦秧。
三、Trie樹和內(nèi)存是死敵嗎撵溃？
是的疚鲤。
四、如何改善Trie樹缘挑？
既然集歇，Trie樹消耗內(nèi)存比較嚴(yán)重，那么其本質(zhì)是why? 猜一下就知道语淘，因為是數(shù)組存儲的诲宇。
我們不用數(shù)組存儲际歼，換一個。
有序數(shù)組姑蓝、跳表鹅心、散列表、紅黑樹
當(dāng)然纺荧，這四個數(shù)據(jù)結(jié)構(gòu)的使用旭愧，查詢效率就會低一些。
假設(shè)有序數(shù)組入選宙暇，數(shù)組中的指針按照所指向的子節(jié)點中的字符的大小順序排列输枯。
查詢的時候，我們可以通過二分查找的方法客给，快速查找到某個字符應(yīng)該匹配的子節(jié)點的指針用押。
但是肢簿，在往 Trie 樹中插入一個字符串的時候靶剑，我們?yōu)榱司S護數(shù)組中數(shù)據(jù)的有序性，插入的操作就會稍微慢了點池充。
Trie樹還有一個變體桩引，which can 解決內(nèi)存消耗，縮點優(yōu)化——
就是對只有一個子節(jié)點的節(jié)點收夸，而且此節(jié)點不是一個串的結(jié)束節(jié)點坑匠，可以將此節(jié)點與子節(jié)點合并。(這樣可以節(jié)省空間卧惜，但卻增加了編碼難度厘灼。)
五、散列表咽瓷、紅黑樹可以替代Trie樹嗎设凹？
Actually，字符串的匹配問題茅姜，就是數(shù)據(jù)的查找問題闪朱。
支持動態(tài)數(shù)據(jù)高效操作的數(shù)據(jù)結(jié)構(gòu)，比如散列表钻洒、紅黑樹奋姿、跳表等等。
實際上素标，這些數(shù)據(jù)結(jié)構(gòu)也可以實現(xiàn)在一組字符串中查找字符串的功能称诗。
Trie樹和紅黑樹and跳表相比，在處理情景一組字符串中查找字符串中头遭，Trie樹對要處理的字符串有4個比較嚴(yán)格的要求——
- 字符串中包含的字符集不能太大寓免。
Because如果字符集太大退腥，那存儲空間可能就會浪費很多。
即便可以優(yōu)化再榄，但也要付出犧牲查詢狡刘、插入效率的代價。
- 要求字符串的前綴重合比較多困鸥，不然空間消耗會變大很多嗅蔬。
- 如果要用 Trie 樹解決問題，那我們就要自己從零開始實現(xiàn)一個 Trie 樹疾就，還要保證沒有 bug澜术，這個在工程上是將簡單問題復(fù)雜化，除非必須猬腰，一般不建議這樣做鸟废。
- 通過指針串起來的數(shù)據(jù)塊是不連續(xù)的，而 Trie 樹中用到了指針姑荷，所以盒延，對緩存并不友好，性能上會打個折扣鼠冕。
綜合以上4點添寺，針對在一組字符串中查找字符串的問題，更傾向于用散列表或者紅黑樹懈费。
In fact计露，Trie 樹只是不適合精確匹配查找，這種問題更適合用散列表或者紅黑樹來解決憎乙。
Trie 樹比較適合的是查找前綴匹配的字符串票罐，也就是類似Google中的搜索詞提示的那種場景。
六泞边、如何利用 Trie 樹该押，實現(xiàn)搜索關(guān)鍵詞的提示功能？
We假設(shè)關(guān)鍵詞庫由用戶的熱門搜索關(guān)鍵詞組成繁堡，我們將這個詞庫構(gòu)建成一個 Trie 樹沈善。
當(dāng)用戶輸入其中某個單詞的時候，把這個詞作為一個前綴子串在 Trie 樹中匹配椭蹄。
- We假設(shè)詞庫里只有 hello闻牡、her、hi绳矩、how罩润、so、see 這 6 個關(guān)鍵詞翼馆。當(dāng)用戶輸入了字母 h 的時候割以，我們就把以 h 為前綴的 hello金度、her、hi严沥、how 展示在搜索提示框內(nèi)猜极。
- 當(dāng)用戶繼續(xù)鍵入字母 e 的時候，我們就把以 he 為前綴的 hello消玄、her 展示在搜索提示框內(nèi)跟伏。
以上就是搜索關(guān)鍵詞提示的最基本的算法原理。
