Java中實(shí)現(xiàn)雙數(shù)組Trie樹實(shí)例
傳統(tǒng)的Trie實(shí)現(xiàn)簡(jiǎn)單，但是占用的空間實(shí)在是難以接受，特別是當(dāng)字符集不僅限于英文26個(gè)字符的時(shí)候，爆炸起來的空間根本無法接受。
雙數(shù)組Trie就是優(yōu)化了空間的Trie樹，原理本文就不講了，請(qǐng)參考An Efficient Implementation of Trie Structures，本程序的編寫也是參考這篇論文的。
關(guān)于幾點(diǎn)論文沒有提及的細(xì)節(jié)和與論文不一一致的實(shí)現(xiàn)：
1.對(duì)于插入字符串，如果有一個(gè)字符串是另一個(gè)字符串的子串的話，我是將結(jié)束符也作為一條邊，產(chǎn)生一個(gè)新的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)新節(jié)點(diǎn)的Base我置為0
所以一個(gè)字符串結(jié)束也有2中情況：一個(gè)是Base值為負(fù)，存儲(chǔ)剩余字符(可能只有一個(gè)結(jié)束符)到Tail數(shù)組；另一個(gè)是Base為0。
所以在查詢的時(shí)候要考慮一下這兩種情況
2.對(duì)于第一種沖突（論文中的Case 3），可能要將Tail中的字符串取出一部分，作為邊放到索引中。論文是使用將尾串左移的方式，我的方式直接修改Base值，而不是移動(dòng)尾串。
下面是java實(shí)現(xiàn)的代碼，可以處理相同字符串插入，子串的插入等情況
/*
* 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<Character ,Integer> CharMap = new HashMap<Character,Integer>();
ArrayList<Character> CharList = new ArrayList<Character>();
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<s.length();++i)
{
Tail[_Pos] = s.charAt(i);
_Pos++;
}
return _Pos;
}
private int x_check(Integer []set)
{
for(int i=1; ; ++i)
{
boolean flag = true;
for(int j=0;j<set.length;++j)
{
int cur_p = i+set[j];
if(cur_p>= Base.length) Extend_Array();
if(Base[cur_p]!= 0 || Check[cur_p]!= 0)
{
flag = false;
break;
}
}
if (flag) return i;
}
}
private ArrayList<Integer> GetChildList(int p)
{
ArrayList<Integer> ret = new ArrayList<Integer>();
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<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
return true;
}
private boolean TailMatchString(int start,String s2)
{
s2 += END_CHAR;
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
return true;
}
public void Insert(String s) throws Exception
{
s += END_CHAR;
int pre_p = 1;
int cur_p;
for(int i=0; i<s.length(); ++i)
{
//獲取狀態(tài)位置
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//如果長(zhǎng)度超過現(xiàn)有，拓展數(shù)組
if (cur_p >= Base.length) Extend_Array();
//空閑狀態(tài)
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
//已存在狀態(tài)
if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
{
pre_p = cur_p;
continue;
}else
//沖突 1：遇到 Base[cur_p]小于0的，即遇到一個(gè)被壓縮存到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) //插入重復(fù)字符串
{
break;
}
//公共字母的情況，因?yàn)樯弦粋€(gè)判斷已經(jīng)排除了結(jié)束符，所以一定是2個(gè)都不是結(jié)束符
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個(gè)字母不相同的情況，可能有一個(gè)為結(jié)束符
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：當(dāng)前結(jié)點(diǎn)已經(jīng)被占用，需要調(diào)整pre的base
if(Check[cur_p] != pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> 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<list.size(); ++j)
{
//BUG
int tmp1 = origin_base + list.get(j);
int tmp2 = avail_base + list.get(j);
Base[tmp2] = Base[tmp1];
Check[tmp2] = Check[tmp1];
//有后續(xù)
if(Base[tmp1] > 0)
{
ArrayList<Integer> subsequence = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Check[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Base[tmp1] = 0;
Check[tmp1] = 0;
}
//更新新的cur_p
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
Base[cur_p] = 0;
else
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
break;
}
}
}
public boolean Exists(String word)
{
int pre_p = 1;
int cur_p = 0;
for(int i=0;i<word.length();++i)
{
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p) return false;
if(Base[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
return true;
return false;
}
pre_p = cur_p;
}
if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
return true;
return false;
}
//內(nèi)部函數(shù)，返回匹配單詞的最靠后的Base index，
class FindStruct
{
int p;
String prefix="";
}
private FindStruct Find(String word)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
for(int i=0;i<word.length();++i)
{
// BUG
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p)
{
fs.p = -1;
return fs;
}
if(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
return fs;
}
fs.p = -1;
return fs;
}
pre_p = cur_p;
}
fs.p = cur_p;
return fs;
}
public ArrayList<String> GetAllChildWord(int index)
{
ArrayList<String> result = new ArrayList<String>();
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<String> FindAllWords(String word)
{
ArrayList<String> result = new ArrayList<String>();
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<String> r = GetAllChildWord(p);
for(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
return r;
}
return result;
}
}
測(cè)試代碼：
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<String> words = new ArrayList<String>();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/兔子的試驗(yàn)學(xué)習(xí)中心[課內(nèi)]/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));
}
}
}
下面是測(cè)試結(jié)果，構(gòu)造6W英文單詞的DAT，大概需要20秒
我增長(zhǎng)數(shù)組的時(shí)候是每次長(zhǎng)度增加到2倍，初始1024
Base和Check數(shù)組的長(zhǎng)度為131072
Tail的長(zhǎng)度為262144
TTT1
相關(guān)文章
elasticsearch索引的創(chuàng)建過程index?create邏輯分析
這篇文章主要介紹了elasticsearch索引核心index?create，索引的創(chuàng)建過程解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-04-04
關(guān)于Spring不同類型的注入方式 p-namespace,c-namespace
這篇文章主要介紹了Spring不同類型的注入方式 p-namespace,c-namespace。具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
Java 反轉(zhuǎn)帶頭結(jié)點(diǎn)的單鏈表并顯示輸出的實(shí)現(xiàn)過程
這篇文章主要介紹了Java 反轉(zhuǎn)帶頭結(jié)點(diǎn)的單鏈表并顯示輸出,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-11-11
JAVA maven項(xiàng)目使用釘釘SDK獲取token、用戶
這篇文章主要介紹了JAVA maven項(xiàng)目使用釘釘SDK獲取token、用戶，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
第一次使用Android Studio時(shí)你應(yīng)該知道的一切配置(推薦)
這篇文章主要介紹了第一次使用Android Studio時(shí)你應(yīng)該知道的一切配置(推薦) ,需要的朋友可以參考下2017-09-09
Spring @Async 的使用與實(shí)現(xiàn)的示例代碼
本篇文章主要介紹了Spring @Async 的使用與實(shí)現(xiàn)的示例代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08
仿釘釘流程輕松實(shí)現(xiàn)JSON轉(zhuǎn)BPMN完整實(shí)現(xiàn)過程示例
這篇文章主要為大家介紹了仿釘釘流程輕松實(shí)現(xiàn)JSON轉(zhuǎn)BPMN完整實(shí)現(xiàn)過程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
基于SpringBoot2.0默認(rèn)使用Redis連接池的配置操作
這篇文章主要介紹了基于SpringBoot2.0默認(rèn)使用Redis連接池的配置操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
三行Java代碼實(shí)現(xiàn)計(jì)算多邊形的幾何中心點(diǎn)
因?yàn)楣ぷ餍枰?jì)算采煤機(jī)工作面的中心點(diǎn)，如果套用數(shù)學(xué)的計(jì)算公式，用java去實(shí)現(xiàn)，太麻煩了。本文將利用java幾何計(jì)算的工具包，幾行代碼就能求出多變形的中心，簡(jiǎn)直yyds!還不快跟隨小編一起學(xué)起來2022-10-10
Java使用ExecutorService來停止線程服務(wù)
這篇文章主要介紹了Java使用ExecutorService來停止線程服務(wù)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04