曾經(jīng)有無數(shù)人掛在了一顆樹上烦磁，它叫“高樹“。這個周末我也徹底的死在了一顆樹上只不過他的名字比較拉風(fēng)”雙數(shù)組Trie樹“ 看Wiki 知道其本質(zhì)是固定有限狀態(tài)自動機，本以為有雞肉吃，結(jié)果滿嘴雞毛。
從前我是毫無經(jīng)驗剪勿，為什么要去研究這特么復(fù)雜的鬼東西。這要從一個看似簡單的事情說起方庭。我的應(yīng)用場景是我有一堆詞厕吉，就是有個詞典。然后需要去文章中查找械念，看文章里面有沒有我詞典中的詞头朱。特簡單對不對，是不是不能再簡單订讼？
當(dāng)詞典只有幾十幾百的時候不是大問題髓窜，可以遍歷詞典。但是當(dāng)詞典上萬，百萬的時候你還要去遍歷嗎寄纵？遍歷還解決不了其他問題鳖敷。比如我詞典中有兩個詞”重慶“，”重慶大學(xué)“ 程拭。 假如你的文章是”我在重慶大學(xué)“ 定踱，那你匹配的結(jié)果是”重慶“，還是”重慶大學(xué)“恃鞋？ 這個問題就是中文分詞存在的問題崖媚。
是不是覺得事情復(fù)雜了點兒，反正我覺得是恤浪。
為了解決快速搜索字典畅哑，有人發(fā)明了叫Trie樹的東西也叫字典樹，這顆樹搜索所需的時間是和字符串長度成正比水由。這棵樹的聰明之處在于利用了字符串的公共前綴來減少比較荠呐。去查一下原理還比較好理解，實現(xiàn)也不復(fù)雜砂客。但是他有一個致命的缺點是比較耗空間泥张。對于英文來說還可行，對于中文鞠值，日文基本就不靠譜了媚创。因為漢字太多，而英文只有26個字母彤恶。
然后就發(fā)現(xiàn)有個日本人钞钙，是的日本人整出了個叫Dougle Array Trie 就是我說的雙數(shù)組Trie樹。Trie 不是Tree 的意思啊粤剧，他是來源于單詞retrieval歇竟。
然后就去找什么是Double Array Trie .這下就完全掛在上面下不來了挥唠。代碼看了抵恋，各種文章找了，還特地買了篇Paper 雖然說只要1塊錢宝磨，但是啥都沒懂弧关。聽說它的本質(zhì)是固定有限狀態(tài)自動機，好吧唤锉，我這種對問題本質(zhì)有著執(zhí)著追求的家伙世囊，開始研究什么是自動狀態(tài)機。結(jié)果就是滿嘴雞毛……
所以啊窿祥，遇到問題株憾。警惕那些說簡單的人。通常覺得某事很簡單無外乎兩種情況：
事情真的很簡單。
你還沒看清真相嗤瞎，覺得很簡單墙歪。
尤其第二種居多，提醒自己贝奇，在你覺得某事很簡單的時候虹菲，麻煩閉嘴，向前走三步掉瞳，再向后走三步毕源，來回三次∩孪埃看問題是不是還簡單霎褐。同理，當(dāng)你覺得事情很復(fù)雜的時候该镣，同樣處理看看問題是不是還復(fù)雜瘩欺。
也歡迎關(guān)注正午的個人公眾號：正午不早了
