کدگذاری هافمن: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات:اصلاح فاصلهٔ مجازی |
|||
خط ۵۷:
در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام [[کدهای بدون پیشوند]](گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکترهای پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آنهایی که کاربردشان کمتر است، نشان داده می‌شوند.
هافمن موفق شد
نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نمادهای اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند.
بعدها روشی برای انجام این کار پیدا شد که این کار را در [[زمانی خطی]] انجام می‌داد.
خط ۷۱:
== تاریخچه ==
در سال ۱۹۵۱ [[David.A.Huffman]] و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد [[Robert M. Fano]] موضوع تحقیق را مسالهٔ پیدا کردن
هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کندکه ایده‌ای به ذهنش رسید.
ایدهٔ استفاده از درخت دودیی مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این
در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، [[Claude Shannon]] برای ساختن کدی مشابه کار کرده بود، پیشی گرفت.
هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ [[Shannon-Fano coding]] جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
خط ۸۶:
تاریخچه
در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن
== انواع ==
خط ۱۱۲:
=== کد هافمن با ارزش حرفی متفاوت ===
در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعه‌ای که
وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام ، با کم کردن تعداد
''کد هافمن با ارزش حرفی متفاوت'' به نحوی عمومیت یافته که این فرض دیگر صحیح نیست:
حروف الفبای کدگذاری ممکن است
مثالی بر این ادعا،الفبای کد گذاری [[کد مورس]] است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد ، پس ارزش خط تیره در زمان انتقال بالاتر است.
درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد
هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
=== کد قانونی هافمن ===
اگر
کد بدست آمده از
تکنیک پیدا کردن این کد ، اکثرا '''کد گذاری Huffman-Shannon-Fano ''' نامیده می‌شود.
و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال
کد هافمن Shannon-Fano مربوط به این مثال <math>\{000,001,01,10,11\}</math> است که در آن طول کد کلمه‌ها ، همان مقداری است که در حل اصلی آمده است.
| |||