الگوریتم هافمن یک الگوریتم فشرده سازی و کد کردن داده هاست که داده های
ورودی خود را بین 20 تا 90 درصد فشرده می کند . در کل ایده ی اصلی این اگوریتم
این است که به کاراکترهایی از متن که بیشترین تکرار را دارند ، کد کوتاه تری را
اختصاص می دهد . یعنی :        تکرار بیشتر -> کد کوتاهتر
شاید اینطور به نظر برسد که وقتی یک کاراکتر را بر میداریم و جای آن یک کد چند
کاراکتری قرار می دهیم ، باعث افزایش حجم داده ها شویم ! این از لحاظ منطقی
درست است اما در واقع این اتفاق نمی افتد ؛ زیرا صفر و یک های تولید شده توسط
هافمن کاراکتر صفر و یک نیستند بلکه بیت اند !
با در نظر گرفتن اینکه در حالت معمول کاراکتر های ما کد اسکی دارند و کد اسکی
8 بیتی است قابل توجیه است که چطور در نهایت بیت های کمتری خواهیم داشت ...
( فرض کنید که به جای یک کاراکتر پرتعداد با کد 8 بیتی در همه جای متن کد
0 را قرار دهیم )



و اما مراحل پیاده سازی این الگوریتم :
الگوریتم هافمن اصلا پیچیده نیست ، به شرط آنکه بتوانید فرآیند های آن را به چند
قسمت کوچک تر و قابل اجرا تقسیم کنید و یک روال منطقی بین قسمت های
مختلف ایجاد کنید . کاری که در کل باید انجام دهید این است :
1- کاراکتری های متن ورودی را بشمارید و کاراکتر را بهمراه تعداد آن در یک لیست
    ( می تواند آرایه باشد ) ذخیره کنید .
2- لیست کاراکتر-تعداد را بر اساس تعداد تکرار به صورت نزولی مرتب کنید.
3- با توجه به لیستی که ایجاد کردید درخت هافمن را برای این لیست ایجاد کنید .
    ( برای پیاده سازی درخت باید از لیست های پیوندی کمک بگیرید . هر نود این
      لیست سه اشاره گر دارد ؛  یکی به والد ، یکی به فرزند چپ و یکی به فرزند
      راست )
4- بعد از ایجاد درخت می توانید کد مربوط به هر کاراکتر را از درخت استخراج نمایید
    و یک لیست کاراکتر-کد ایجاد کنید.
5- تا این مرحله لیستی ایجاد کردیم که در آن برای هر کاراکتر یک کد منحصر به فرد
    وجود دارد . حال کافیست که متن ورودی را دوباره خوانده و با استفاده از لیست
    کاراکتر-کد به جای هر کاراکتر کد کربوط به آن را قرار دهیم.

در طی این 5 مرحله کلیه ی فرآیند های مربوط به پیاده سازی این الگوریتم مشخص
شد . حال کافی ست یکمی از هنر برنامه نویسی خود را بروز داده و این 5 کار را به
 ترتیب انجام دهید .


و اما در مورد خود درخت :
این حرفی که میگم شاید خیلی ساده به نظر بیاد اما حقیقت واقعا به همین سادگی
هستش اینجا خیییلی از برنامه هایی که ما اون ها رو ایجاد می کنیم دقیقا بر مبنای
همون کاری هست که به صورت دستی انجامش میدیم . با همین دید ساده و با توجه
به اینکه کمی در مورد لیست های پیوندی اطلاعات دارید ، به راحتی میشه این درخت
رو ایجاد کرد .

نکاتی که طی ایجاد این درخت برای من مطرح شد اینها بود :
1- وقتی می خواهیم درخت را روی کاغذ و با توجه به تعداد مشخص حروف رسم کنیم
    اون دو حرف با تعداد تکرار کمتر رو انتخاب می کنیم . برای اون ها برگ کشیده و
    حاصل جمع اونها رو در نود والد قرار می دهیم . ( دقت کنین که 2تا نود برداشتیم )
    از اینجا به بعد هر دفعه یک نود بر میداریم و با نود والد قبلی جمع کرده و یک والد
    جدید برای این دو تود فعی در نظر می گیریم ... همینطور ادامه می دهیم تا زمانی
    که دیگر حرفی باقی نماند
2- در درختی که در کلاس رسم شد ، 0 و 1 ها را روی شاخه های درخت قرار دادیم
    اما در درختی که ما ایجاد می کنیم شاخه به آن شکل وجود ندارد . پس 0 و 1 هر
    شاخه را به نمایندگی روی نودی در نظر میگیریم که شاخه به آن متصل شده است
   ( 0 و 1 هر شاخه روی نود پایینی )
3- برای پیمایش این درخت نمی توان از شیوه های معمول استفاده کرد . شیوه ای
    که من استفاده کردم این است که از  برگ هایی از درخت که نشان دهنده ی یک
    کاراکتر خاص می باشند ، درخت را به سمت بالا تا ریشه پیمایش کنیم و 0 و 1
    هایی را که قبلا روی نود ها ( موقع ساخت درخت ) در نظر گرفتیم را جمع کنیم .
4- در دنیای واقعی برای خواندن یک کد از درخت از بالا به پایین می خواندیم ( از ریشه
    تا برگ ) اما در روش بالا ناچارا از برگ تا ریشه صفر و یک ها را جمع کردیم . پس
    کد برعکس است . با استفاده از یک پشته به راحتی می توانیم کد را معکوس
    کنیم .
    ( کافی ست کد را در پشته Push کنیم و در نهایت پشته را کلا Pop نماییم ! )


فعلا دیگه چیزی به ذهنم نمیرسه !!!
اگه سوالی بود بپرسین  

پ.ن 1: من همیشه از شیوه ی شکستن برای نوشتن برنامه هام استفاده می کنم .
            یعنی مسأله را به قسمت های کوچکتر تقسیم و برای آن راه حل پیدا می
           کنم . این مراحل هم دقیقا با همین دید ایجاد شده است.
پ.ن 2: میدونم که این پست خیلی کلی بود اما خب توی یک راهنمایی که کل جواب
            رو ذکر  نمی کنن دیگه :دی
           اما مراحل کار دقیقا همینه ! اگر کد همین رو بنویسین جواب میگیرین