البحث الفعال عن شجرة هوفمان مع تذكر المسار الذي سلكته

Question

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

وهذا ما لدي حاليا:

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

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

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

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

Answer 1

أنشئ قاموسًا ذا قيمة -> سلسلة بت، مما يمنحك أسرع عملية بحث.

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

Answer 2

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