تکنیک حریصانه در حل مسائل

روش هافمن

كد گذاري به روش هافمن روشي براي فشرده سازي داده ها است . به عبارت ديگر هدف اصلي كد هافمن کمينه سازي حجم داده است . اين روش زماني مطرح مي شود كه مثلا تعدادي حرف با تعداد تكرار معين داشته باشيم . در اين حالت در هر مرحله دو حرف ازحروف با كمترين تعداد تكرار را انتخاب كرده ، حرف با تعداد تكرار كمتر را به عنوان فرزند چپ و حرف با تعداد تكرار بيشتر را به عنوان فرزند راست و حاصل جمع تكرار ها را به عنوان گره والد در درخت قرار مي دهيم. سپس مجموع تكرار ها را به جاي آن دو حرف در دنباله حروف قرار داده و دوباره اين اعمال را تكرار مي كنيم. در انتها فرزندان چپ را  با 0 و فرزندان راست را با 1 علامت گذاري مي كنيم. با دنبال كردن درخت از ريشه تا گره مورد نظر كد جديد به دست مي آيد.

حل

اگر به حروف به ترتيب کدی از 000 تا101اختصاص دهيم يا به عبارت ديگر براي هر حرف 3بيت اختصاص دهيم تعداد بيتهاي مورد نياز براي نوشتن متني با تعداد تكرار فوق برابراست با:

تعداد بيت ها = 3Î(5+2+10+1+20+4) = 126

اما اگر از كد هافمن استفاده كنيم جواب متفاوت است . درخت هافمن به صورت زير است:

تمرين ها

.1ميزان كاهش حجم اطلاعات در حالت كلي چقدر است؟

.2روش ديكد كردن اطلاعات در گيرنده به چه صورت است؟

.3صحت الگوريتم را اثبات كنيد؟

.4پيچيدگي زماني وروش پياده سازي را بیان كنيد؟

.5پيچيدگي حافظه اي الگوريتم را محاسبه كنيد؟

.6كمترين و بيشترين طول كد هافمن به چه صورت است؟