کدگذاری هافمن
در علوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن (به انگلیسی: ) نوع مشخصی از کد پیشوندی (به انگلیسی: ) بهینه است که کاربردی فراوان در فشرده‌سازی بی‌اتلاف اطلاعات دارد. فرایند پیدا کردن یا استفاده از این کد، با بهره‌گیری از الگوریتمی انجام می‌شود که توسط «دیوید هافمن» (زمانی که وی دانشجوی دوره دکتری در دانشگاه MIT بود) توسعه داده شده‌است و برای اولین بار در سال 1952 در مقاله‌ای با عنوان «روشی برای تولید کدی با کمترین تکرار زوائد» منتشر شد.
می‌توان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور و یا فراوانی تکرار حروف در فایل منبع ایجاد شده‌است و مانند هر ی دیگر، حروف پرتکرار تر با تعداد بیت‌های کمتری نمایش داده می‌شوند.
باید دقت کرد با توجه به کارآیی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشرده‌سازی بهینه‌تری داشته باشیم، می‌توان از الگوریتم‌های کدگذاری حسابی و یا سیستم‌های عددی نامتقارن استفاده کرد.
در سال 1951 میلادی، دیوید آ. هافمن و هم شاگردی‌هایش در کلاس تئوری اطلاعات در دانشگاه 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 تکرار می‌کنیم.اثبات بهینه بودن درخت کد حاصل از الگوریتم هافمن را می‌توانید در «درسنامه جلسه 10 کلاس تحلیل الگوریتم‌ها دانشکده ریاضی دانشگاه صنعتی شریف» مطالعه کنید.
الگوریتم هافمن اگر به صورت ساده گفته شده در بالا پیاده‌سازی شود، می‌توان به راحتی با استفاده از رابطه بازگشتی formula_29 نشان داد دارای پیچیدگی زمانی formula_30 است. اما می‌توان با استفاده از داده ساختار هرم الگوریتم را بهبود بخشید و پیچیدگی زمانی را به formula_31 کاهش داد. در پیاده‌سازی این الگوریتم به سه آرایه نیاز داریم و برای هر گره formula_32 در درخت، مقادیر فرزند راست formula_33، فرزند چپ formula_34 و والد formula_35 را در آن‌ها ذخیره می‌کنیم.function BuildHuffman(W)در این قسمت مثالی از کدگذاری هافمن را با مجموعه‌ای پنج حرفی و با وزن‌های داده شده (احتمال حضور) را بررسی می‌کنیم. در این مثال اثبات نمی‌کنیم مقدار formula_36 برای همه کدگذاری‌ها کمینه است بلکه مقادیر به دست آمده را با آنتروپی شانون formula_37 مقایسه کرده و نشان می‌دهیم مقادیر formula_36 به دست آمده تقریبا بهینه هستند.
برای اطلاع از نحوه محاسبه formula_37 به ویکی‌پدیای انگلیسی همین صفحه مراجعه کنید.
انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آن‌ها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاه می‌کنند.
در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چندجمله‌ای هم نداشته باشد. لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی زیان اطلاعات»  داده شده‌است.
الگوریتم کد هافمن "n" تایی از الفبای {۰، ۱،... ، "n" − ۱} برای کد کردن پیام‌ها و ساختن درخت n تایی استفاده می‌کند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش بررسی شده بود.
نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ الگوریتم‌های LZ است.
بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آن‌ها نیازمند است. الگوریتم الگو هافمن امکان استفاده از هر نوع وزنی را می‌دهد.(ارزش-تکرار-جفت وزن ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی مختلف. اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.
کد هافمن با طول محدود نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد.
الگوریتم بسته بندی-ادغام این مشکل را به‌وسیلهٔ یک الگوریتم حریصانه ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند. پیچیدگی زمانی این الگوریتم formula_40، که formula_36 ماکزیمم طول یک کدکلمه (codeword)است.
هیچ الگوریتمی شناخته نشده که این کا را در زمان linear or linearithmic انجام دهد، بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.
در کد گذاری استاندارد هافمن، فرض شده‌است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند، ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن "N" است ارزشی برابر "N" خواهد داشت، مهم نیست که چند رقم آن ۱ و چند رقم آن ۰ است. وقتی با این فرض کار می‌کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقم‌های کل ۲ چیز یکسانند. "کد هافمن با ارزش حرفی متفاوت" به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند، به خاطر خصوصیت‌های واسطهٔ انتقال. مثالی بر این ادعا، الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده‌است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
اگر وزن‌های مربوط به ورودی‌های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید. کد بدست آمده از ورودی‌های مرتب شده از نظر عددی، کد قانونی هافمن گفته می‌شود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی، در عمل استفاده می‌شود. تکنیک پیدا کردن این کد، اکثراً کد گذاری Huffman-Shannon-Fano نامیده می‌شود. و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن‌ها مانند کد گذاری رمزگذاری شانون-فانو الفبایی است. کد هافمن Shannon-Fano مربوط به این مثال formula_42 است که در آن طول کد کلمه‌ها، همان مقداری است که در حل اصلی آمده‌است.