双数组字典树DoubleArrayTrie

        双数组Tire树是Tire树的存储结构上升级版。

       在查询方面，双数组Tire树拥有Tire树的所有优点，而且刻服了Tire树浪费空间的不足。在插入和删除的时，往往需要对双数组结构进行全局调整,灵活性能较差。如果核心词典已经预先建立好并且有序的，并且不会添加或删除新词，那么这个缺点是可以忽略的。

标准Trie

     向一棵树中插入“清华”、“清华大学”、“清新”、“中华”、“华人”，形成trie.

双数组结构

       设例树的字符编码表为：[清-1，华-2，大-3，学-4，新-5，中-6，人-7]（也可以用默认的统一字符编码）

如图所示：

               Position:数据下标，position = 0的时间为root

               Base Array:转移基数数组，ROOT节点为1（可自定义），清的position位置确定为 base[0] + 1（清的编码）                     

                                  如何表示叶子节点？转移基数统一设置设为-1 * base[n], n为叶子节点的position

            Check Array: 较验数组。check数组记录的提这个字的父亲节点的下标，例【清】其 check[2] = 0 指向ROOT

           如果我们要在例树中确认外部的一个字符串“清中”是否是一个词，按照 Trie 树的查找规则，首先要查找“清”这个字，我们从根节点出发，获得|base[1]|+code(“清”)=3，然后转移到“清”节点，确认清在数组中存在，我们继续查找“中”，通过|base[3]|+code(“中”)=9获得位置9，字符串此时查询完毕，根据位置9的转移基数base[9]=-2确定该词在此终结，从而认为字符串“清中”是一个词。而这显然是错误的！所以加了check数组，发现check[9]=3指向“华”。

数组的构建

           1.首先将五个词中的首字"清"、“中”、“华”写入数组之中，写入的位置由base[1]+code(字符)确定，每个位置的转移基数（base[i]）等于上一个状态的转移基数（此例也即base[1]），这个过程未遇到冲突，最终结果见下图：

         2.然后依次处理每个词的第二个字，首先需要整理相同前缀词（“清华”，“清新”）（“中华”），（“华人”），程序先从根节点出发，通过base[1]+code(“清”)=2找到“清”节点，然后以此计算“华”节点应写入的位置，通过计算base[2]+code(“华”)=3寻找到位置 3,却发现位置3已有值；将base[2] + 1 = 2.再通过计算base[2]+code(“华”)=4，base[2]+code(“新”) = 7，base[7] 又发现有值；base[2] + 1 =3，再通过计算base[2]+code(“华”)=5，base[2]+code(“新”) = 8，成功。 base[5]=base[8]=base[2]=3.(“中华”），（“华人”） 简单。注： 上述的 base[2] 表示 |base[s]| (因为可能是叶子结点，上面忘记写绝对值)

simple代码

public class DoubleArrayTrie {String[] keys;// 字符集int[] base;// 转移数组int[] check;// 较验数组private static class Node {private int code;// 字符编码private int s;// 父字符位置@Overridepublic boolean equals(Object o) {if (this == o)return true;if (o == null || getClass() != o.getClass())return false;Node node = (Node) o;if (code != node.code)return false;return s == node.s;}@Overridepublic int hashCode() {int result = code;result = 31 * result + s;return result;}}public void build(List<String> list) {// 给所有字符定编码this.keys = list.stream().map(word -> word.split("")).flatMap(Arrays::stream).distinct().sorted().collect(Collectors.toList()).toArray(new String[0]);base = new int[3 * keys.length];check = new int[3 * keys.length];String[] dir = list.toArray(new String[0]);// 设置rootbase[0] = 1;for (int i = 0; i < check.length ; i++) {check[i] = -1;}// 词的深度int depth = 1;while (!list.isEmpty()) {// 根据相同前缀分组Map<Integer, List<Node>> map = new HashMap<>();for (int i = 0; i < list.size();) {String word = list.get(i);String pre = word.substring(0, depth - 1);String k = word.substring(depth - 1, depth);Node n = new Node();n.code = findIndex(k);n.s = depth == 1 ? 0 : indexOf(pre);if (depth == word.length()) {list.remove(i);} else {i++;}List<Node> siblings = map.getOrDefault(n.s, new ArrayList<>());if(siblings.contains(n)){continue;}siblings.add(n);map.put(n.s, siblings);}map.forEach((s, siblings) -> {int offset = 0;for (int i = 0; i < siblings.size(); i++) {Node node = siblings.get(i);int c = node.code;int t = base[s] + offset + c;// 发现在节点已有值则偏移+1if (check[t] != -1) {offset++;i = -1;}}base[s] = base[s] + offset;for (Node node : siblings) {int c = node.code;int t = base[s] + c;// 给上父结点check[t] = s;// 给拿上一个节点偏移量base[t] = base[s];}});depth++;}// 发现字节点，置为负数for (String aDir : dir) {int s = indexOf(aDir);base[s] = -1 * base[s];}}// 找询字符编码private int findIndex(String key) {for (int i = 0; i < keys.length; i++) {if (keys[i].equals(key))return i + 1;}throw new RuntimeException("找不到[" + key + "]");}// 定位前缀结点positionprivate int indexOf(String pre) {int s = 0;String[] ss = pre.split("");for (int i = 0; i < ss.length; i++) {String word = ss[i];int c = findIndex(word);int t = (base[s] < 0 ? -1 * base[s] : base[s]) + c;s = t;}return s;}public boolean get(String key) {int s = 0;String[] ss = key.split("");for (int i = 0; i < ss.length; i++) {String word = ss[i];int c = findIndex(word);int t = (base[s] < 0 ? -1 * base[s] : base[s]) + c;if (t >= base.length)return false;if (i == ss.length - 1 && check[t] == s) {return true;}s = t;}return false;}public static void main(String[] args) {DoubleArrayTrie adt = new DoubleArrayTrie();List<String> list = Stream.of(new String[]{"hers", "his", "she", "he"}).collect(Collectors.toList());// 构建DoubleArrayTrieadt.build(list);System.out.println(adt.get("hers"));System.out.println(adt.get("hr"));}
}

双数组Tire树相对Tire树。减少了查询过程的中比较。相当于对每单词进行hashcode标记
 

参考文献

      小白详解 Trie 树