java双数组trie树的实现方案总结-mile米乐体育
java学习
2020年03月25日 23:40
1
传统的trie实现简单，但是占用的空间实在是难以接受，特别是当字符集不仅限于英文26个字符的时候，爆炸起来的空间根本无法接受。
双数组trie就是优化了空间的trie树，原理本文就不讲了，请参考an efficient implementation of trie structures，本程序的编写也是参考这篇论文的。
关于几点论文没有提及的细节和与论文不一一致的实现：
1.对于插入字符串，如果有一个字符串是另一个字符串的子串的话，我是将结束符也作为一条边，产生一个新的结点，这个结点新节点的base我置为0
所以一个字符串结束也有2中情况：一个是base值为负，存储剩余字符(可能只有一个结束符)到tail数组；另一个是base为0。
所以在查询的时候要考虑一下这两种情况
2.对于第一种冲突（论文中的case 3），可能要将tail中的字符串取出一部分，作为边放到索引中。论文是使用将尾串左移的方式，我的方式直接修改base值，而不是移动尾串。
下面是java实现的代码，可以处理相同字符串插入，子串的插入等情况
/* * name: double array trie * author: yaguang ding * mail: dingyaguang117@gmail.com * blog: blog.csdn.net/dingyaguang117 * date: 2012/5/21 * note: a word ends may be either of these two case: * 1. base[cur_p] == pos ( pos<0 and tail[-pos] == 'end_char' ) * 2. check[base[cur_p] code('end_char')] == cur_p */ import java.util.arraylist; import java.util.hashmap; import java.util.map; import java.util.arrays; public class doublearraytrie { final char end_char = '\0'; final int default_len = 1024; int base[] = new int [default_len]; int check[] = new int [default_len]; char tail[] = new char [default_len]; int pos = 1; map charmap = new hashmap(); arraylist charlist = new arraylist(); public doublearraytrie() { base[1] = 1; charmap.put(end_char,1); charlist.add(end_char); charlist.add(end_char); for(int i=0;i<26; i) { charmap.put((char)('a' i),charmap.size() 1); charlist.add((char)('a' i)); } } private void extend_array() { base = arrays.copyof(base, base.length*2); check = arrays.copyof(check, check.length*2); } private void extend_tail() { tail = arrays.copyof(tail, tail.length*2); } private int getcharcode(char c) { if (!charmap.containskey(c)) { charmap.put(c,charmap.size() 1); charlist.add(c); } return charmap.get(c); } private int copytotailarray(string s,int p) { int _pos = pos; while(s.length()-p 1 > tail.length-pos) { extend_tail(); } for(int i=p; i= base.length) extend_array(); if(base[cur_p]!= 0 || check[cur_p]!= 0) { flag = false; break; } } if (flag) return i; } } private arraylist getchildlist(int p) { arraylist ret = new arraylist(); for(int i=1; i<=charmap.size(); i) { if(base[p] i >= check.length) break; if(check[base[p] i] == p) { ret.add(i); } } return ret; } private boolean tailcontainstring(int start,string s2) { for(int i=0;i= base.length) extend_array(); //空闲状态 if(base[cur_p] == 0 && check[cur_p] == 0) { base[cur_p] = -pos; check[cur_p] = pre_p; pos = copytotailarray(s,i 1); break; }else //已存在状态 if(base[cur_p] > 0 && check[cur_p] == pre_p) { pre_p = cur_p; continue; }else //冲突 1：遇到 base[cur_p]小于0的，即遇到一个被压缩存到tail中的字符串 if(base[cur_p] < 0 && check[cur_p] == pre_p) { int head = -base[cur_p]; if(s.charat(i 1)== end_char && tail[head]==end_char) //插入重复字符串 { break; } //公共字母的情况，因为上一个判断已经排除了结束符，所以一定是2个都不是结束符 if (tail[head] == s.charat(i 1)) { int avail_base = x_check(new integer[]{getcharcode(s.charat(i 1))}); base[cur_p] = avail_base; check[avail_base getcharcode(s.charat(i 1))] = cur_p; base[avail_base getcharcode(s.charat(i 1))] = -(head 1); pre_p = cur_p; continue; } else { //2个字母不相同的情况，可能有一个为结束符 int avail_base ; avail_base = x_check(new integer[]{getcharcode(s.charat(i 1)),getcharcode(tail[head])}); base[cur_p] = avail_base; check[avail_base getcharcode(tail[head])] = cur_p; check[avail_base getcharcode(s.charat(i 1))] = cur_p; //tail 为end_flag 的情况 if(tail[head] == end_char) base[avail_base getcharcode(tail[head])] = 0; else base[avail_base getcharcode(tail[head])] = -(head 1); if(s.charat(i 1) == end_char) base[avail_base getcharcode(s.charat(i 1))] = 0; else base[avail_base getcharcode(s.charat(i 1))] = -pos; pos = copytotailarray(s,i 2); break; } }else //冲突2：当前结点已经被占用，需要调整pre的base if(check[cur_p] != pre_p) { arraylist list1 = getchildlist(pre_p); int tobeadjust; arraylist list = null; if(true) { tobeadjust = pre_p; list = list1; } int origin_base = base[tobeadjust]; list.add(getcharcode(s.charat(i))); int avail_base = x_check((integer[])list.toarray(new integer[list.size()])); list.remove(list.size()-1); base[tobeadjust] = avail_base; for(int j=0; j 0) { arraylist subsequence = getchildlist(tmp1); for(int k=0; k getallchildword(int index) { arraylist result = new arraylist(); if(base[index] == 0) { result.add(""); return result; } if(base[index] < 0) { string r=""; for(int i=-base[index];tail[i]!=end_char; i) { r = tail[i]; } result.add(r); return result; } for(int i=1;i<=charmap.size(); i) { if(check[base[index] i] == index) { for(string s:getallchildword(base[index] i)) { result.add(charlist.get(i) s); } //result.addall(getallchildword(base[index] i)); } } return result; } public arraylist findallwords(string word) { arraylist result = new arraylist(); string prefix = ""; findstruct fs = find(word); int p = fs.p; if (p == -1) return result; if(base[p]<0) { string r=""; for(int i=-base[p];tail[i]!=end_char; i) { r = tail[i]; } result.add(fs.prefix r); return result; } if(base[p] > 0) { arraylist r = getallchildword(p); for(int i=0;i 测试代码：
import java.io.bufferedreader; import java.io.fileinputstream; import java.io.ioexception; import java.io.inputstream; import java.io.inputstreamreader; import java.util.arraylist; import java.util.scanner; import javax.xml.crypto.data; public class main { public static void main(string[] args) throws exception { arraylist words = new arraylist(); bufferedreader reader = new bufferedreader(new inputstreamreader(new fileinputstream("e:/兔子的试验学习中心[课内]/acm大赛/acm第四届校赛/e命令提示/words3.dic"))); string s; int num = 0; while((s=reader.readline()) != null) { words.add(s); num ; } doublearraytrie dat = new doublearraytrie(); for(string word: words) { dat.insert(word); } system.out.println(dat.base.length); system.out.println(dat.tail.length); scanner sc = new scanner(system.in); while(sc.hasnext()) { string word = sc.next(); system.out.println(dat.exists(word)); system.out.println(dat.findallwords(word)); } } } 下面是测试结果，构造6w英文单词的dat，大概需要20秒
我增长数组的时候是每次长度增加到2倍，初始1024
base和check数组的长度为131072
tail的长度为262144
展开全文