當前位置:成語大全網 - 新華字典 - 如何克服字典樹的缺點

如何克服字典樹的缺點

常用的做法是用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自動機的內存占用。