موضوع مقاله: کدگذاری هافمن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کدگذاری هافمن | مقدمه: فرایند پیدا کردن یا استفاده از این کد، با بهره‌گیری از الگوریتمی انجام می‌شود که توسط «دیوید هافمن» (زمانی که وی دانشجوی دوره دکتری در دانشگاه MIT بود) توسعه داده شده‌است و برای اولین بار در سال ۱۹۵۲ در مقاله‌ای با عنوان «روشی برای تولید کدی با کمترین تکرار زوائد» منتشر شد. | ## بخش 1: کدگذاری هافمن | می‌توان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور یا فراوانی تکرار حروف در فایل منبع ایجاد شده‌است و مانند هر رمزگذاری درگاشتی دیگر، حروف پرتکرار تر با تعداد بیت‌های کمتری نمایش داده می‌شوند. باید دقت کرد با توجه به کارایی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشرده‌سازی بهینه‌تری داشته باشیم، می‌توان از الگوریتم‌های کدگذاری حسابی یا سیستم‌های عددی نامتقارن استفاده کرد. هافمن و هم شاگردی‌هایش در کلاس تئوری اطلاعات در دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا شرکت در امتحان پایانی را داشتند. هافمن که در ابتدا موفق به یافتن کارآمدترین کد نشده بود، تصمیم گرفت خودش را برای شرکت در امتحان پایانی آماده کند. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، کلود شانون برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ رمزگذاری شانون-فانو جلوگیری کرد و درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت. واژه‌شناسی در کدگذاری هافمن، از روشی به نام کدهای بدون پیشوند (که به عنوان «کدهای پیشوندی» نیز شناخته می‌شود) برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. در این روش نویسه‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند. کدگذاری هفمن به اندازه‌ای پرکابرد است که کلمه «کد هافمن» به صورت گسترده به عنوان مترادفی برای کدهای پیشوندی استفاده می‌شود. تعریف مسئله تعریف غیررسمی داده‌های مسئله: مجموعه‌ای از نمادها (حروف و کاراکترها) به همراه وزن هر کدام. تعریف رسمی ورودی: مجموعه حروف به طول مجموعه وزن‌ها که نشان‌دهنده وزن هر نماد (حرف) از مجموعه حروف است به طوری که: خروجی: مجموعه کد (دودویی) که هر عضو آن نشان‌دهنده کد متناسب با یکی از حروف در مجموعه است. حال مجموعه حروف جدید را در نظر می‌گیریم که شامل تمام اعضای مجموعه به جز دو عضو و است و جدید را داراست. در این مجموعه حروف جدید، وزن همهٔ اعضا برابر با وزن قبلی آنها در مجموعه است و وزن عضو برابر با خواهد بود. | ## بخش 2: کدگذاری هافمن | مراحل الگوریتم اگر اندازه مجموعه حروف برابر ۲ باشد، درخت بهینه از اتصال دو راس با ریشه به دست می‌آید. اگر اندازه مجموعه بیشتر از ۲ باشد: توسط الگوریتم داده شده در بالا، و را به دست آورده و به صورت بازگشتی درخت را می‌سازیم. در درخت گرهٔ را با درختی سه راسی که با یک پدر و دو فرزند که هرکدام از فرزندها یکی از رئوس یا است، جایگزین می‌کنیم. اثبات بهینه بودن درخت کد حاصل از الگوریتم هافمن را می‌توانید در «درسنامه جلسه ۱۰ کلاس تحلیل الگوریتم‌ها دانشکده ریاضی دانشگاه صنعتی شریف» کنید. پیچیدگی الگوریتم الگوریتم هافمن اگر به صورت ساده گفته شده در بالا پیاده‌سازی شود، می‌توان به راحتی با استفاده از رابطه بازگشتی نشان داد دارای پیچیدگی زمانی است. اما می‌توان با استفاده از داده ساختار هرم الگوریتم را بهبود بخشید و پیچیدگی زمانی را به کاهش داد. در پیاده‌سازی این الگوریتم به سه آرایه نیاز داریم و برای هر گره در درخت، مقادیر فرزند راست ، فرزند چپ و والد را در آن‌ها ذخیره می‌کنیم. در این مثال اثبات نمی‌کنیم مقدار برای همه کدگذاری‌ها کمینه است بلکه مقادیر به دست آمده را با آنتروپی شانون مقایسه کرده و نشان می‌دهیم مقادیر به دست آمده تقریباً بهینه هستند. ورودی و نمادabcdeمجموعوزن0.100.150.300.160.29= ۱خروجیکد کلمه010011110010طول کد (تعداد بیت)33222مشارکت در طول مسیر وزن دار0.300.450.600.320.58L(C) = ۲٫۲۵بهینگیمشارکت در آنتروپی0.3320.4110.5210.4230.518H(A) = ۲٫۲۰۵ برای اطلاع از نحوه محاسبه به ویکی‌پدیای انگلیسی همین صفحه مراجعه کنید. انواع انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آن‌ها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی) استفاده می‌کنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چندجمله‌ای هم نداشته باشد. لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی‌زیان اطلاعات» داده شده‌است. کد هافمن انطباقی نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. | ## بخش 3: کدگذاری هافمن | الگوریتم الگوی هافمن بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آن‌ها نیازمند است. این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد. الگوریتم بسته‌بندی-ادغام این مشکل را به‌وسیلهٔ یک الگوریتم حریصانه ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند. کد هافمن با ارزش حرفی متفاوت در کد گذاری استاندارد هافمن، فرض شده‌است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند، ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن N است ارزشی برابر N خواهد داشت، مهم نیست که چند رقم آن ۱ و چند رقم آن ۰ است. وقتی با این فرض کار می‌کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقم‌های کل ۲ چیز یکسانند. کد هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند، به خاطر خصوصیت‌های واسطهٔ انتقال. مثالی بر این ادعا، الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده‌است که این را به همان روش و همان کارایی کد قراردادی هافمن انجام دهد. کد قانونی هافمن اگر وزن‌های مربوط به ورودی‌های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید. کد بدست آمده از ورودی‌های مرتب شده از نظر عددی، کد قانونی هافمن گفته می‌شود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی، در عمل استفاده می‌شود. | ## جمع‌بندی | و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن‌ها مانند کد گذاری رمزگذاری شانون-فانو الفبایی است.