كيف دليل على خوارزمية هوفمان الجشع المنشأة يبدأ الأمثل الشجرة ؟

Question

في هذه الورقة المطالبة 1 الدول التي x و y هي أصغر احتمال ، هناك الأمثل رمز الشجرة التي حرفين هي الأشقاء في أقصى العمق.في دليل على هذا الادعاء ، المؤلف يبدأ مع شجرة T الذي ب و ج في أقصى عمق شجرة.لا أستطيع أن أفهم لماذا شجرة T ويسمى الأمثل, لأنه إذا x و y يكون أصغر الاحتمالات ، ثم شجرة T لا يمكن أن يكون الأمثل لأن خوارزمية هوفمان لن تبني مثل هذه الشجرة.اعتقد ان المشكلة هنا مع فهم ما المثلى شجرة يعني.

إذا كان شخص ما يأتي من CSLR هذا هو يما 16.2 و دليل على ذلك.

Answer 1

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

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