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

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