البادئة البحث في شجرة راديكس / باتريشيا تراي

Question

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

يستند تنفيذي على هذه المادة, ، ولكن الكود الخاص به لا يشمل عمليات البحث البادئة، على الرغم من أن المؤلف يقول:

...] قل أنك تريد تعداد جميع العقد التي تحتوي على مفاتيح بادئة مشتركة "AB". يمكنك إجراء بحث عميق أول بدء في هذا الجذر، توقف كلما واجهت حواف الظهر.

لكنني لا أرى كيف يفترض أن يعمل ذلك. على سبيل المثال، إذا قمت ببناء شجرة Radix من هذه الكلمات:

مرض
وهمي
خيال
يتصور
تقليد
مباشر
فورا
هائل
في

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

بالإضافة إلى ذلك، هناك تنفيذ شجرة radix في جافا يحتوي على البادئة المنفذة في البحث في radixtreeimpl.java.. وبعد يتحقق هذا الرمز صراحة جميع العقد (بدءا من عقدة معينة) لتطابق البادئة - فهو يقارن بالفعل بايت.

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

Answer 1

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

• Λ
• λ → "أنا"

في عقدة "أنا"، هناك طفلان، واحد ل "م" وواحد ل "n". الحرف التالي هو "ن"، لذلك تأخذ ذلك،

• λ → "أنا" → "n"

وبما أن الكلمة الوحيدة التي تبدأ "i"، "n" في مجموعة البيانات الخاصة بك يكون "في"، لا يوجد أطفال من "ن". هذه مباراة.

الآن، دعنا نقول مجموعة البيانات، بدلا من وجود "in"، كان "Infindibulum". (ما هي SF التي أشير إليها، يترك كممارسة.) كنت لا تزال تحصل على عقدة "n" بنفس الطريقة، ولكن بعد ذلك إذا كانت الحرف التالي الذي تحصل عليه هو "q"، فأنت تعرف أن الكلمة لا تظهر في مجموعة البيانات الخاصة بك على الإطلاق، لأنه لا يوجد فرع "Q". في تلك المرحلة، تقول "حسنا، لا تطابق". (ربما تبدأ بعد ذلك بإضافة الكلمة، ربما لا، اعتمادا على التطبيق.)

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

كيف تستخدمك ذلك؟ في الكثير من مترجمي الأمر غير اليونكس، مثل VAX DCL القديم، يمكنك استخدام أي بادئة فريدة من أمر أمر. لذلك، ما يعادل LS (1) كنت DIRECTORY, ، ولكن لا يوجد أمر آخر بدأ مع DIR، حتى تتمكن من الكتابة DIR وكان ذلك جيدا كما تفعل الكلمة كلها. إذا لم تتمكن من تذكر الأمر الصحيح، فيمكنك كتابة "D '، وضرب (أعتقد) ESC؛ سوف يعيدك DCL CLI الكل الأوامر التي بدأت D, ، والتي يمكن أن تبحث بسرعة كبيرة.

Answer 2

اتضح أن امتدادات جنو ل Lib القياسية C ++ تتضمن تنفيذ Trie Patricia. تم العثور عليه تحت امتداد هياكل البيانات القائمة على السياسة. يرى http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html.

Answer 3

خوارزمية بديلة: احتفظ بها بسيطة غبية!

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

ستتطلب هذه الخوارزمية فقط 5٪ فقط من رمز باتريشيا Trie وسوف يكون من السهل الحفاظ عليها وفهمها وتحديثها. من شبه المؤكد أن هذه البحث قائمة بسيطة ستكون أكثر فعالية أيضا.

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

Answer 4

Algo بديل آخر هو شجرة البحث الثغرية (المزيد من الذاكرة كفاءة) https://github.com/varunpant/ernarytree/tree/master/ernarytree.