كيف يمكنني الاختيار بين جدول التجزئة وTrie (شجرة البادئة)؟

Question

لذلك، إذا كان علي الاختيار بين جدول التجزئة أو شجرة البادئة، فما هي العوامل التمييزية التي قد تقودني إلى اختيار أحدهما على الآخر.من وجهة نظري الساذجة، يبدو كما لو أن استخدام محاولة له بعض الحمل الإضافي لأنه لا يتم تخزينه كمصفوفة ولكن من حيث وقت التشغيل (بافتراض أن أطول مفتاح هو أطول كلمة إنجليزية) يمكن أن يكون O بشكل أساسي (١) (بالنسبة إلى الحد الأعلى).ربما أطول كلمة إنجليزية هي 50 حرفا؟

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

هل يمكن لأي شخص أن يقدم لي وجهة نظر أكثر خبرة في هذا الشأن؟شكرًا!

Answer 1

مزايا المحاولات:

أساسيات:

• وقت البحث O(k) المتوقع حيث k هو حجم المفتاح
• يمكن أن يستغرق البحث أقل من k من الوقت إذا لم يكن موجودًا
• يدعم اجتياز أمر
• لا حاجة لوظيفة التجزئة
• الحذف واضح ومباشر

العمليات الجديدة:

• يمكنك البحث بسرعة عن بادئات المفاتيح، وتعداد كافة الإدخالات ببادئة معينة، وما إلى ذلك.

مزايا الهيكل المرتبط:

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

مزايا الهاشتابل:

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

Answer 2

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

Answer 3

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

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

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

Answer 4

استخدم شجرة:

1. إذا كنت بحاجة إلى ميزة الإكمال التلقائي
2. ابحث عن جميع الكلمات التي تبدأ بـ "a" أو "ax" وما إلى ذلك.
3. الشجرة اللاحقة هي شكل خاص من الشجرة.تتمتع الأشجار اللاحقة بقائمة كاملة من المزايا التي لا يمكن للتجزئة تغطيتها.

Answer 5

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

ملاحظة.: بخلاف هؤلاء، أشجار البحث الثلاثية (TSTs) سيكون اختيارا ممتازا.وقت البحث الخاص به أطول من HashTable، ولكنه فعال من حيث الوقت في جميع العمليات الأخرى.كما أنها أكثر كفاءة في استخدام المساحة من المحاولات.

Answer 6

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

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

Answer 7

والإدراج والبحث على TRIE خطي مع lengh من O سلسلة الإدخال (ق).

وتجزئة سوف اعطيكم O (1) لإدخال بحث الجواب، ولكن أولا عليك أن حساب تجزئة استنادا إلى سلسلة الإدخال وهو مرة أخرى O (ق).

وConclussion، وتعقيد الوقت مقارب غير الخطية في كلتا الحالتين.

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

لكسر التعادل اسأل نفسك هذا السؤال: هل أنا بحاجة لبحث عن كلمات كاملة فقط؟ أو هل أنا بحاجة إلى إعادة جميع الكلمات مطابقة بادئة؟ (كما هو الحال في نظام الإدخال التنبئي للنص). وبالنسبة للحالة الأولى، انتقل للتجزئة. ذلك هو رمز أبسط وأكثر نظافة. أسهل لاختبار وصيانة. لحالة استخدام أكثر ellaborated حيث البادئات أو sufixes المسألة، تذهب لTRIE.

وإذا كنت تفعل ذلك لمجرد التسلية، وتنفيذ TRIE من شأنه أن يضع بعد ظهر اليوم الاحد لحسن استخدامها.

Answer 8

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