Trie tradisional mudah diterapkan, tetapi ruang yang digunakan benar-benar tidak dapat diterima. Terutama jika rangkaian karakter tidak terbatas pada 26 karakter bahasa Inggris, ruang yang meledak tidak dapat diterima.
Double array Trie adalah pohon Trie yang dioptimalkan ruang. Prinsipnya tidak akan dibahas dalam artikel ini. Silakan lihat Implementasi Struktur Trie yang Efisien. Program ini juga ditulis dengan mengacu pada makalah ini.
Mengenai beberapa rincian yang tidak disebutkan dalam makalah dan implementasi yang tidak sesuai dengan makalah:
1. Untuk memasukkan string, jika sebuah string adalah substring dari string lain, saya juga akan menggunakan terminator sebagai tepi untuk menghasilkan node baru. Saya akan mengatur Basis node baru ke 0.
Oleh karena itu, ada dua situasi di akhir string: satu adalah nilai Base negatif dan karakter yang tersisa (mungkin hanya satu terminator) disimpan dalam array Tail;
Oleh karena itu, Anda harus mempertimbangkan kedua situasi ini ketika mengajukan pertanyaan.
2. Untuk jenis konflik pertama (Kasus 3 di makalah), mungkin perlu mengambil sebagian string di Tail dan meletakkannya di indeks sebagai tepi. Makalah ini menggunakan metode menggeser string ekor ke kiri. Metode saya langsung mengubah nilai Base alih-alih memindahkan string ekor.
Berikut ini adalah kode yang diimplementasikan di java, yang dapat menangani penyisipan string yang sama, penyisipan substring, dll.
Copy kode kodenya sebagai berikut:
/*
* Nama: Trie Array Ganda
* Penulis: Yaguang Ding
* Surat: [email protected]
*Blog: blog.csdn.net/dingyaguang117
* Tanggal: 21/5/2012
* Catatan: akhiran kata dapat berupa salah satu dari dua kasus berikut:
* 1. Base[cur_p] == pos ( pos<0 dan Tail[-pos] == 'END_CHAR' )
* 2. Centang[Base[cur_p] + Kode('END_CHAR')] == cur_p
*/
impor java.util.ArrayList;
impor java.util.HashMap;
import java.util.Map;
import java.util.Array;
kelas publik DoubleArrayTrie {
karakter terakhir END_CHAR = '/0';
int akhir DEFAULT_LEN = 1024;
int Basis[] = int baru [DEFAULT_LEN];
int Periksa[] = int baru [DEFAULT_LEN];
char Tail[] = karakter baru [DEFAULT_LEN];
int Pos = 1;
Peta<Karakter,Bilangan Bulat> CharMap = HashMap baru<Karakter,Bilangan Bulat>();
ArrayList<Karakter> CharList = ArrayList<Karakter>();
publik DoubleArrayTrie()
{
Basis[1] = 1;
CharMap.put(END_CHAR,1);
CharList.tambahkan(END_CHAR);
CharList.tambahkan(END_CHAR);
untuk(int i=0;i<26;++i)
{
CharMap.put((char)('a'+i),CharMap.size()+1);
CharList.tambahkan((char)('a'+i));
}
}
kekosongan pribadi Extend_Array()
{
Basis = Array.copyOf(Basis, Basis.panjang*2);
Periksa = Arrays.copyOf(Periksa, Periksa.panjang*2);
}
kekosongan pribadi Extend_Tail()
{
Ekor = Arrays.copyOf(Ekor, Ekor.panjang*2);
}
int pribadi GetCharCode(char c)
{
if (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.tambahkan(c);
}
return CharMap.get(c);
}
pribadi int CopyToTailArray(String s,int p)
{
int _Pos = Pos;
while(s.length()-p+1 > Tail.length-Pos)
{
Perluas_Ekor();
}
untuk(int i=p; i<s.panjang();++i)
{
Ekor[_Pos] = s.charAt(i);
_Pos++;
}
kembalikan _Pos;
}
int pribadi x_check(Bilangan bulat []set)
{
untuk(ke dalam i=1; ; ++i)
{
bendera boolean = benar;
for(int j=0;j<set.panjang;++j)
{
int cur_p = i+set[j];
if(cur_p>= Basis.panjang) Extend_Array();
if(Base[cur_p]!= 0 || Centang[cur_p]!= 0)
{
bendera = salah;
merusak;
}
}
jika (bendera) kembalikan i;
}
}
Daftar Array pribadi<Bilangan Bulat> GetChildList(int p)
{
ArrayList<Bilangan Bulat> ret = Daftar Array baru<Bilangan Bulat>();
untuk(int i=1; i<=CharMap.size();++i)
{
if(Base[p]+i >= Check.length) break;
if(Periksa[Dasar[p]+i] == p)
{
ret.tambahkan(i);
}
}
kembali mundur;
}
boolean pribadi TailContainString(int start,String s2)
{
untuk(int i=0;i<s2.panjang();++i)
{
if(s2.charAt(i) != Tail[i+start]) mengembalikan false;
}
kembali benar;
}
boolean pribadi TailMatchString(int start,String s2)
{
s2 += END_CHAR;
untuk(int i=0;i<s2.panjang();++i)
{
if(s2.charAt(i) != Tail[i+start]) mengembalikan false;
}
kembali benar;
}
public void Insert(String s) memunculkan Pengecualian
{
s += END_CHAR;
int pra_p = 1;
int saat ini_p;
untuk(int i=0; i<s.panjang(); ++i)
{
//Dapatkan lokasi status
cur_p = Basis[pre_p]+GetCharCode(s.charAt(i));
//Jika panjangnya melebihi panjang yang ada, perluas arraynya
if (cur_p >= Base.length) Extend_Array();
// keadaan menganggur
if(Base[cur_p] == 0 && Periksa[cur_p] == 0)
{
Basis[saat ini_p] = -Pos;
Periksa[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
merusak;
}kalau tidak
//status yang ada
if(Base[cur_p] > 0 && Periksa[cur_p] == pre_p)
{
pra_p = sekarang_p;
melanjutkan;
}kalau tidak
//Konflik 1: Ketika Base[cur_p] kurang dari 0, ia menemukan string yang dikompresi dan disimpan di Tail.
if(Base[cur_p] < 0 && Periksa[cur_p] == pre_p)
{
int kepala = -Base[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)//Masukkan string berulang
{
merusak;
}
//Dalam kasus huruf biasa, karena keputusan terakhir tidak menyertakan terminator, maka keduanya harus bukan terminator.
if (Ekor[kepala] == s.charAt(i+1))
{
int ketersediaan_base = x_check(Bilangan Bulat baru[]{GetCharCode(s.charAt(i+1))});
Basis[saat ini_p] = basis_fail;
Periksa[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
Basis[avail_base+GetCharCode(s.charAt(i+1))] = -(head+1);
pra_p = sekarang_p;
melanjutkan;
}
kalau tidak
{
//Jika kedua huruf tersebut tidak sama, salah satunya mungkin merupakan terminator.
int info_base;
info_base = x_check(Bilangan Bulat baru[]{GetCharCode(s.charAt(i+1)),GetCharCode(Ekor[kepala])});
Basis[saat ini_p] = basis_fail;
Periksa[avail_base+GetCharCode(Ekor[kepala])] = cur_p;
Periksa[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//Ekornya adalah END_FLAG
if(Ekor[kepala] == END_CHAR)
Basis[avail_base+GetCharCode(Ekor[kepala])] = 0;
kalau tidak
Basis[avail_base+GetCharCode(Ekor[kepala])] = -(kepala+1);
if(s.charAt(i+1) == END_CHAR)
Basis[avail_base+GetCharCode(s.charAt(i+1))] = 0;
kalau tidak
Basis[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
merusak;
}
}kalau tidak
//Konflik 2: Node saat ini sudah terisi dan basis awal perlu disesuaikan.
if(Periksa[saat ini_p] != pra_p)
{
ArrayList<Bilangan Bulat> daftar1 = GetChildList(pre_p);
int untukMenyesuaikan;
ArrayList<Bilangan Bulat> daftar = null;
jika (benar)
{
toBeAdjust = pra_p;
daftar = daftar1;
}
int origin_base = Basis[toBeAdjust];
daftar.tambahkan(GetCharCode(s.charAt(i)));
int ketersediaan_base = x_check((Bilangan Bulat[])daftar.toArray(Bilangan Bulat Baru[daftar.ukuran()]));
daftar.hapus(daftar.ukuran()-1);
Basis[toBeAdjust] = info_base;
untuk(int j=0; j<daftar.ukuran(); ++j)
{
//SERANGGA
int tmp1 = asal_base + daftar.get(j);
int tmp2 = info_base + daftar.get(j);
Basis[tmp2] = Basis[tmp1];
Periksa[tmp2] = Periksa[tmp1];
//Ada tindak lanjut
jika(Dasar[tmp1] > 0)
{
ArrayList<Integer> selanjutnya = GetChildList(tmp1);
for(int k=0; k<urutan.ukuran(); ++k)
{
Periksa[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Basis[tmp1] = 0;
Periksa[tmp1] = 0;
}
//Perbarui cur_p baru
cur_p = Basis[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
Basis[saat ini_p] = 0;
kalau tidak
Basis[saat ini_p] = -Pos;
Periksa[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
merusak;
}
}
}
boolean publik Ada (String kata)
{
int pra_p = 1;
int sekarang_p = 0;
for(int i=0;i<kata.panjang();++i)
{
cur_p = Basis[pre_p]+GetCharCode(word.charAt(i));
if(Periksa[cur_p] != pre_p) mengembalikan false;
if(Dasar[saat ini_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
kembali benar;
kembali salah;
}
pra_p = sekarang_p;
}
if(Periksa[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
kembali benar;
kembali salah;
}
//Fungsi internal, mengembalikan indeks Basis terakhir dari kata yang cocok,
kelasFindStruct
{
ke dalam p;
Awalan string="";
}
FindStruct Find pribadi (String kata)
{
int pra_p = 1;
int sekarang_p = 0;
FindStruct fs = FindStruct baru();
for(int i=0;i<kata.panjang();++i)
{
// SERANGGA
fs.awalan += kata.charAt(i);
cur_p = Basis[pre_p]+GetCharCode(word.charAt(i));
if(Periksa[saat ini_p] != pra_p)
{
fs.p = -1;
kembalikan fs;
}
if(Dasar[saat ini_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
kembalikan fs;
}
fs.p = -1;
kembalikan fs;
}
pra_p = sekarang_p;
}
fs.p = cur_p;
kembalikan fs;
}
Daftar Array publik<String> GetAllChildWord(int indeks)
{
ArrayList<String> hasil = ArrayList<String>();
jika(Dasar[indeks] == 0)
{
hasil.tambahkan("");
hasil pengembalian;
}
jika(Dasar[indeks] < 0)
{
Tali r="";
for(int i=-Base[index];Ekor[i]!=END_CHAR;++i)
{
r+= Ekor[i];
}
hasil.tambahkan(r);
hasil pengembalian;
}
untuk(int i=1;i<=CharMap.size();++i)
{
if(Periksa[Dasar[indeks]+i] == indeks)
{
for(String s:GetAllChildWord(Base[index]+i))
{
hasil.tambahkan(CharList.get(i)+s);
}
//hasil.tambahkanSemua(GetAllChildWord(Dasar[indeks]+i));
}
}
hasil pengembalian;
}
Daftar Array publik<String> TemukanSemuaKata(String kata)
{
ArrayList<String> hasil = ArrayList<String>();
Awalan string = "";
FindStruct fs = Temukan(kata);
int p = fs.p;
if (p == -1) mengembalikan hasil;
jika(Dasar[p]<0)
{
Tali r="";
for(int i=-Base[p];Ekor[i]!=END_CHAR;++i)
{
r+= Ekor[i];
}
hasil.tambahkan(fs.prefix+r);
hasil pengembalian;
}
jika(Dasar[p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
untuk(int i=0;i<r.ukuran();++i)
{
r.set(i, fs.prefix+r.get(i));
}
kembali r;
}
hasil pengembalian;
}
}
Kode tes:
Copy kode kodenya sebagai berikut:
impor java.io.BufferedReader;
impor java.io.FileInputStream;
impor java.io.IOException;
impor java.io.InputStream;
impor java.io.InputStreamReader;
impor java.util.ArrayList;
impor java.util.Scanner;
impor javax.xml.crypto.Data;
kelas publik Utama {
public static void main(String[] args) melempar Pengecualian {
ArrayList<String> kata = ArrayList<String>();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Pusat Pembelajaran Eksperimental Kelinci [Di Kelas]/Kompetisi ACM/Kompetisi Sekolah ke-4 ACM/Prompt Perintah E/words3.dic")));
string;
int angka = 0;
while((s=reader.readLine()) != null)
{
kata-kata.add(s);
nomor++;
}
DoubleArrayTrie tanggal = DoubleArrayTrie baru();
untuk (String kata: kata-kata)
{
dat.Sisipkan(kata);
}
System.out.println(dat.Base.panjang);
System.out.println(dat.Tail.length);
Pemindai sc = Pemindai baru(Sistem.dalam);
while(sc.hasNext())
{
String kata = sc.next();
System.out.println(dat.Exists(kata));
System.out.println(dat.FindAllWords(kata));
}
}
}
Berikut adalah hasil tesnya. Dibutuhkan sekitar 20 detik untuk membuat DAT kata bahasa Inggris 6W.
Saat saya mengembangkan array, panjangnya bertambah menjadi 2 kali lipat setiap kali, awalnya 1024
Panjang array Base dan Check adalah 131072
Panjang Ekornya adalah 262144
TTT1