曾经有无数人挂在了一颗树上，它叫“高树“。这个周末我也彻底的死在了一颗树上只不过他的名字比较拉风”双数组Trie树“ 看Wiki 知道其本质是固定有限状态自动机，本以为有鸡肉吃，结果满嘴鸡毛。
从前我是毫无经验，为什么要去研究这特么复杂的鬼东西。这要从一个看似简单的事情说起。我的应用场景是我有一堆词，就是有个词典。然后需要去文章中查找，看文章里面有没有我词典中的词。特简单对不对，是不是不能再简单？
当词典只有几十几百的时候不是大问题，可以遍历词典。但是当词典上万，百万的时候你还要去遍历吗？遍历还解决不了其他问题。比如我词典中有两个词”重庆“，”重庆大学“ 。 假如你的文章是”我在重庆大学“ ，那你匹配的结果是”重庆“，还是”重庆大学“？ 这个问题就是中文分词存在的问题。
是不是觉得事情复杂了点儿，反正我觉得是。
为了解决快速搜索字典，有人发明了叫Trie树的东西也叫字典树，这颗树搜索所需的时间是和字符串长度成正比。这棵树的聪明之处在于利用了字符串的公共前缀来减少比较。去查一下原理还比较好理解，实现也不复杂。但是他有一个致命的缺点是比较耗空间。对于英文来说还可行，对于中文，日文基本就不靠谱了。因为汉字太多，而英文只有26个字母。
然后就发现有个日本人，是的日本人整出了个叫Dougle Array Trie 就是我说的双数组Trie树。Trie 不是Tree 的意思啊，他是来源于单词retrieval。
然后就去找什么是Double Array Trie .这下就完全挂在上面下不来了。代码看了，各种文章找了，还特地买了篇Paper 虽然说只要1块钱，但是啥都没懂。听说它的本质是固定有限状态自动机，好吧，我这种对问题本质有着执着追求的家伙，开始研究什么是自动状态机。结果就是满嘴鸡毛……
所以啊，遇到问题。警惕那些说简单的人。通常觉得某事很简单无外乎两种情况：
事情真的很简单。
你还没看清真相，觉得很简单。
尤其第二种居多，提醒自己，在你觉得某事很简单的时候，麻烦闭嘴，向前走三步，再向后走三步，来回三次。看问题是不是还简单。同理，当你觉得事情很复杂的时候，同样处理看看问题是不是还复杂。
也欢迎关注正午的个人公众号：正午不早了
