전통적인 Trie는 구현이 간단하지만 차지하는 공간이 정말 용납할 수 없습니다. 특히 문자 세트가 영어 26자로 제한되지 않는 경우에는 폭발적인 공간이 용납될 수 없습니다.
이중 배열 Trie는 공간 최적화된 Trie 트리입니다. 이 기사에서는 원리를 논의하지 않습니다. 이 프로그램은 이 문서를 참조하여 작성되었습니다.
백서에 언급되지 않은 몇 가지 세부 사항 및 백서와 일치하지 않는 구현에 관해:
1. 문자열을 삽입하기 위해 문자열이 다른 문자열의 하위 문자열인 경우 종결자를 가장자리로 사용하여 새 노드의 기준을 0으로 설정합니다.
따라서 문자열 끝에는 두 가지 상황이 있습니다. 하나는 Base 값이 음수이고 나머지 문자(아마도 단 하나의 종결자)가 Tail 배열에 저장되는 경우이고, 다른 하나는 Base가 0인 경우입니다.
따라서 문의 시에는 이 두 가지 상황을 고려해야 합니다.
2. 첫 번째 유형의 충돌(논문의 사례 3)의 경우 Tail의 문자열 일부를 꺼내 인덱스에 가장자리로 넣어야 할 수도 있습니다. 논문에서는 꼬리 문자열을 왼쪽으로 이동하는 방법을 사용합니다. 제 방법은 꼬리 문자열을 이동하는 대신 Base 값을 직접 수정합니다.
다음은 동일한 문자열 삽입, 하위 문자열 삽입 등을 처리할 수 있는 Java로 구현된 코드입니다.
다음과 같이 코드 코드를 복사합니다.
/*
* 이름: 이중 배열 트라이
* 저자: Yaguang Ding
* 메일 : [email protected]
* 블로그: blog.csdn.net/dingyaguang117
* 날짜: 2012년 5월 21일
* 참고: 단어 끝은 다음 두 가지 경우 중 하나일 수 있습니다.
* 1. Base[cur_p] == pos ( pos<0 및 Tail[-pos] == 'END_CHAR' )
* 2. 확인[Base[cur_p] + Code('END_CHAR')] == cur_p
*/
import java.util.ArrayList;
java.util.HashMap 가져오기;
java.util.Map 가져오기;
import java.util.Arrays;
공개 클래스 DoubleArrayTrie {
최종 문자 END_CHAR = '/0';
최종 int DEFAULT_LEN = 1024;
int Base[] = 새로운 int [DEFAULT_LEN];
int Check[] = 새로운 int [DEFAULT_LEN];
char Tail[] = 새 문자 [DEFAULT_LEN];
int Pos = 1;
Map<Character,Integer> CharMap = new HashMap<Character,Integer>();
ArrayList<Character> CharList = new ArrayList<Character>();
공개 DoubleArrayTrie()
{
베이스[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));
}
}
개인 무효 Extend_Array()
{
베이스 = Arrays.copyOf(베이스, Base.length*2);
Check = Arrays.copyOf(Check, Check.length*2);
}
개인 무효 Extend_Tail()
{
Tail = Arrays.copyOf(Tail, Tail.length*2);
}
개인 정수 GetCharCode(문자 c)
{
if (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
CharMap.get(c)를 반환합니다.
}
개인 int CopyToTailArray(String s,int p)
{
int _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++;
}
_Pos를 반환합니다.
}
private int x_check(정수 []set)
{
for(int i=1; ; ++i)
{
부울 플래그 = 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 || 확인[cur_p]!= 0)
{
플래그 = 거짓;
부서지다;
}
}
(플래그)가 i를 반환하는 경우;
}
}
개인 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(체크[베이스[p]+i] == p)
{
ret.add(i);
}
}
반환 ret;
}
개인 부울 TailContainString(int start,String s2)
{
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
사실을 반환;
}
개인 부울 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;
}
사실을 반환;
}
public void Insert(String s)가 예외를 발생시킵니다.
{
s += END_CHAR;
int pre_p = 1;
int cur_p;
for(int i=0; i<s.length(); ++i)
{
//상태 위치 가져오기
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//길이가 기존 길이를 초과하면 배열을 확장합니다.
if (cur_p >= Base.length) Extend_Array();
//유휴 상태
if(베이스[cur_p] == 0 && 확인[cur_p] == 0)
{
베이스[cur_p] = -Pos;
확인[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
부서지다;
}또 다른
//기존상태
if(Base[cur_p] > 0 && 확인[cur_p] == pre_p)
{
pre_p = cur_p;
계속하다;
}또 다른
//충돌 1: Base[cur_p]가 0보다 작을 때 Tail에 압축되어 저장된 문자열을 발견합니다.
if(베이스[cur_p] < 0 && 확인[cur_p] == pre_p)
{
int head = -Base[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)//반복 문자열 삽입
{
부서지다;
}
//공통문자의 경우 최종판결에서 종결자를 제외하였으므로 둘 다 종결자가 아니어야 합니다.
if (꼬리[머리] == s.charAt(i+1))
{
int avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});
베이스[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;
계속하다;
}
또 다른
{
//두 글자가 동일하지 않으면 그 중 하나가 종결자일 수 있습니다.
int avail_base;
avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
베이스[cur_p] = avail_base;
Check[avail_base+GetCharCode(Tail[head])] = cur_p;
Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//꼬리는 END_FLAG입니다.
if(꼬리[머리] == END_CHAR)
베이스[avail_base+GetCharCode(Tail[head])] = 0;
또 다른
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
if(s.charAt(i+1) == END_CHAR)
베이스[avail_base+GetCharCode(s.charAt(i+1))] = 0;
또 다른
베이스[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
부서지다;
}
}또 다른
//충돌 2: 현재 노드는 이미 점유되어 있으며 사전 베이스를 조정해야 합니다.
if(체크[cur_p] != pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> 목록 = null;
만약(사실)
{
toBeAdjust = pre_p;
목록 = 목록1;
}
int Origin_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);
베이스[toBeAdjust] = avail_base;
for(int j=0; j<list.size(); ++j)
{
//벌레
int tmp1 = Origin_base + list.get(j);
int tmp2 = avail_base + list.get(j);
베이스[tmp2] = 베이스[tmp1];
확인[tmp2] = 확인[tmp1];
//후속 작업이 있습니다.
if(베이스[tmp1] > 0)
{
ArrayList<Integer> 하위 시퀀스 = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Check[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
베이스[tmp1] = 0;
확인[tmp1] = 0;
}
//새 cur_p 업데이트
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
베이스[cur_p] = 0;
또 다른
베이스[cur_p] = -Pos;
확인[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
부서지다;
}
}
}
공개 부울 존재(문자열 단어)
{
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(베이스[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
사실을 반환;
거짓을 반환;
}
pre_p = cur_p;
}
if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
사실을 반환;
거짓을 반환;
}
//내부 함수, 일치하는 단어의 마지막 기본 인덱스를 반환합니다.
클래스FindStruct
{
정수 p;
문자열 접두사="";
}
개인 FindStruct Find(문자열 단어)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = 새로운 FindStruct();
for(int i=0;i<word.length();++i)
{
// 벌레
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(체크[cur_p] != pre_p)
{
fs.p = -1;
fs를 반환;
}
if(베이스[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
fs를 반환;
}
fs.p = -1;
fs를 반환;
}
pre_p = cur_p;
}
fs.p = cur_p;
fs를 반환;
}
공개 ArrayList<String> GetAllChildWord(int 인덱스)
{
ArrayList<String> 결과 = new ArrayList<String>();
if(베이스[인덱스] == 0)
{
결과.추가("");
결과 반환;
}
if(베이스[인덱스] < 0)
{
문자열 r="";
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= 꼬리[i];
}
결과.추가(r);
결과 반환;
}
for(int i=1;i<=CharMap.size();++i)
{
if(Check[Base[index]+i] == 인덱스)
{
for(문자열 s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
결과 반환;
}
public ArrayList<String> FindAllWords(문자열 단어)
{
ArrayList<String> 결과 = new ArrayList<String>();
문자열 접두사 = "";
FindStruct fs = 찾기(단어);
int p = fs.p;
if (p == -1) 결과를 반환합니다.
if(베이스[p]<0)
{
문자열 r="";
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= 꼬리[i];
}
result.add(fs.prefix+r);
결과 반환;
}
if(베이스[p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
for(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
r을 반환;
}
결과 반환;
}
}
테스트 코드:
다음과 같이 코드 코드를 복사합니다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
java.util.Scanner 가져오기;
javax.xml.crypto.Data 가져오기;
공개 클래스 메인 {
public static void main(String[] args)에서 예외가 발생합니다.
ArrayList<String> 단어 = new ArrayList<String>();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/토끼의 실험 학습 센터 [교실 내]/ACM 대회/ACM 4학년 대회/E 명령 프롬프트/words3.dic")));
문자열 s;
정수 숫자 = 0;
while((s=reader.readLine()) != null)
{
단어.추가(들);
숫자++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
for(문자열 단어: 단어)
{
dat.Insert(단어);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Scanner sc = new Scanner(System.in);
동안(sc.hasNext())
{
문자열 단어 = sc.next();
System.out.println(dat.Exists(단어));
System.out.println(dat.FindAllWords(단어));
}
}
}
다음은 테스트 결과입니다. 6W 영어 단어의 DAT를 구성하는 데 약 20초가 걸립니다.
배열을 늘리면 길이가 매번 2배로 늘어납니다. 처음에는 1024입니다.
Base 및 Check 배열의 길이는 131072입니다.
꼬리의 길이는 262144입니다.
TTT1