کدگذاری هافمن: تفاوت میان نسخه‌ها

در[[علوم کامپیوتر]] و [[نظریه اطلاعات|تئوری اطلاعات]]، '''کد‌گذاریکدگذاری هافمن''' یک [[الگوریتم کد‌گذاریکدگذاری]] برای [[فشرده‌سازی بی‌اتلاف اطلاعات]] است.

در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام [[کد‌هایکدهای بدون پیشوند]](گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌هایکاراکترهای پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌هاینمادهای اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند.

برای مجموعه‌ای از نمادها با [[توزیع احتمالی یکنواخت]] و تعداد عضو‌هاییعضوهایی برابر با [[توانی از ۲]]، کد گذاری هافمن هم ارز با [[قطعه کد]] سادهٔ دوجمله‌ای است. مانند کد گذاری [[ASCII]].

کد گذاری هافمن روشی متداول برای ایجاد کد‌هایکدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.

انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آنها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کد‌هایکدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاه می‌کنند.

در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی [[چند‌جمله‌ایچندجمله‌ای]] هم نداشته باشد.

[[رده:نظریه کد‌گذاریکدگذاری]]

[[رده:درخت‌های دو‌دوئیدودوئی]]