کدگذاری هافمن
از ویکیپدیا، دانشنامهٔ آزاد
 |
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه آن را تغییر دهید. در پایان، پس از ویکیسازی این الگوی پیامی را بردارید. |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
درعلوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن یک الگوریتم کدگذاری برای فشردهسازی بیاتلاف اطلاعات است.
این تعبیر بر میگردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانههای مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشانهای مبدا بدست میآید. این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.
در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده میشود. روشی به نام کدهای بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته میشود. یعنی در این روش رشتهای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمیباشد.).در این روش کاراکترهای پرکاربرد تر با رشتههای بیتی کوتاهتری نسبت به آنهایی که کاربردشان کمتر است، نشان داده میشوند.
هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشانهای منفرد مبدا به رشتههای بیتی یکتا، هرگاه تعداد تکرار نمادهای اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجیهایی با اندازهٔ کمتر تولید میکند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام میداد.
برای مجموعهای از نمادها با توزیع احتمالی یکنواخت و تعداد عضوهایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجملهای است. مانند کد گذاری ASCII. کد گذاری هافمن روشی متداول برای ایجاد کدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده میشود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.
اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینهاست، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته میشود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی توانایی بالاتری در فشرده سازی دارند.
فهرست مندرجات |
[ویرایش] تاریخچه
در سال ۱۹۵۱ David.A.Huffman و هم شاگردیهایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کندکه ایدهای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
[ویرایش] تعریف مساله
[ویرایش] توضیح غیر رسمی
داریم: مجموعهای از نمادها و وزن هایشان (معمولا متناسب با احتمالها یشان)
پیدا کنید: کد دودویی بدون پیشوند، (مجموعهای از کدها) با کمترین امید ریاضی برای طول کد.(به طور معادل، درختی با کمترین مسیر وزن دار)
تاریخچه در سال ۱۹۵۱ David.A.Huffman و هم شاگردیهایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کندکه ایدهای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
[ویرایش] انواع
انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آنها از الگوریتمهایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیتهای خاص برای خروجی)استفاه میکنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چندجملهای هم نداشته باشد. لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درختهای کد و تجزیه برای کد کردن بی زیان اطلاعات» [۱] داده شدهاست.
[ویرایش] کد هافمن n تایی
الگوریتم کد هافمن n تایی از الفبای {۰, ۱,..., n − ۱} برای کد کردن پیامها و ساختن درخت n تایی استفاده میکند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش بررسی شده بود.
[ویرایش] کد هافمن انطباقی
نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه میکند. این به گونهای مربوط به خانوادهٔ الگوریتمهای LZ است.
[ویرایش] الگوریتم الگوی هافمن
بیشتر اوقات، وزنهای مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزنها و اضافه کردن آنها نیازمند است. الگوریتم الگو هافمن امکان استفاده از هر نوع وزنی را میدهد.(ارزش-تکرار-جفت وزن ها-وزنهای غیر عددی) و هر کدام از روشهای ترکیبی مختلف. اینگونه الگوریتمها میتوانند مسائل فشرده سازی دیگر را نیز حل کنند.
[ویرایش] کد هافمن با طول محدود
کد هافمن با طول محدود نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار میگیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد. الگوریتم بسته بندی-ادغام این مشکل را بوسیلهٔ یک الگوریتم حریصانه ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل میکند. پیچیدگی زمانی این الگوریتم O(nL), که L ماکزیمم طول یک کدکلمه(codeword)است.
هیچ الگوریتمی شناخته نشده که این کا را در زمان linear or linearithmic انجام دهد,بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.
[ویرایش] کد هافمن با ارزش حرفی متفاوت
در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعهای که کد ها از آن استخراج میشوند،ارزشی یکسان با بقیه دارد: کد کلمهای که طول آن N است ارزشی برابر N خواهد داشت ،مهم نیس که چند رقم آن 1 و چند رقم آن 0 است. وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام ، با کم کردن تعداد رقم های کل 2 چیز یکسانند. کد هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طول های غیر همسانی داشته باشند ، به خاطر خصوصیت های واسطهٔ انتقال. مثالی بر این ادعا،الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول میکشد ، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نماد های بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
[ویرایش] کد قانونی هافمن
اگر وزن های مربوط به ورودی های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که میتواند از طریق محاسبه بدست آید. کد بدست آمده از ورودی های مرتب شده از نظر عددی ، کد قانونی هافمن گفته میشود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی ،در عمل استفاده میشود. تکنیک پیدا کردن این کد ، اکثرا کد گذاری Huffman-Shannon-Fano نامیده میشود. و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن ها مانند کد گذاریShannon-Fano coding الفبایی است. کد هافمن Shannon-Fano مربوط به این مثال {000,001,01,10,11} است که در آن طول کد کلمهها ، همان مقداری است که در حل اصلی آمده است.
[ویرایش] جستارهای وابسته
- کد اصلاحشدهٔ هافمن به کار رفته درماشینهای فکس
- فشردهسازی اطلاعات
- لمپل-زیو-ولچ
- سیستمهای دودویی نامتقارن
[ویرایش] منابع
- مقالهٔ اصلی هافمن: D.A. Huffman, «روشی برای ارائهٔ کدی با کمترین میزان حشو و زوائد»
- ویکیپدای انگلیسی
[ویرایش] پیوند به بیرون
 |
در ویکیانبار منابعی در رابطه با موجود است. |
- Program for explaining the Huffman Coding procedure.
- Huffman Code Applet
- n-ary Huffman Template Algorithm
- Sloane A۰۹۸۹۵۰ Minimizing k-ordered sequences of maximum height Huffman tree
- Computing Huffman codes on a Turing Machine
- Mordecai J. Golin, Claire Kenyon, Neal E. Young «Huffman coding with unequal letter costs» (PDF), STOC ۲۰۰۲: ۷۸۵-۷۹۱
- Huffman Coding: A CS۲ Assignment a good introduction to Huffman coding
- A quick tutorial on generating a Huffman tree
- Pointers to Huffman coding visualizations
- Huffman in C
- Huffman in Java
- Huffman binary algorithm applet
- Implementation approaches to Huffman Decoding
