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

محتوای حذف‌شده محتوای افزوده‌شده
Amirobot (بحث | مشارکت‌ها)
جز ربات: تصحیح کاما، شمارگان هزارگان
ابراهیم (بحث | مشارکت‌ها)
تمیزکاری + فاصله‌گذاری + فارسی‌سازی + کمی‌ویکی‌سازی
خط ۱:
[[پرونده:Huffman tree 2.svg|centerleft|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف های جملهٔ «this is an example of a huffman tree». تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، بدون در نظر گرفتن فاصله‌ها، به 135 بیت نیاز دارد.]]
{{ویکیسازی}}
{| class="wikitable sortable" style="float:left; clear:left;"
<div class="tleft">
 
{|
|-----
|
[[پرونده:Huffman tree 2.svg|center|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف های جملهٔ «this is an example of a huffman tree».تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، بدون در نظر گرفتن فاصله‌ها، به 135 بیت نیاز دارد.]]
|-----
|
{|
|-----
|
{| class="wikitable"
!حرف!!تکرار!!کد
|-
سطر ۴۶ ⟵ ۳۵:
|x ||۱||۱۰۰۱۰
|}
|}
|}
</div>
 
در[[علوم کامپیوتر]] و [[نظریه اطلاعات|تئوری اطلاعات]]، '''کدگذاری هافمن''' یک [[الگوریتم کدگذاری]] برای [[فشرده‌سازی بی‌اتلاف اطلاعات]] است.
 
این تعبیر بر می‌گردد به استفاده از جدول [[کد طول متغیر]] برای کد کردن هر کدام از نشانه‌های مبدا (مانند کاراکترهای[[نویسه]]‌های یک فایل[[پرونده (رایانه)|پرونده]]). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید.
این روش بوسیلهٔ [[دیوید هافمن]] توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه [[موسسهٔ تکنولوژی ماساچوست|MIT]] بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.
 
در کد کذاریکدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام [[کدهای بدون پیشوند]] (گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکترنویسه خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکترینویسهٔ دیگر است، نمی‌باشد.). در این روش کاراکترهای پرکاربردنویسه‌های ترپرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.
 
هافمن موفق شد کارآمدترین روش فشرده سازی از این نوع را طراحی کند:
نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نمادهای اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند.
بعدها روشی برای انجام این کار پیدا شد که این کار را در [[زمانی خطی]] انجام می‌داد.
 
برای مجموعه‌ای از نمادها با [[توزیع احتمالی یکنواخت]] و تعداد عضوهایی برابر با [[توانی از ۲]]، کد گذاری هافمن هم ارز با [[قطعه کد]] سادهٔ دوجمله‌ای است. مانند کد گذاری [[ASCIIاسکی (استاندارد)|اسکی]].
کد گذاری هافمن روشی متداول برای ایجاد کدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.
 
اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود.
برای مثال، [[کد کردن حسابی]] و کد کردن [[LZW]]،
گاهی توانایی بالاتری در فشرده سازی دارند.
 
 
== تاریخچه ==
در سال ۱۹۵۱ [[David.A.Huffman]] و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند. استاد [[Robert M. Fano]] موضوع تحقیق را مسالهٔ پیدا کردن کارآمدترین کد دودویی تعیین کرد.
 
در سال ۱۹۵۱ [[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 جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
 
== انواع ==
انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آنها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاه می‌کنند.
 
در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی [[چندجمله‌ای]] هم نداشته باشد.
لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی زیان اطلاعات» [http://scholar.google.com/scholar?hl=en&lr=&cluster=6556734736002074338] داده شده‌است.
 
=== کد هافمن ''n'' تایی ===
الگوریتم کد هافمن ''n'' تایی از الفبای {۰, ۱,... , ''n'' − ۱} برای کد کردن پیام‌ها و ساختن درخت n تایی استفاده می‌کند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش بررسی شده بود.
 
=== کد هافمن انطباقی ===
سطر ۱۰۲ ⟵ ۸۴:
بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آنها نیازمند است.
'''الگوریتم الگو هافمن''' امکان استفاده از هر نوع وزنی را می‌دهد.(ارزش-تکرار-جفت وزن ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی مختلف.
اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.
 
=== کد هافمن با طول محدود ===
'''کد هافمن با طول محدود''' نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد.
الگوریتم [[بسته بندی-ادغام]] این مشکل را بوسیلهٔ یک [[الگوریتم حریصانه]] ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند.
پیچیدگی زمانی این الگوریتم <math>O(nL)</math>، که <math>L</math> ماکزیمم طول یک کدکلمه(codeword)است.
 
الگوریتم [[بسته بندی-ادغام]] این مشکل را بوسیلهٔبه‌وسیلهٔ یک [[الگوریتم حریصانه]] ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند.
هیچ الگوریتمی شناخته نشده که این کا را در زمان [[Big O notation#Common orders of functions|linear or linearithmic]] انجام دهد، بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.
پیچیدگی زمانی این الگوریتم <math>O(nL)</math>، که <math>L</math> ماکزیمم طول یک کدکلمه (codeword)است.
 
هیچ الگوریتمی شناخته نشده که این کا را در زمان [[Big O notation#Common orders of functions|linear or linearithmic]] انجام دهد، بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.
 
=== کد هافمن با ارزش حرفی متفاوت ===
در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند، ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن ''N'' است ارزشی برابر ''N'' خواهد داشت، مهم نیس که چند رقم آن 1۱ و چند رقم آن 0۰ است.
وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقم‌های کل 2۲ چیز یکسانند.
''کد هافمن با ارزش حرفی متفاوت'' به نحوی عمومیت یافته که این فرض دیگر صحیح نیست:
حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند، به خاطر خصوصیت‌های واسطهٔ انتقال.
مثالی بر این ادعا، الفبای کد گذاری [[کد مورس]] است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد، پس ارزش خط تیره در زمان انتقال بالاتر است.
درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست.
هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
 
 
=== کد قانونی هافمن ===
اگر وزن‌های مربوط به ورودی‌های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید.
کد بدست آمده از ورودی‌های مرتب شده از نظر عددی ،عددی، ''' کد قانونی هافمن ''' گفته می‌شود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی، در عمل استفاده می‌شود.
تکنیک پیدا کردن این کد، اکثرا '''کد گذاری Huffman-Shannon-Fano ''' نامیده می‌شود.
و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن‌ها مانند کد گذاری[[Shannon-Fano coding]] الفبایی است.
کد هافمن Shannon-Fano مربوط به این مثال <math>\{000,001,01,10,11\}</math> است که در آن طول کد کلمه‌ها، همان مقداری است که در حل اصلی آمده است.
 
== جستارهای وابسته ==
 
* [[کد اصلاح‌شده هافمن|کد اصلاح‌شدهٔ هافمن]] به کار رفته در[[ماشین‌های فکس]]
* [[فشرده‌سازی اطلاعات]]
سطر ۱۳۶ ⟵ ۱۱۷:
 
== منابع ==
* مقالهٔ اصلی هافمن: D.A. Huffman, «روشی برای ارائهٔ کدی با کمترین میزان حشو و زوائد»
* ویکیپدای انگلیسی
 
* مقالهٔ اصلی هافمن: D.A. Huffman, «روشی برای ارائهٔ کدی با کمترین میزان حشو و زوائد»
* ویکیپدای انگلیسی
== پیوند به بیرون ==
{{انبار-رده|Huffman coding}}
سطر ۱۴۸ ⟵ ۱۲۸:
* [http://semillon.wpi.edu/~aofa/AofA/msg00040.html Computing Huffman codes on a Turing Machine]
* Mordecai J. Golin, Claire Kenyon, Neal E. Young «[http://www.cs.ust.hk/faculty/golin/pubs/LOP_PTAS_STOC.pdf Huffman coding with unequal letter costs]» (PDF), [http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2002.html STOC ۲۰۰۲]: ۷۸۵-۷۹۱
* [http://www.cs.duke.edu/csed/poop/huff/info/ Huffman Coding: A CS۲CS2 Assignment] a good introduction to Huffman coding
* [http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html A quick tutorial on generating a Huffman tree]
* Pointers to [http://web-cat.cs.vt.edu/AlgovizWiki/HuffmanCodingTrees Huffman coding visualizations]