کدگذاری هافمن: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جز ربات: اصلاح حمزهٔ بعد از "ه" |
جز ربات: اصلاح فاصله مجازی |
||
خط ۱۰۵:
=== کد هافمن با طول محدود ===
'''کد هافمن با طول محدود''' نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار
الگوریتم [[بسته بندی-ادغام]] این مشکل را بوسیلهٔ یک [[الگوریتم حریصانه]] ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل
پیچیدگی زمانی این الگوریتم <math>O(nL)</math>, که <math>L</math> ماکزیمم طول یک کدکلمه(codeword)است.
خط ۱۱۲:
=== کد هافمن با ارزش حرفی متفاوت ===
در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعهای که کد ها از آن استخراج
وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام ، با کم کردن تعداد رقم های کل 2 چیز یکسانند.
''کد هافمن با ارزش حرفی متفاوت'' به نحوی عمومیت یافته که این فرض دیگر صحیح نیست:
حروف الفبای کدگذاری ممکن است طول های غیر همسانی داشته باشند ، به خاطر خصوصیت های واسطهٔ انتقال.
مثالی بر این ادعا،الفبای کد گذاری [[کد مورس]] است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول
درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نماد های بکار برده شده در پیام، به تنهایی کافی نیست.
هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
خط ۱۲۲:
=== کد قانونی هافمن ===
اگر وزن های مربوط به ورودی های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که
کد بدست آمده از ورودی های مرتب شده از نظر عددی ، ''' کد قانونی هافمن ''' گفته
تکنیک پیدا کردن این کد ، اکثرا '''کد گذاری Huffman-Shannon-Fano ''' نامیده
و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن ها مانند کد گذاری[[Shannon-Fano coding]] الفبایی است.
کد هافمن Shannon-Fano مربوط به این مثال <math>\{000,001,01,10,11\}</math> است که در آن طول کد کلمهها ، همان مقداری است که در حل اصلی آمده است.
|