我弔死在了一顆樹上

曾經有無數人掛在了一顆樹上，它叫「高樹「。這個周末我也徹底的死在了一顆樹上只不過他的名字比較拉風」雙數組Trie樹「 看Wiki 知道其本質是固定有限狀態自動機，本以為有雞肉吃，結果滿嘴雞毛。

從前我是毫無經驗，為什麼要去研究這特么複雜的鬼東西。

這要從一個看似簡單的事情說起。我的應用場景是我有一堆詞，就是有個詞典。然後需要去文章中查找，看文章裡面有沒有我詞典中的詞。特簡單對不對，是不是不能再簡單？

當詞典只有幾十幾百的時候不是大問題，可以遍歷詞典。但是當詞典上萬，百萬的時候你還要去遍歷嗎？遍歷還解決不了其他問題。比如我詞典中有兩個詞」重慶「，」重慶大學「 。 假如你的文章是」我在重慶大學「 ，那你匹配的結果是」重慶「，還是」重慶大學「？ 這個問題就是中文分詞存在的問題。

是不是覺得事情複雜了點兒，反正我覺得是。

為了解決快速搜索字典，有人發明了叫Trie樹的東西也叫字典樹，這顆樹搜索所需的時間是和字元串長度成正比。這棵樹的聰明之處在於利用了字元串的公共前綴來減少比較。去查一下原理還比較好理解，實現也不複雜。但是他有一個致命的缺點是比較耗空間。對於英文來說還可行，對於中文，日文基本就不靠譜了。因為漢字太多，而英文只有26個字母。

然後就發現有個日本人，是的日本人整出了個叫Dougle Array Trie 就是我說的雙數組Trie樹。Trie 不是Tree 的意思啊，他是來源於單詞retrieval。

然後就去找什麼是Double Array Trie .這下就完全掛在上面下不來了。代碼看了，各種文章找了，還特地買了篇Paper 雖然說只要1塊錢，但是啥都沒懂。聽說它的本質是固定有限狀態自動機，好吧，我這種對問題本質有著執著追求的傢伙，開始研究什麼是自動狀態機。結果就是滿嘴雞毛……

所以啊，遇到問題。警惕那些說簡單的人。

1. 事情真的很簡單。
2. 你還沒看清真相，覺得很簡單。

尤其第二種居多，提醒自己，在你覺得某事很簡單的時候，麻煩閉嘴，向前走三步，再向後走三步，來回三次。看問題是不是還簡單。

同理，當你覺得事情很複雜的時候，同樣處理看看問題是不是還複雜。

歡迎關注正午的公眾號：正午不早了

也可訪問我的技術博客：http://midday.me

推薦閱讀：