如何克服字典樹的缺點

常用的做法是用double array trie 取代樸素的trie能節省下大量內存空間，但未加修改的double array結構，大量插入時會產生大量的relocate操作，插入性能低下，最近看到叫cedar的double array改進方法。http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/ 插入和刪除性能已經和樸素的trie差不多了。其主要思想是建立空閑節點的索引，減少relocate和尋找可用節點的代價。官方的實現是C++版本的，有和很多常見和不常見的key-value數據結構對比的benchmark。結果上看性能確實很可觀。有興趣可以讀下源碼。最近在github上發現開始有用go在cedar結構上實現ahocorasick. 均衡了AC自動機的內存占用。