dat

https://linux.thai.net/~thep/datrie/datrie.html

https://github.com/yuichiro-s/js-double-array-trie
https://github.com/euclidr/darts

双数组字典树核心思想：由base和check两个数组构成(base和check的索引表示一个状态)，缩短状态转移过程的时间。具体的，当状态b接受字符c转移到状态p时，满足条件(状态由整数下标表示)：state[p] = base[state[b]] + index[c]check[state[p]] == state[b]若条件不满足则转换失败。如：当前状态自然(例如state[自然]=1),若想判断是否可以转移到状态自然人，先执行state[自然人] = base[state[自然]] + index[人] = base[1] + index[人],然后判断check[state[自然人]] == state[自然]是否成立即可，仅需一次加法和整数比较就能进行状态转移，转移过程为常数事件。base和check构建过程*：假设有一个字符集仅有 {a, b, c} 有单词 a, ab, bbc, bc 构建一个 DAT，首先给字符集编码 index[a] = 1; index[b] = 2; index[c] = 3;

https://www.zhihu.com/topic/21180696/top-answers

DAT(double-array trie)定义:

把trie压缩成两个一维数组 BASE,CHECK 的DS-Tree(digital search tree)算法，称为double-array trie(下面缩写成DAT);这个算法的本质就是将Trie树结构简化为两个线性数组.

1.4、DAT由triple-array 演化而来缘由:

triple-array 结构较之DAT多了个 NEXT 数组,因我们可以把输入字符用数字化表示,

有 BASE[s] + a = m 以及CHECK[m] = s;

可知下一个节点m可以通过当前节点加上当前输入字符的索引算得出,并且保证其上一个节点就是s,故triple-array结构可以压缩到两个数组;

https://my.oschina.net/amince/blog/222806

https://blog.csdn.net/weixin_30670103/article/details/112720718

https://blog.csdn.net/qq_37667364/article/details/104242126

https://zhuanlan.zhihu.com/p/35193582

https://www.cnblogs.com/en-heng/p/6265256.html

Digital-search Tree定义:

K 表示模式串(KEYS)集合.

S 是有限的节点集合.

s 是初始节点,即root节点.

I 表示有限的输入字符(INPUT)集合.

g() 转移函数,是一个节点在接受一个字符后转向另一个节点或者失败的函数.

A 表示有限的接受状态(ACCEPT)节点集合.

https://my.oschina.net/amince/blog/222806