إن تطبيق Trie التقليدي سهل التنفيذ، لكن المساحة التي تشغلها غير مقبولة حقًا، خاصة عندما لا تقتصر مجموعة الأحرف على 26 حرفًا إنجليزيًا، فإن المساحة المنفجرة غير مقبولة بكل بساطة.
المصفوفة المزدوجة Trie عبارة عن شجرة Trie مُحسَّنة للمساحة ولن يتم مناقشة المبدأ في هذه المقالة، يرجى الرجوع إلى التنفيذ الفعال لهياكل Trie. تمت كتابة هذا البرنامج أيضًا بالإشارة إلى هذه الورقة.
فيما يتعلق بعدة تفاصيل لم تذكر في الورقة وتطبيقات تتعارض مع الورقة:
1. لإدراج سلاسل، إذا كانت السلسلة عبارة عن سلسلة فرعية من سلسلة أخرى، فسوف أستخدم أيضًا أداة الإنهاء كحافة لإنشاء عقدة جديدة وسأقوم بتعيين قاعدة العقدة الجديدة على 0.
لذلك، هناك حالتان في نهاية السلسلة: الأول هو أن القيمة الأساسية سالبة وأن الأحرف المتبقية (ربما نهاية واحدة فقط) مخزنة في المصفوفة الخلفية؛ والأخرى هي أن القاعدة هي 0.
لذلك، يجب عليك مراعاة هذين الموقفين عند إجراء الاستفسارات.
2. بالنسبة للنوع الأول من التعارض (الحالة 3 في الورقة)، قد يكون من الضروري إخراج جزء من الخيط في الذيل ووضعه في الفهرس كحافة. تستخدم الورقة طريقة نقل سلسلة الذيل إلى اليسار. تقوم طريقتي بتعديل القيمة الأساسية مباشرة بدلاً من تحريك سلسلة الذيل.
ما يلي هو الكود الذي تم تنفيذه في جافا، والذي يمكنه التعامل مع إدراج نفس السلسلة، وإدراج سلاسل فرعية، وما إلى ذلك.
انسخ رمز الكود كما يلي:
/*
* الاسم: مصفوفة مزدوجة
* المؤلف: ياجوانج دينج
* البريد: [email protected]
* المدونة: blog.csdn.net/dingyaguang117
* التاريخ: 2012/5/21
*ملاحظة: نهاية الكلمة قد تكون إحدى الحالتين التاليتين:
* 1. Base[cur_p] == pos ( pos<0 and Tail[-pos] == 'END_CHAR' )
* 2. تحقق من [Base[cur_p] + Code('END_CHAR')] == cur_p
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
استيراد java.util.Arrays؛
الطبقة العامة DoubleArrayTrie {
الحرف النهائي END_CHAR = '/0'؛
العدد النهائي DEFAULT_LEN = 1024؛
int Base[] = new int [DEFAULT_LEN];
int Check[] = new int [DEFAULT_LEN];
char Tail[] = new char [DEFAULT_LEN];
إنت بوس = 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);
ل(int i=0;i<26;++i)
{
CharMap.put((char)('a'+i),CharMap.size()+1);
CharList.add((شار)('a'+i));
}
}
الفراغ الخاص Extend_Array ()
{
Base = Arrays.copyOf(Base, Base.length*2);
Check = Arrays.copyOf(Check, Check.length*2);
}
الفراغ الخاص Extend_Tail ()
{
Tail = Arrays.copyOf(Tail, Tail.length*2);
}
int الخاص GetCharCode (شار ج)
{
إذا (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
إرجاع CharMap.get(c);
}
int الخاص CopyToTailArray(String s,int p)
{
int _Pos = Pos;
بينما (s.length()-p+1 > Tail.length-Pos)
{
Extend_Tail();
}
ل(int i=p;i<s.length();++i)
{
Tail[_Pos] = s.charAt(i);
_Pos++;
}
إرجاع _Pos؛
}
كثافة العمليات الخاصة x_check(عدد صحيح []مجموعة)
{
ل(int i=1; ; ++i)
{
علامة منطقية = صحيح؛
ل(int j=0;j<set.length;++j)
{
int cur_p = i+set[j];
if(cur_p>= Base. length) Extend_Array();
إذا (قاعدة[cur_p]!= 0 || تحقق[cur_p]!= 0)
{
العلم = خطأ؛
استراحة؛
}
}
إذا (العلم) العودة أنا؛
}
}
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;
إذا (تحقق [قاعدة [p]+i] == ص)
{
ret.add(i);
}
}
عودة متقاعد؛
}
TailContainString المنطقية الخاصة (int start، String s2)
{
ل(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
عودة صحيحة؛
}
سلسلة TailMatchString المنطقية الخاصة (بداية int، سلسلة s2)
{
s2 += END_CHAR;
ل(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
عودة صحيحة؛
}
إدراج الفراغ العام (سلسلة s) يطرح استثناء
{
ث += END_CHAR;
int pre_p = 1;
int cur_p;
ل(int i=0; i<s.length(); ++i)
{
// احصل على موقع الحالة
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
// إذا تجاوز الطول الطول الحالي، قم بتوسيع المصفوفة
if (cur_p >= Base. length) Extend_Array();
// حالة الخمول
إذا (Base[cur_p] == 0 && تحقق[cur_p] == 0)
{
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
استراحة؛
}آخر
//الحالة الحالية
إذا (Base[cur_p] > 0 && تحقق[cur_p] == pre_p)
{
pre_p = cur_p;
يكمل؛
}آخر
// الصراع 1: عندما يكون Base[cur_p] أقل من 0، فإنه يواجه سلسلة مضغوطة ومخزنة في Tail.
إذا (Base[cur_p] < 0 && تحقق[cur_p] == pre_p)
{
int head = -Base[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)// أدخل سلسلة متكررة
{
استراحة؛
}
// في حالة الحروف المشتركة، لأن الحكم الأخير قد استثنى النهي، فيجب ألا يكون كلاهما نهيًا.
إذا (الذيل [الرأس] == 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;
يكمل؛
}
آخر
{
// إذا لم يكن الحرفان متماثلين، فقد يكون أحدهما هو الإنهاء.
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;
// الذيل هو END_FLAG
إذا (الذيل [الرأس] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
آخر
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
إذا (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: العقدة الحالية مشغولة بالفعل وتحتاج القاعدة المسبقة إلى التعديل.
إذا (تحقق [cur_p]! = pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> list = 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;
ل(int j=0; j<list.size(); ++j)
{
//حشرة
int tmp1 = Origin_base + list.get(j);
int tmp2 = avail_base + list.get(j);
Base[tmp2] = Base[tmp1];
Check[tmp2] = Check[tmp1];
// هناك متابعة
إذا (قاعدة [tmp1] > 0)
{
ArrayList<Integer> subsequence = 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));
إذا (s.charAt(i) == END_CHAR)
قاعدة[cur_p] = 0;
آخر
Base[cur_p] = -Pos;
Check[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 = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p]!= pre_p) يُرجع false;
إذا (قاعدة [cur_p] <0)
{
إذا (TailMatchString(-Base[cur_p]،word.substring(i+1)))
عودة صحيحة؛
عودة كاذبة.
}
pre_p = cur_p;
}
إذا (تحقق من [Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
عودة صحيحة؛
عودة كاذبة.
}
// وظيفة داخلية، تُرجع آخر فهرس أساسي للكلمة المطابقة،
classFindStruct
{
كثافة العمليات ع؛
بادئة السلسلة = ""؛
}
FindStruct خاص البحث (كلمة سلسلة)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
ل(int i=0;i<word.length();++i)
{
// حشرة
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
إذا (تحقق [cur_p]!= pre_p)
{
fs.p = -1;
عودة خ م؛
}
إذا (قاعدة [cur_p] <0)
{
إذا (TailContainString(-Base[cur_p]،word.substring(i+1)))
{
fs.p = cur_p;
عودة خ م؛
}
fs.p = -1;
عودة خ م؛
}
pre_p = cur_p;
}
fs.p = cur_p;
عودة خ م؛
}
ArrayList العامة <String> GetAllChildWord (مؤشر int)
{
ArrayList<String> result = new ArrayList<String>();
إذا (القاعدة [الفهرس] == 0)
{
result.add("");
نتيجة الإرجاع؛
}
إذا (قاعدة [الفهرس] <0)
{
سلسلة ص = ""؛
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= الذيل[i];
}
result.add(r);
نتيجة الإرجاع؛
}
for(int i=1;i<=CharMap.size();++i)
{
إذا (تحقق من [Base[index]+i] == Index)
{
for(String s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
نتيجة الإرجاع؛
}
ArrayList العامة <String> FindAllWords (كلمة سلسلة)
{
ArrayList<String> result = new ArrayList<String>();
بادئة السلسلة = ""؛
FindStruct fs = Find(word);
int p = fs.p;
إذا (ع == -1) إرجاع النتيجة؛
إذا (قاعدة [ع]<0)
{
سلسلة ص = ""؛
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= الذيل[i];
}
result.add(fs.prefix+r);
نتيجة الإرجاع؛
}
إذا (قاعدة [ع] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
ل(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
العودة ص؛
}
نتيجة الإرجاع؛
}
}
رمز الاختبار:
انسخ رمز الكود كما يلي:
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
استيراد java.io.InputStream؛
استيراد java.io.InputStreamReader؛
import java.util.ArrayList;
استيراد java.util.Scanner؛
استيراد javax.xml.crypto.Data؛
الطبقة العامة الرئيسية {
public static void main(String[] args) يطرح الاستثناء {
ArrayList<String>words = new ArrayList<String>();
BufferedReader Reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Rabbit's Experimental Learning Center [In-class]/ACM المنافسة/ACM مسابقة المدرسة الرابعة/E Command Prompt/words3.dic")));
سلسلة ق؛
عدد صحيح = 0؛
بينما ((s=reader.readLine()) != فارغة)
{
word.add(s);
رقم++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
ل(كلمة السلسلة: كلمات)
{
dat.Insert(word);
}
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(word));
System.out.println(dat.FindAllWords(word));
}
}
}
فيما يلي نتائج الاختبار. يستغرق إنشاء DAT من الكلمات الإنجليزية 6W حوالي 20 ثانية.
عندما أقوم بتنمية المصفوفة، يزداد الطول مرتين في كل مرة، في البداية 1024
طول المصفوفة الأساسية والتحقق هو 131072
طول الذيل 262144
TTT1