کدگذاری هافمن کیست؟ توضیح بده.
در علوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن (به انگلیسی: ) نوع مشخصی از کد پیشوندی (به انگلیسی: ) بهینه است که کاربردی فراوان در فشرده‌سازی بی‌اتلاف اطلاعات دارد. فرایند پیدا کردن یا استفاده از این کد، با بهره‌گیری از الگوریتمی انجام می‌شود که توسط «دیوید هافمن» (زمانی که وی دانشجوی دوره دکتری در دانشگاه MIT بود) توسعه داده شده‌است و برای اولین بار در سال ۱۹۵۲ در مقاله‌ای با عنوان «روشی برای تولید کدی با کمترین تکرار زوائد» منتشر شد.می‌توان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور یا فراوانی تکرار حروف در فایل منبع ایجاد شده‌است و مانند هر ی دیگر، حروف پرتکرار تر با تعداد بیت‌های کمتری نمایش داده می‌شوند.باید دقت کرد با توجه به کارایی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشرده‌سازی بهینه‌تری داشته باشیم، می‌توان از الگوریتم‌های کدگذاری حسابی یا سیستم‌های عددی نامتقارن استفاده کرد.تاریخچه.در سال ۱۹۵۱ میلادی، دیوید آ. هافمن و هم شاگردی‌هایش در کلاس تئوری اطلاعات در دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا شرکت در امتحان پایانی را داشتند. دکتر روبرتو فانو موضوع تحقیق را یافتن کارآمدترین کد دودویی تعیین کرد. هافمن که در ابتدا موفق به یافتن کارآمدترین کد نشده بود، تصمیم گرفت خودش را برای شرکت در امتحان پایانی آماده کند. که ایدهٔ استفاده از درخت دودیی مرتب شده برحسب فراوانی به ذهنش رسید. او در نهایت توانست اثبات کند که روش کارآمدترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، کلود شانون برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ رمزگذاری شانون-فانو جلوگیری کرد و درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.واژه‌شناسی.در کدگذاری هافمن، از روشی به نام کدهای بدون پیشوند (که به عنوان «کدهای پیشوندی» نیز شناخته می‌شود) برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. در این روش نویسه‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند. کدگذاری هفمن به اندازه‌ای پرکابرد است که کلمه «کد هافمن» به صورت گسترده به عنوان مترادفی برای کدهای پیشوندی استفاده می‌شود.تعریف مسئله.تعریف غیررسمی.داده‌های مسئله:مجموعه‌ای از نمادها (حروف و کاراکترها) به همراه وزن هر کدام. وزن هر حرف غالباً همان تعداد تکرار آن در فایل منبع است.خواسته:یافتن کد دودویی بدون پیشوند با کمترین امید ریاضی برای طول کد.تعریف رسمی.ورودی:مجموعه حروف formula_1 به طول formula_2مجموعه وزن‌ها formula_3 که نشان‌دهنده وزن هر نماد (حرف) از مجموعه حروف است به طوری که:formula_4خروجی:مجموعه کد (دودویی) formula_5 که هر عضو آن نشان‌دهنده کد متناسب با یکی از حروف در مجموعه formula_6 است.هدف:با تعریف formula_7 شرط بهینه بودن: formula_8 برای هر کدگذاری formula_9الگوریتم هافمن.اساس الگوریتم هافمن به این صورت است که دو عضو formula_10 و formula_11 که دو عضو از بین حرف‌هایی هستند که کمترین تکرار را بین حروف مجموعه formula_6 دارند، انتخاب می‌کنیم. حال مجموعه حروف جدید formula_13 را در نظر می‌گیریم که شامل تمام اعضای مجموعه formula_6 به جز دو عضو formula_10 و formula_11 است و جدید formula_17 را داراست. در این مجموعه حروف جدید، وزن همهٔ اعضا برابر با وزن قبلی آنها در مجموعه formula_6 است و وزن عضو formula_17 برابر با formula_20 خواهد بود. حال دوباره این الگوریتم را برای مجموعه جدیدformula_13 تکرار می‌کنیم.مراحل الگوریتم.اثبات بهینه بودن درخت کد حاصل از الگوریتم هافمن را می‌توانید در «درسنامه جلسه ۱۰ کلاس تحلیل الگوریتم‌ها دانشکده ریاضی دانشگاه صنعتی شریف»مطالعه کنید.پیچیدگی الگوریتم.الگوریتم هافمن اگر به صورت ساده گفته شده در بالا پیاده‌سازی شود، می‌توان به راحتی با استفاده از رابطه بازگشتی formula_29 نشان داد دارای پیچیدگی زمانی formula_30 است. اما می‌توان با استفاده از داده ساختار هرم الگوریتم را بهبود بخشید و پیچیدگی زمانی را به formula_31 کاهش داد. در پیاده‌سازی این الگوریتم به سه آرایه نیاز داریم و برای هر گره formula_32 در درخت، مقادیر فرزند راست formula_33، فرزند چپ formula_34 و والد formula_35 را در آن‌ها ذخیره می‌کنیم.شبه کد.&lt;syntaxhighlight&gt;function BuildHuffman(W) for i = 1 to n do L[i] &lt;- 0; R[i] &lt;- 0 InsertHeap(i, W[i]) for i = n to 2n - 1 do x &lt;- PopMinHeap() y &lt;- PopMinHeap() W[i] &lt;- W[x] + W[y] L[i] &lt;- x; R[i] &lt;- y P[x] &lt;- i; P[y] &lt;- i InsertHeap(i, W[i]) P[2n - 1] &lt;- 0&lt;/syntaxhighlight&gt;مثال.در این قسمت مثالی از کدگذاری هافمن را با مجموعه‌ای پنج حرفی و با وزن‌های داده شده (احتمال حضور) را بررسی می‌کنیم. در این مثال اثبات نمی‌کنیم مقدار formula_36 برای همه کدگذاری‌ها کمینه است بلکه مقادیر به دست آمده را با آنتروپی شانون formula_37 مقایسه کرده و نشان می‌دهیم مقادیر formula_36 به دست آمده تقریباً بهینه هستند.برای اطلاع از نحوه محاسبه formula_37 به ویکی‌پدیای انگلیسی همین صفحه مراجعه کنید.انواع.انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آن‌ها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی) استفاده می‌کنند.در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چندجمله‌ای هم نداشته باشد.لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی‌زیان اطلاعات» داده شده‌است.کد هافمن n تایی.الگوریتم کد هافمن "n" تایی از الفبای {۰، ۱،... ، "n" − ۱} برای کد کردن پیام‌ها و ساختن درخت n تایی استفاده می‌کند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش بررسی شده بود.کد هافمن انطباقی.نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ الگوریتم‌های LZ است.الگوریتم الگوی هافمن.بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آن‌ها نیازمند است.الگوریتم الگو هافمن امکان استفاده از هر نوع وزنی را می‌دهد. (ارزش-تکرار-جفت وزن ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی مختلف.اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.کد هافمن با طول محدود.کد هافمن با طول محدود نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد.الگوریتم بسته‌بندی-ادغام این مشکل را به‌وسیلهٔ یک الگوریتم حریصانه ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند.پیچیدگی زمانی این الگوریتم formula_40، که formula_36 ماکزیمم طول یک کدکلمه (codeword)است.هیچ الگوریتمی شناخته نشده که این کا را در زمان linear or linearithmic انجام دهد، بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.کد هافمن با ارزش حرفی متفاوت.در کد گذاری استاندارد هافمن، فرض شده‌است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند، ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن "N" است ارزشی برابر "N" خواهد داشت، مهم نیست که چند رقم آن ۱ و چند رقم آن ۰ است.وقتی با این فرض کار می‌کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقم‌های کل ۲ چیز یکسانند."کد هافمن با ارزش حرفی متفاوت" به نحوی عمومیت یافته که این فرض دیگر صحیح نیست:حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند، به خاطر خصوصیت‌های واسطهٔ انتقال.مثالی بر این ادعا، الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد، پس ارزش خط تیره در زمان انتقال بالاتر است.درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست.هیچ الگوریتمی شناخته نشده‌است که این را به همان روش و همان کارایی کد قراردادی هافمن انجام دهد.کد قانونی هافمن.اگر وزن‌های مربوط به ورودی‌های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید.کد بدست آمده از ورودی‌های مرتب شده از نظر عددی، کد قانونی هافمن گفته می‌شود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی، در عمل استفاده می‌شود.تکنیک پیدا کردن این کد، اکثراً کد گذاری Huffman-Shannon-Fano نامیده می‌شود.و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن‌ها مانند کد گذاری رمزگذاری شانون-فانو الفبایی است.کد هافمن Shannon-Fano مربوط به این مثال formula_42 است که در آن طول کد کلمه‌ها، همان مقداری است که در حل اصلی آمده‌است.