Trie แบบดั้งเดิมนั้นใช้งานง่าย แต่พื้นที่ที่ใช้นั้นไม่สามารถยอมรับได้ โดยเฉพาะอย่างยิ่งเมื่อชุดอักขระไม่ได้จำกัดอยู่เพียงอักขระภาษาอังกฤษ 26 ตัว พื้นที่ที่ระเบิดนั้นเป็นสิ่งที่ยอมรับไม่ได้
Double array Trie เป็นแผนผัง Trie ที่ปรับให้เหมาะสมกับพื้นที่ หลักการจะไม่ถูกกล่าวถึงในบทความนี้
เกี่ยวกับรายละเอียดหลายประการที่ไม่ได้กล่าวถึงในรายงานและการดำเนินการที่ไม่สอดคล้องกับรายงาน:
1. สำหรับการแทรกสตริง หากสตริงเป็นสตริงย่อยของสตริงอื่น ฉันจะใช้จุดสิ้นสุดเป็นขอบเพื่อสร้างโหนดใหม่ ฉันจะตั้งค่าฐานของโหนดใหม่เป็น 0
ดังนั้นจึงมีสองสถานการณ์ที่ส่วนท้ายของสตริง: สถานการณ์แรกคือค่าฐานเป็นลบและอักขระที่เหลือ (อาจมีตัวสิ้นสุดเพียงตัวเดียว) จะถูกเก็บไว้ในอาร์เรย์ Tail อีกประการหนึ่งคือฐานเป็น 0
ดังนั้นคุณควรพิจารณาทั้งสองสถานการณ์นี้เมื่อทำการสอบถาม
2. สำหรับความขัดแย้งประเภทแรก (กรณีที่ 3 ในกระดาษ) อาจจำเป็นต้องดึงส่วนหนึ่งของสตริงใน Tail ออกแล้ววางลงในดัชนีเป็นขอบ กระดาษใช้วิธีการเลื่อนสตริงส่วนท้ายไปทางซ้าย วิธีการของฉันจะปรับเปลี่ยนค่าฐานโดยตรงแทนที่จะย้ายสตริงส่วนท้าย
ต่อไปนี้เป็นโค้ดที่ใช้ใน Java ซึ่งสามารถจัดการการแทรกสตริงเดียวกัน การแทรกสตริงย่อย ฯลฯ
คัดลอกรหัสรหัสดังต่อไปนี้:
-
* ชื่อ: อาร์เรย์คู่ Trie
* ผู้เขียน: ย่ากวง ติง
* ไปรษณีย์: [email protected]
* บล็อก: blog.csdn.net/dingyaguang117
* วันที่: 5/2555
* หมายเหตุ: คำที่ลงท้ายอาจเป็นอย่างใดอย่างหนึ่งในสองกรณีนี้:
* 1. Base[cur_p] == pos ( pos<0 และ Tail[-pos] == 'END_CHAR' )
* 2. ตรวจสอบ[ฐาน[cur_p] + รหัส('END_CHAR')] == cur_p
-
นำเข้า java.util.ArrayList;
นำเข้า java.util.HashMap;
นำเข้า java.util.Map;
นำเข้า java.util.Arrays;
DoubleArrayTrie คลาสสาธารณะ {
ถ่านสุดท้าย END_CHAR = '/0';
สุดท้าย int DEFAULT_LEN = 1,024;
int Base[] = int ใหม่ [DEFAULT_LEN];
int Check[] = int ใหม่ [DEFAULT_LEN];
ถ่าน Tail[] = ถ่านใหม่ [DEFAULT_LEN];
int POS = 1;
แผนที่<ตัวละคร,จำนวนเต็ม> CharMap = ใหม่ HashMap<ตัวละคร,จำนวนเต็ม>();
ArrayList<ตัวละคร> CharList = ใหม่ ArrayList<ตัวละคร>();
DoubleArrayTrie สาธารณะ ()
-
ฐาน[1] = 1;
CharMap.put(END_CHAR,1);
CharList.add(END_CHAR);
CharList.add(END_CHAR);
สำหรับ(int i=0;i<26;++i)
-
CharMap.put((ถ่าน)('a'+i),CharMap.size()+1);
CharList.add((ถ่าน)('a'+i));
-
-
โมฆะส่วนตัว Extended_Array ()
-
Base = Arrays.copyOf(ฐาน, Base.length*2);
ตรวจสอบ = Arrays.copyOf (ตรวจสอบ, ตรวจสอบความยาว * 2);
-
โมฆะส่วนตัว Extended_Tail ()
-
หาง = Arrays.copyOf (หาง, Tail.length*2);
-
int GetCharCode ส่วนตัว (ถ่าน c)
-
ถ้า (!CharMap.containsKey(c))
-
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
-
กลับ CharMap.get(c);
-
ส่วนตัว int CopyToTailArray (สตริง s, int p)
-
int _Pos = ตำแหน่ง;
ในขณะที่(s.length()-p+1 > Tail.length-Pos)
-
ขยาย_หาง();
-
สำหรับ(int i=p; i<s.length();++i)
-
หาง[_Pos] = s.charAt(i);
_ตำแหน่ง++;
-
กลับ _Pos;
-
int x_check ส่วนตัว (ชุดจำนวนเต็ม [])
-
สำหรับ(int i=1; ; ++i)
-
ธงบูลีน = จริง;
สำหรับ(int j=0;j<set.length;++j)
-
int cur_p = i+set[j];
ถ้า (cur_p>= Base.length) Extended_Array ();
ถ้า(ฐาน[cur_p]!= 0 || ตรวจสอบ[cur_p]!= 0)
-
ธง = เท็จ;
หยุดพัก;
-
-
ถ้า (ธง) ส่งคืน i;
-
-
ArrayList ส่วนตัว <จำนวนเต็ม> GetChildList (int p)
-
ArrayList<จำนวนเต็ม> ret = ใหม่ ArrayList<จำนวนเต็ม>();
สำหรับ(int i=1; i<=CharMap.size();++i)
-
if(Base[p]+i >= Check.length) แตก;
ถ้า(ตรวจสอบ[ฐาน[p]+i] == p)
-
ret.เพิ่ม(i);
-
-
กลับมาอีกครั้ง;
-
TailContainString บูลีนส่วนตัว (เริ่มต้น int, String s2)
-
สำหรับ(int i=0;i<s2.length();++i)
-
if(s2.charAt(i) != Tail[i+start]) กลับเท็จ;
-
กลับเป็นจริง;
-
TailMatchString บูลีนส่วนตัว (เริ่มต้น int, String s2)
-
s2 += END_CHAR;
สำหรับ(int i=0;i<s2.length();++i)
-
if(s2.charAt(i) != Tail[i+start]) กลับเท็จ;
-
กลับเป็นจริง;
-
โมฆะสาธารณะแทรก (สตริง s) พ่นข้อยกเว้น
-
ส += END_CHAR;
int pre_p = 1;
intcur_p;
สำหรับ(int i=0; i<s.length(); ++i)
-
//รับตำแหน่งสถานะ
cur_p = ฐาน[pre_p]+GetCharCode(s.charAt(i));
//หากความยาวเกินความยาวที่มีอยู่ ให้ขยายอาร์เรย์
ถ้า (cur_p >= Base.length) Extended_Array();
//สถานะไม่ได้ใช้งาน
ถ้า(ฐาน[cur_p] == 0 && ตรวจสอบ[cur_p] == 0)
-
ฐาน[cur_p] = -Pos;
ตรวจสอบ[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
หยุดพัก;
}อื่น
//สถานะที่มีอยู่
ถ้า(ฐาน[cur_p] > 0 && ตรวจสอบ[cur_p] == pre_p)
-
pre_p = cur_p;
ดำเนินการต่อ;
}อื่น
//ข้อขัดแย้งที่ 1: เมื่อ Base[cur_p] น้อยกว่า 0 จะพบสตริงที่ถูกบีบอัดและเก็บไว้ใน Tail
ถ้า (ฐาน [cur_p] < 0 && ตรวจสอบ [cur_p] == pre_p)
-
int head = -ฐาน[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)// ใส่สตริงซ้ำ
-
หยุดพัก;
-
//ในกรณีของตัวอักษรทั่วไป เนื่องจากการตัดสินครั้งสุดท้ายไม่รวมตัวต่อท้าย ดังนั้นทั้งสองตัวจะต้องไม่ใช่ตัวต่อท้าย
ถ้า (หาง[หัว] == s.charAt(i+1))
-
int avail_base = x_check(จำนวนเต็มใหม่[]{GetCharCode(s.charAt(i+1))});
ฐาน[cur_p] = avail_base;
ตรวจสอบ [avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
ฐาน[avail_base+GetCharCode(s.charAt(i+1))] = -(หัว+1);
pre_p = cur_p;
ดำเนินการต่อ;
-
อื่น
-
//หากตัวอักษรสองตัวไม่เหมือนกัน หนึ่งในนั้นอาจเป็นตัวยุติ
int avail_base;
avail_base = x_check(จำนวนเต็มใหม่[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
ฐาน[cur_p] = avail_base;
ตรวจสอบ [avail_base+GetCharCode(ส่วนท้าย[หัว])] = cur_p;
ตรวจสอบ [avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//ส่วนท้ายคือ END_FLAG
ถ้า (หาง [หัว] == END_CHAR)
ฐาน[avail_base+GetCharCode(ส่วนท้าย[หัว])] = 0;
อื่น
ฐาน[avail_base+GetCharCode(ส่วนท้าย[หัว])] = -(หัว+1);
ถ้า(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: โหนดปัจจุบันถูกครอบครองแล้ว และจำเป็นต้องปรับฐานล่วงหน้า
ถ้า (ตรวจสอบ [cur_p] != pre_p)
-
ArrayList<จำนวนเต็ม> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<จำนวนเต็ม> รายการ = null;
ถ้า(จริง)
-
toBeAdjust = pre_p;
รายการ = รายการ 1;
-
int origin_base = ฐาน[toBeAdjust];
list.add(GetCharCode(s.charAt(i)));
int avail_base = x_check((จำนวนเต็ม[])list.toArray(จำนวนเต็มใหม่[list.size()]));
list.remove(list.size()-1);
ฐาน[toBeAdjust] = avail_base;
สำหรับ(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);
สำหรับ(int k=0; k<subsequence.size(); ++k)
-
ตรวจสอบ[ฐาน[tmp1]+subsequence.get(k)] = tmp2;
-
-
ฐาน[tmp1] = 0;
ตรวจสอบ [tmp1] = 0;
-
//อัพเดต cur_p ใหม่
cur_p = ฐาน[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);
หยุดพัก;
-
-
-
บูลีนสาธารณะมีอยู่ (คำสตริง)
-
int pre_p = 1;
int cur_p = 0;
สำหรับ(int i=0;i<word.length();++i)
-
cur_p = ฐาน[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p) return false;
ถ้า (ฐาน [cur_p] < 0)
-
ถ้า(TailMatchString(-Base[cur_p],word.substring(i+1)))
กลับเป็นจริง;
กลับเท็จ;
-
pre_p = cur_p;
-
ถ้า(ตรวจสอบ[ฐาน[cur_p]+GetCharCode(END_CHAR)] == cur_p)
กลับเป็นจริง;
กลับเท็จ;
-
//ฟังก์ชันภายในส่งคืนดัชนีฐานสุดท้ายของคำที่ตรงกัน
classFindStruct
-
อินท์พี;
คำนำหน้าสตริง = "";
-
FindStruct ค้นหาส่วนตัว (คำสตริง)
-
int pre_p = 1;
int cur_p = 0;
FindStruct fs = FindStruct ใหม่ ();
สำหรับ(int i=0;i<word.length();++i)
-
// บั๊ก
fs.prefix += word.charAt(i);
cur_p = ฐาน[pre_p]+GetCharCode(word.charAt(i));
ถ้า (ตรวจสอบ [cur_p] != pre_p)
-
fs.p = -1;
กลับ fs;
-
ถ้า (ฐาน [cur_p] < 0)
-
ถ้า(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 สาธารณะ GetAllChildWord (ดัชนี int)
-
ArrayList<String> result = new ArrayList<String>();
ถ้า (ฐาน [ดัชนี] == 0)
-
result.add("");
ส่งคืนผลลัพธ์;
-
ถ้า (ฐาน [ดัชนี] < 0)
-
สตริง r="";
สำหรับ (int i=-Base[ดัชนี];หาง[i]!=END_CHAR;++i)
-
r+= หาง[i];
-
result.add(r);
ส่งคืนผลลัพธ์;
-
สำหรับ(int i=1;i<=CharMap.size();++i)
-
ถ้า (ตรวจสอบ [ฐาน [ดัชนี] + i] == ดัชนี)
-
สำหรับ (สตริง s:GetAllChildWord(ฐาน [ดัชนี]+i))
-
result.add(CharList.get(i)+s);
-
//result.addAll(GetAllChildWord(ฐาน[ดัชนี]+i));
-
-
ส่งคืนผลลัพธ์;
-
ArrayList สาธารณะ FindAllWords (คำสตริง)
-
ArrayList<String> result = new ArrayList<String>();
คำนำหน้าสตริง = "";
FindStruct fs = ค้นหา (คำ);
int p = fs.p;
ถ้า (p == -1) ส่งคืนผลลัพธ์;
ถ้า(ฐาน[p]<0)
-
สตริง r="";
สำหรับ (int i=-Base[p];Tail[i]!=END_CHAR;++i)
-
r+= หาง[i];
-
result.add(fs.prefix+r);
ส่งคืนผลลัพธ์;
-
ถ้า(ฐาน[p] > 0)
-
ArrayList<String> r = GetAllChildWord(p);
สำหรับ(int i=0;i<r.size();++i)
-
r.set(i, fs.prefix+r.get(i));
-
กลับ r;
-
ส่งคืนผลลัพธ์;
-
-
รหัสทดสอบ:
คัดลอกรหัสรหัสดังต่อไปนี้:
นำเข้า 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 (String [] args) พ่นข้อยกเว้น {
ArrayList<String> คำ = ใหม่ ArrayList<String>();
BufferedReader reader = new BufferedReader(InputStreamReader ใหม่ (FileInputStream ใหม่ ("E:/Rabbit's Experimental Learning Center [ในชั้นเรียน]/การแข่งขัน ACM/การแข่งขัน ACM 4th School/E Command Prompt/words3.dic")));
สตริง;
จำนวน int = 0;
ในขณะที่((s=reader.readLine()) != null)
-
คำ. เพิ่ม (s);
หมายเลข++;
-
DoubleArrayTrie dat = DoubleArrayTrie ใหม่ ();
สำหรับ (คำสตริง: คำ)
-
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(คำ));
-
-
-
ต่อไปนี้คือผลการทดสอบ ซึ่งจะใช้เวลาประมาณ 20 วินาทีในการสร้างคำภาษาอังกฤษขนาด 6W
เมื่อฉันขยายอาร์เรย์ ความยาวจะเพิ่มขึ้นเป็น 2 ครั้งในแต่ละครั้ง โดยเริ่มแรกคือ 1,024
ความยาวของอาร์เรย์ฐานและเช็คคือ 131072
ความยาวของหางคือ 262144
ทีทีที1