بهینه سازی الگوریتم هافمن با توسعه دو بخشی

الگوریتم هافمن با ایجاد یک درخت دودویی که از پایین به بالا ساخته می شود، این الگوریتم برای فشرده سازی مورد استفاده قرار می گیرد. از مسائل مهم در ایجاد درخت کدینگ هافمن بوجود آوردن درخت با حداقل ارتفاع میباشد که با کمینه کردن ارتفاع درخت در تولید کد-کلمه کوتاه تر موثر است. در مواقعی که متن مورد نظر دامنه اطلاعاتی وسیعی داشته باشد، مانند تصاویر، این درخت با افزایش ارتفاع درخت، کد-کلمه طولانی ایجاد می کندهمچنین یکنواختی فراوانی اطلاعات درنرخ فشردگی تاثیر منفی می گذارد، که در بعضی مواقع حجم فایل فشرده شده از حجم اصلی آن بیشتر هم میشود. برای جلوگیری از افزایش ارتفاع درخت می توان با اعمال محدودیت درتولید کد-کلمه با توسعه آن به دو بخش واندکی تغییردر درخت هافمن، بهینه سازی انجام داد. با اعمال این راهکار می توان ارتفاع درخت را کاهشداد.همچنین بخش پرتکرار را در سطوح پایینتری کد کرد. با انجام آزمایش بر روی تصویر پر تحرک بهینه سازی در الگوریتم هافمن مورد بررسی قرار می گیرد.

Keywords:

هافمن , فشرده سازی , محدودیت , دوبخشی , بهینه Algorithms , Coding Theory , Image Processing , سازی