شجرة البادئة مع فهارس الصورة النقطية

منذ وقت ليس ببعيد ، كنت بحاجة إلى تنفيذ وظيفة تم تنفيذها بالفعل من قبل أشخاص آخرين وأكثر من مرة ، لكنها لم تناسب بعض الخصائص. في هذه الحالة ، كان مطلوبًا نوعًا ما من بنية البيانات مع القدرة على البحث بواسطة مفتاح سلسلة أو عدة أحرف أولية للمفتاح. المفتاح هو سلسلة من الحروف اللاتينية في أي حال ، المسافات والأرقام.

تطبيقات أخرى لا تتناسب ، أولاً وقبل كل شيء ، على الذاكرة المستهلكة. وعلى أي حال ، لن يكون تطبيق آخر لشجرة البادئة ضروريًا.

ربما كانت الفكرة مستوحاة من هذه المقالة ، حيث تقرر استخدام فهرس الصورة النقطية لفهرسة الارتباطات إلى العقد اللاحقة في العقدة.

من الواضح أن عدد الروابط في عقدة واحدة لا يمكن أن يزيد عن 63 (10 أرقام ، 26 حرفًا في كل حالة ، بالإضافة إلى مسافة). لذلك ، للحصول على فهرس نقطية ، يتم استخدام رقم 64 بت في كل عقدة. تعني مجموعة البت في أي موضع وجود الرمز والعقدة المقابلة (الشجرة الفرعية).

يكون التوزيع في فهرس الصورة النقطية كما يلي: تشغل الأرقام من 0 إلى 9 من 0 إلى 9 بتات ، والحروف az من 10 إلى 35 بت ، والأحرف AZ من 36 إلى 62 بت ، وتشغل المساحة 63 بت. للحصول على رقم البت ، يتم استخدام رمز حرف ASCII ببساطة ، ويتم تخفيضه بعدد معين. يختلف الرقم بالنسبة لكل نطاق من الأحرف: بالنسبة للأرقام 48 (يبدأ نطاق الأرقام في أكواد ASCII بـ 48) ، وللأحرف az 87 (يبدأ نطاق الأحرف az بـ 10 بتات تحت الصفر ، ويشغلها بالفعل 10 أرقام) وهكذا.

الجدول المقابل موضح أدناه.


العقدة ممثلة بالرمز أدناه:

type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} } 

وبالتالي ، تخزن كل عقدة فهرس الصورة النقطية للأحرف التالية وشريحة بها ارتباطات إلى مجموعات فرعية والبيانات نفسها. سوف أخبر بإيجاز عن آليات البحث والإدخال والحذف.

عند إدخال الإدخال ، يمر المفتاح رمزًا عبر الشجرة ، بدءًا من عقدة الجذر. لكل حرف من شفرة ASCII الخاصة به ، يتم حساب رقم البت ، ويتم احتساب الفهرس على أساسه في شريحة الروابط (محاولات فرعية) إلى الأشجار الفرعية. قيمة الفهرس هي عدد البتات قبل البتة المطلوبة. على سبيل المثال ، لدينا مثل هذا الفهرس: 00 ... 101. هذا يعني أنه في فهرس الصورة النقطية يوجد رقمان 0 و 2. ثم سيكون الرقم للرقم 0 صفراً ، والرقم 2 سيكون 1 ، أي ، ستحاول subTries 2 ارتباطات إلى الأشجار الفرعية: subTries [0] و subTries [1] .

الكود للحصول على رقم البت للحرف:

 func calcBitNum(char rune) (uint64, bool) { // Characters az use bit positions 10-35 if char > 96 && char < 123 { return uint64(char - 87), true } // Characters AZ use bit positions 36-61 if char > 64 && char < 91 { return uint64(char - 29), true } // digits 0-9 use bit positions 0-9 if char > 47 && char < 58 { return uint64(char - 48), true } // space uses 62 bit position if char == 32 { return 62, true } return 0, false } 

الكود للحصول على فهرس العقدة للحرف:

 func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) } 

رمز الحصول على العقدة الخاصة بالحرف المعطى:

 func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum) // There is no subTrie under given character since the corresponding bit is zero if trie.characters&(1<<bitNum) == 0 { return bitNum, subTrieId, nil } return bitNum, subTrieId, trie.subTries[subTrieId] } 

إدراج

يتم عبور شجرة لإدراج عنصر. في حالة فقد أي حرف (وبالتالي كل الأحرف اللاحقة) ، يتم إدراجه في فهرس الصورة النقطية. يتم إنشاء شجرة فرعية ، يتم إدراج الارتباط الذي تم إدخاله في المكان الصحيح لمحاولة الشرائح الفرعية (يتم تحديد المكان الصحيح بعدد البتات إلى الرقم المطلوب). عندما وصلوا إلى الحرف الأخير من المفتاح ، يتم إدراج البيانات في الشجرة الفرعية الأخيرة.

بحث

للبحث ، المفتاح رمزي "يعمل" عبر الشجرة. بمجرد انتهائها ، يتم إرجاع النتيجة. إذا لم تكن هناك بيانات للمفتاح ، ولكن هناك المزيد من الأشجار الفرعية ، فسيتم اختيار النتائج من جميع الأشجار الفرعية اللاحقة التي تحتوي على بيانات. يمكن تعيين الحد الأقصى لعدد البيانات التي تم إرجاعها. وبالتالي ، من الممكن البحث عن عقدة واحدة عن طريق مصادفة المفتاح بأكمله ، أو مجموعة من العقد بالصدفة بين عدة أحرف أولية.

إزالة

جاء إجراء الإزالة أكثر تعقيدًا (كما هو متوقع) من الباقي. لحذف مفتاح ، يتم اجتياز شجرة ، يتم خلالها تسجيل العقد التي لا تحتوي على بيانات في شريحة منفصلة. في حالة العثور على عقدة تحتوي على بيانات ، تتم إعادة تعيين الشريحة إلى الصفر ويستمر المرور عبر الشجرة. أي ، يجب أن تحتوي شريحة العقد للحذف على سلسلة من العقد التي لا تحتوي على بيانات. إذا لم تكن الشريحة فارغة في النهاية ، فستذهب بالترتيب العكسي وتتم إزالة البتات المقابلة من فهرس الصورة النقطية ويتم حذف العقد.

يؤدي

والنتيجة هي شجرة بادئة متفوقة على نظيراتها الأخرى في السرعة واستهلاك الذاكرة (في المتوسط ​​، 30 ٪ أقل في الذاكرة وأسرع بكثير). أيضًا ، لم أكن كسولًا جدًا في جعل العمليات ذات مؤشرات الترابط مع شجرة ممكنة ، مما يزيد الإنتاجية بشكل كبير ، لا سيما في عمليات البحث. بطبيعة الحال ، فإن الحل متخصص تمامًا (تحديد في شكل أحرف لاتينية وأرقام ومساحة كمكونات رئيسية).

بناءً على الغرض من شجرة البادئة ، يمكن استخدام هذا الحل لإنشاء قاموس ، فهرس البحث.

لم أذكر الاستشهاد بالرموز والبحث والبحث وحذف الرموز ، حتى لا أقوم بفوضى المقالة ، بالإضافة إلى أن الكود المصدري متاح في جيثب .