Традиционный Trie прост в реализации, но место, которое он занимает, действительно неприемлемо. Особенно, когда набор символов не ограничен 26 английскими символами, разнесенное пространство просто неприемлемо.
Trie с двойным массивом — это оптимизированное по пространству дерево Trie. Этот принцип не будет обсуждаться в этой статье. См. «Эффективная реализация структур Trie». Эта программа также написана со ссылкой на эту статью.
Что касается некоторых деталей, не упомянутых в документе, и реализаций, не соответствующих документу:
1. Для вставки строк, если строка является подстрокой другой строки, я также буду использовать терминатор в качестве ребра для создания нового узла. Я установлю базу нового узла на 0.
Таким образом, в конце строки возможны две ситуации: одна — значение Base отрицательное, а оставшиеся символы (возможно, только один терминатор) сохраняются в массиве Tail; другая — значение Base равно 0;
Поэтому вам следует учитывать эти две ситуации при отправке запроса.
2. Для первого типа конфликта (случай 3 в статье) может потребоваться вынуть часть строки из Tail и поместить ее в индекс в качестве ребра. В документе используется метод смещения хвостовой строки влево. Мой метод напрямую изменяет базовое значение вместо перемещения хвостовой строки.
Ниже приведен код, реализованный в Java, который может обрабатывать вставку одной и той же строки, вставку подстрок и т. д.
Скопируйте код кода следующим образом:
/*
* Имя: Trie двойного массива
* Автор: Ягуан Дин
* Почта: [email protected]
* Блог: blog.csdn.net/dingyaguang117.
* Дата: 21 мая 2012 г.
* Примечание: окончание слова может быть в любом из этих двух случаев:
* 1. Base[cur_p] == pos ( pos<0 и Tail[-pos] == 'END_CHAR' )
* 2. Проверка[Base[cur_p] + Code('END_CHAR')] == cur_p
*/
импортировать java.util.ArrayList;
импортировать java.util.HashMap;
импортировать java.util.Map;
импортировать java.util.Arrays;
общественный класс DoubleArrayTrie {
конечный символ END_CHAR = '/0';
окончательный интервал DEFAULT_LEN = 1024;
int Base[] = новый int [DEFAULT_LEN];
int Check[] = новый int [DEFAULT_LEN];
char Tail[] = новый символ [DEFAULT_LEN];
интервал Поз = 1;
Map<Character,Integer> CharMap = новый HashMap<Character,Integer>();
ArrayList<Character> CharList = новый 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(База, База.длина*2);
Проверка = Arrays.copyOf(Проверка, Проверка.длина*2);
}
частная пустота Extend_Tail()
{
Хвост = Arrays.copyOf(Хвост, Хвост.длина*2);
}
частный int GetCharCode (char c)
{
если (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
вернуть CharMap.get(c);
}
частный int CopyToTailArray (String s, int p)
{
интервал _Pos = Поз;
while(s.length()-p+1 > Tail.length-Pos)
{
Расширить_Хвост();
}
for(int i=p; i<s.length();++i)
{
Хвост[_Pos] = s.charAt(i);
_Пос++;
}
вернуть _Pos;
}
частный int x_check (Целое число [] set)
{
for(int i=1; ; ++i)
{
логический флаг = правда;
for(int j=0;j<set.length;++j)
{
int cur_p = я+set[j];
if(cur_p>= Base.length) Extend_Array();
if(Base[cur_p]!= 0 || Проверить[cur_p]!= 0)
{
флаг = ложь;
перерыв;
}
}
if (флаг) возвращает i;
}
}
частный ArrayList<Integer> GetChildList(int p)
{
ArrayList<Integer> ret = новый ArrayList<Integer>();
for(int i=1; i<=CharMap.size();++i)
{
if(Base[p]+i >= Check.length) перерыв;
if(Проверить[Base[p]+i] == p)
{
ret.add(я);
}
}
вернуть возврат;
}
частное логическое значение TailContainString(int start,String s2)
{
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) возвращает false;
}
вернуть истину;
}
частное логическое значение TailMatchString(int start,String s2)
{
с2 += END_CHAR;
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) возвращает false;
}
вернуть истину;
}
public void Insert(String s) выдает исключение
{
с += END_CHAR;
интервал pre_p = 1;
интервал cur_p;
for(int i=0; i<s.length(); ++i)
{
//Получаем местоположение статуса
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//Если длина превышает существующую, расширяем массив
если (cur_p >= Base.length) Extend_Array();
// состояние простоя
if(Base[cur_p] == 0 && Проверка[cur_p] == 0)
{
База[cur_p] = -Pos;
Проверьте [cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
перерыв;
}еще
//существующий статус
if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
{
pre_p = cur_p;
продолжать;
}еще
//Конфликт 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)//Вставляем повторяющуюся строку
{
перерыв;
}
//В случае обычных писем, поскольку последнее решение исключило терминатор, оба они не должны быть терминаторами.
if (Tail[head] == 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;
продолжать;
}
еще
{
//Если две буквы не совпадают, одна из них может быть терминатором.
ИНТ 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
если(Хвост[голова] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
еще
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
if(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
еще
Base[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);
ИНТ toBeAdjust;
Список ArrayList<Integer> = null;
если (правда)
{
toBeAdjust = pre_p;
список = список1;
}
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)
{
//ОШИБКА
int tmp1 = origin_base + list.get(j);
int tmp2 =avail_base + list.get(j);
База[tmp2] = База[tmp1];
Проверить[tmp2] = Проверить[tmp1];
//Есть продолжение
если (База [tmp1] > 0)
{
Подпоследовательность ArrayList<Integer> = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Проверить[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
База[tmp1] = 0;
Проверить[tmp1] = 0;
}
//Обновляем новый cur_p
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
если(s.charAt(i) == END_CHAR)
База[cur_p] = 0;
еще
База[cur_p] = -Pos;
Проверьте [cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
перерыв;
}
}
}
общедоступное логическое значение существует (строковое слово)
{
интервал pre_p = 1;
интервал 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) возвращает false;
если (База [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
{
интервал р;
Строковый префикс="";
}
частный FindStruct Find (строковое слово)
{
интервал pre_p = 1;
интервал 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)
{
фс.п = -1;
вернуть фс;
}
если (База [cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
фс.п = cur_p;
вернуть фс;
}
фс.п = -1;
вернуть фс;
}
pre_p = cur_p;
}
фс.п = cur_p;
вернуть фс;
}
public ArrayList<String> GetAllChildWord (индекс int)
{
Результат ArrayList<String> = новый ArrayList<String>();
если(База[индекс] == 0)
{
результат.добавить("");
вернуть результат;
}
если(База[индекс] <0)
{
Строка г="";
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
г+= Хвост[i];
}
результат.добавить(г);
вернуть результат;
}
for(int i=1;i<=CharMap.size();++i)
{
if(Проверить[База[индекс]+i] == индекс)
{
for(String s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
вернуть результат;
}
public ArrayList<String> FindAllWords (строковое слово)
{
Результат ArrayList<String> = новый ArrayList<String>();
Строковый префикс = "";
FindStruct fs = Найти (слово);
int p = fs.p;
if (p == -1) вернуть результат;
если(База[p]<0)
{
Строка г="";
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
г+= Хвост[i];
}
result.add(fs.prefix+r);
вернуть результат;
}
если (База [p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
for(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
вернуть р;
}
вернуть результат;
}
}
Тестовый код:
Скопируйте код кода следующим образом:
импортировать java.io.BufferedReader;
импортировать java.io.FileInputStream;
импортировать java.io.IOException;
импортировать java.io.InputStream;
импортировать java.io.InputStreamReader;
импортировать java.util.ArrayList;
импортировать java.util.Scanner;
импортировать javax.xml.crypto.Data;
общественный класс Main {
public static void main(String[] args) выдает исключение {
ArrayList<String> слова = новый ArrayList<String>();
Читатель BufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Экспериментальный учебный центр Rabbit [В классе]/ACM Competition/4-й школьный конкурс ACM/E Command Prompt/words3.dic")));
Строка с;
целое число = 0;
while((s=reader.readLine()) != null)
{
слова.добавить(я);
число++;
}
DoubleArrayTrie dat = новый DoubleArrayTrie();
for(Строковое слово: слова)
{
dat.Insert (слово);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Сканер sc = новый сканер(System.in);
в то время как (sc.hasNext())
{
Строковое слово = sc.next();
System.out.println(dat.Exists(слово));
System.out.println(dat.FindAllWords(слово));
}
}
}
Ниже приведены результаты теста. Создание DAT из 6 Вт английских слов занимает около 20 секунд.
Когда я увеличиваю массив, длина каждый раз увеличивается в 2 раза, первоначально 1024.
Длина массивов Base и Check равна 131072.
Длина хвоста 262144.
ТТТ1