双数组Trie树(DoubleArrayTrie)Java实现-下
前言：这代码写的我都快郁闷死了，构建逻辑是清楚的，但是落实在代码上就有很多边界问题和取上一个的问题，本来还想再优化一下，但是又想了下，先出一版代码吧。。。
前言2：这版代码我只测了a到z的字符，其他的没测（因为字符串要按char排序），也不支持数组扩展，如果太多的词就会有越界问题，不过这不影响本身的算法，重要的在于如何将前缀树构建到一个二维数组中，实现字符串匹配。
构建词列表要求：
词列表：
ab
abc
abcd
ba
bac
bacd
ca
cac
cacd
提供的字符串必须是有序的，每一列的每一行都是有序的，因为树是按照广度遍历建立的，也就是按照列顺序循环遍历建立，所以提供的词列表必须有序。
构建过程：
对应值： a = 97 b = 98 c = 99 d = 100
1 初始化 base 和check 默认值 base 默认 0 check 默认-1
2 输入的 base[0] 的值为 1 这个是偏移量 也可以是别的数
3 循环初始化第一列，去重后可以看出是 a b c 这时候base 和check 值如下
下标 0 98 99 100
字母 a b c
base 1 1 1 1
check -1 0 0 0
a的base下标 = 98 是通过 a的 char 97 + base[0]得到的，其他b和c也一样，因为第一层去重后，命中的base 下标不会冲突，所以直接构建就可以
4 (为了区分树的深度，如果是第一层的a我写成1a)循环初始化 第二列，在1a父节点的下边 只有 2b这个子节点 ，1b父节点下面只有2a这个子节点，1c父节点下面有2a这个子节点。
查出结果
下标 0 98 99 100 101 102 103
字母 a b c b a a
base 1 3 5 6 -3 -5 -6
check -1 0 0 0 98 99 100
这时候我们发现 base 下标为 98 99 100 也就是之前的第一层节点的base值都变了，因为根据上一次base[98] 中的值 偏移量为1 加上 b 98 = 99 已经被 1b占用了，所以自增了1，98+2=100也被1b占用了，所以就又加了1 找到 101 这时候 偏移量已经是3了，所以base[98]位置变成了3
这里第一层的 a b c节点每一层只有一个叶子节点，如果有多个 要满足 所有叶子几点的char 值加上父节点base上的偏移量，都能找到叶子节点的下标，否则就要累加偏移量继续寻找
check 记录 父节点的base下标，因为有可能出现 base[98]偏移量+char值 得到对应下标是有值的，但是不是base[98]的叶子节点，有可能被其他节点占用了，所以要加上check来验证
base 101 102 103 的值为负值，代表有一个词结束 当前数据就代表 ab ba ca 这三个词
5 循环上面的操作 下一层可得
查出结果
下标 0 98 99 100 101 102 103 104 105
字母 a b c b a a c c
base 1 3 5 6 -5 -6 -6 -5 -6
check -1 0 0 0 98 99 100 101 102
6 整体构建过程
下标 0 98 99 100 字母 a b c base 1 1 1 1
check -1 0 0 0 查出结果下标 0 98 99 100 101 102 103 字母 a b c b a a base 1 3 5 6 -3 -5 -6
check -1 0 0 0 98 99 100 查出结果下标 0 98 99 100 101 102 103 104 105 字母 a b c b a a c c base 1 3 5 6 -5 -6 -6 -5 -6
check -1 0 0 0 98 99 100 101 102 查出结果下标 0 98 99 100 101 102 103 104 105 106 107 108 字母 a b c b a a c c d c d base 1 3 5 6 -5 -6 -6 -6 -8 -6 7 8
check -1 0 0 0 98 99 100 101 102 104 105 105 查出结果下标 0 98 99 100 101 102 103 104 105 106 107 108 109 110 字母 a b c b a a c c d c d d e base 1 3 5 6 -5 -6 -6 -6 -8 -6 7 9 -8 -9
check -1 0 0 0 98 99 100 101 102 104 105 105 108 108 查出结果下标 0 98 99 100 101 102 103 104 105 106 107 108 109 110 字母 a b c b a a c c d c d d e base 1 3 5 6 -5 -6 -6 -6 -8 -6 7 9 -8 -9
check -1 0 0 0 98 99 100 101 102 104 105 105 108 108 查询过程
比如 查询 abcd
对应值： a = 97 b = 98 c = 99 d = 100
1 通过 base[0] + 97 = 98
2 通过 base[98] + 98 = 101
3 这时候看到base[101] 中为负值 说明有个结束 输出ab
4 通过base[101] + 99 = 104 base[104] 的值是 -6 （注释：如果base中的值是负数，计算的时候安绝对值算）负值 说明有个结束 输出abc
5 base[104]+ d = 106 base[106] 是负值说明有个结束 输出 abcd
6 其他：每次计算后都需要验证check中的值是不是父节点的下标
代码：
package myDoubleArrayTrie;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class MyDoubleArrayTrie {private final int arr_size = 655350; //数组大小private final int base_default = 0; //base默认值private final int base_head = 1; //base头偏移量private final int check_default = -1; //check默认private int[] base;private int[] check;/*** 构建方法** @param words*/public void build(List words) {//初始化resize();//先把首字母放进前缀树种-这里为了防止headAdd(words);//再把所有放入前缀树种AddAll(words);}/*** 查询方法** @return*/public List search(String word) {List rt = new ArrayList<>();if (word == null || word.length() == 0) {return new ArrayList<>();}//循环每个字符char[] chars = word.toCharArray();int before = base[0];String outWord = "";for (int i = 0; i < chars.length; i++) {//判断base是否有如果没有就直接结束int b = chars[i] + before;if (base[b] == base_default) {break;}before = Math.abs(base[b]);//如果有就把字符记录下来outWord = outWord + chars[i];//判断是否有结尾if (base[b] < 0) {rt.add(outWord);}}return rt;}/*** 初始化基础数据*/private void resize() {base = new int[arr_size];check = new int[arr_size];for (int i = 0; i < arr_size; i++) {base[i] = base_default;check[i] = check_default;}base[0] = base_head;}/*** 首字母* 这里必须先把首字母加进去，否则第一个字母不能直接命中，会找不到*/private void headAdd(List words) {Set set = new HashSet<>();//取首字母去重for (String s : words) {set.add(s.charAt(0));}//上一个的偏移量int before = base[0];//将首字母放入base 和 checkfor (char s : set) {//当前char加偏移量int a = before + s;base[a] = 1;check[a] = 0;}}/*** 添加所有到 base 和check** @param words*/private void AddAll(List words) {//1 获取最长int wordsLength = 0;//2 构建charchar[][] wordsChar = new char[words.size()][];for (int i = 0; i < words.size(); i++) {char[] charArr = words.get(i).toCharArray();wordsLength = Math.max(wordsLength,charArr.length);wordsChar[i] = charArr;}//列int column =0;//因为之前构建int l =0;int r =1;//上一个字符char pre = wordsChar[l][column];//上一个 base 下标int basePre = getPreBase(wordsChar[0],column);;boolean flag = true;while (flag) {//当前值如果和上一个值相等就继续找if (wordsChar[r].length>column&&wordsChar[r][column]==pre&&r < wordsChar.length-1) {r++;continue;}if (r == wordsChar.length-1) {r = wordsChar.length;}// l 到 r 的 字符 检查 base 和check是否有位置for (int i = l; i < r; i++) {//如果当前wordsChar是有数据的 才找叶子节点的base地址if (column+10) {base[basePre]=base[basePre]+1;}else{base[basePre]=base[basePre]-1;}i =l-1;//要从头找}}}// 走到这说明上一个循环已经确认base[basePre]偏移量 加上叶子节点的字符都能找到 空的base[]位置for (int i = l; i < r; i++) {//如果当前wordsChar是有数据的 才找叶子节点的base地址if (column+1());}}public int getPreBase(char[] chars, int column) {int before = base[0];for (int i = 0; i < chars.length; i++) {//判断base是否有如果没有就直接结束int b = chars[i] + before;if (base[b] == base_default) {break;}before = Math.abs(base[b]);if (i == column) {return b;}}return -1;}/*** 打印*/public void print(List list) {System.out.printf("%5s", "下标");for (int i = 0; i < base.length; i++) {if (base[i] != base_default) {System.out.printf("%7s\t", i);}}System.out.println();System.out.printf("%5s", "字母");System.out.printf("%7s\t", "");for (int i = 1; i < base.length; i++) {if (base[i] != base_default) {System.out.printf("%7s\t", String.valueOf((char) (i - Math.abs(base[check[i]]))));}}System.out.println();System.out.printf("%5s", "base");for (int i = 0; i < base.length; i++) {if (base[i] != base_default) {System.out.printf("%7s\t", base[i]);}}System.out.println();System.out.printf("%5s", "check");for (int i = 0; i < base.length; i++) {if (base[i] != base_default) {System.out.printf("%7s\t", check[i]);}}System.out.println();System.out.printf("%5s", "查出结果");if (list != null && list.size() != 0) {list.stream().forEach(a -> System.out.printf(a+","));}System.out.println();}
}
package myDoubleArrayTrie;import java.util.ArrayList;
import java.util.List;public class test {public static void main(String[] args) {MyDoubleArrayTrie myDoubleArrayTrie = new MyDoubleArrayTrie();List words = new ArrayList<>();words.add("ab");words.add("abc");words.add("abcd");words.add("ba");words.add("bac");words.add("bacde");words.add("ca");words.add("cac");words.add("cacde");//words.add("abe");myDoubleArrayTrie.build(words);List list = myDoubleArrayTrie.search("cac");myDoubleArrayTrie.print(list);System.out.println();}
}
总结：写的描述很简单，但是里面的流程确实比较复杂，后面再优化一半吧。。。。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！