问题背景
最经典的字典树trie空间冗余太大了,设备只有64M内存实在顶不住,稍微学习了下其他字典树,DAT因为是第一个接触的,同时结构和理论很简洁,所以对它好感度较高,但这不意味着DAT是某种最优实现。
接触印象
优化冗余的一大方向就是去掉指针,将树结构映射成数组,DAT是此方向的佼佼者,DAT结构正如其名,将字典树映射成了两个数组base和check。去掉指针之后,DAT更加偏向一台记录状态的状态机,base负责记录当前状态转到下个状态的绝对数组下标,check负责记录状态转移是否有效。
其转移公式为t = base[p] + c, check[t] = p, 有部分实现将状态检查设计为 check[t] = base[p], 我还不能完全理解,可能在索引冲突时,在处理check数组时后者更加容易迁移数据。
关于DAT的一些优劣势
首先DAT的压缩率很高,base和check一个item各占用4byte,即使数组是稀疏数组,浪费的空间也极少。
DAT最擅长做的是精确匹配和前缀匹配,不擅长动态更新(实现复杂,涉及扩容和子孙数据迁移)和遍历数据(需要遍历所有可能状态)。
在构建DAT时,大部分时候还是使用静态构建,因为动态修改DAT非常容易造成索引冲突,解决冲突的实现和操作都较为复杂,同时需要注意,静态构建一般还是先构建成一颗传统字典树,然后按照排序构建DAT,因此程序的瞬时内存压力仍然存在,这方面应该存在优化方向。