روش کدگذاری هافمن

روش فشرده سازی هافمن الگوریتمی است که برای فشرده سازی متن مناسب می‌باشد.
الگوریتم هافمن جزو خانوادهٔ الگوریتم‌هایی است که طول کد متغیری دارند. این به آن معناست که نمادهای مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت‌هایی که طول‌های
مختلفی دارند تعویض می‌شود. بنابراین نمادهایی که زیاد در یک فایل تکرار می‌شوند یک رشته بیت کوتاه می‌گیرند در حالی که نمادهای دیگر که به ندرت دیده می‌شوند رشته بیت طولانی‌تری را
می‌گیرند.

تاریخچه
در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند. استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمدترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کند که ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودویی مرتب شده بر حسب تکرار(frequency) و توانست اثبات کند که این کارآمدترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.

کد‌گذاری هافمن

یک الگوریتم کد‌گذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است. این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا به دست می‌آید. این روش به‌وسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

در کدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.
هافمن موفق شد کارآمدترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با آن‌هایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.
برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری ASCII. کد گذاری هافمن روشی متداول برای ایجاد کد‌های بدون پیشوند است به‌طوری‌که عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن به دست نیامده باشد.
اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی توانایی بالاتری در فشرده سازی دارند.

کد قانونی هافمن
اگر وزن‌های مربوط به ورودی‌های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه به دست آید. کد به دست آمده از ورودی‌های مرتب شده از نظر عددی ،کد قانونی هافمن گفته می‌شود و کدی است که به خاطر سادگی رمز کردن و رمز گشایی ،در عمل استفاده می‌شود. تکنیک پیدا کردن این کد ، اکثرا کد گذاری Huffman-Shannon-Fano نامیده می‌شود. و این به خاطر آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن‌ها مانند کد گذاری Shannon-Fano coding الفبایی است. کد هافمن Shannon-Fano مربوط به این مثال {۰۰۰,۰۰۱,۰۱,۱۰,۱۱} است که در آن طول کد کلمه‌ها ، همان مقداری است که در حل اصلی آمده است.

کد هافمن با ارزش حرفی متفاوت
در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند،ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن N است ارزشی برابر N خواهد داشت ،مهم نیس که چند رقم آن ۱ و چند رقم آن ۰ است. وقتی با این فرض کار می‌کنیم، کم کردن هزینهٔ کلی پیام ، با کم کردن تعداد رقم‌های کل ۲ چیز یکسانند. کد هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند ، به خاطر خصوصیت‌های واسطهٔ انتقال. مثالی بر این ادعا،الفبای کد گذاری کد مورس است، که در آن فرستادن یک ‘خط تیره’ بیشتر از فرستادن یک ‘نقطه’ طول می‌کشد ، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.

انواع
انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آن‌ها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کد‌های بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاده می‌کنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چند‌جمله‌ای هم نداشته باشد. لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی زیان اطلاعات» [۱] داده شده‌است.

کد هافمن n تایی
الگوریتم کد هافمن n تایی از الفبای {۰, ۱,…, n − ۱} برای کد کردن پیام‌ها و ساختن درخت n تایی استفاده می‌کند. این روش دسترسی به‌وسیلهٔ هافمن و در مقاله اش بررسی شده بود.

کد هافمن انطباقی
نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ الگوریتم‌های LZ است.

الگوریتم الگوی هافمن
بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آن‌ها نیازمند است. الگوریتم الگوی هافمن امکان استفاده از هر نوع وزنی را می‌دهد.(ارزش-تکرار-جفت وزن‌ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی مختلف. اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.

کد هافمن با طول محدود
کد هافمن با طول محدود نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز به دست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد. الگوریتم بسته بندی-ادغام این مشکل را به‌وسیلهٔ یک الگوریتم حریصانه ساده شبیه به همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند. پیچیدگی زمانی این الگوریتم O(nL), که L ماکزیمم طول یک کدکلمه(codeword)است.

هیچ الگوریتمی شناخته نشده که این کار را در زمان linear or linearithmic انجام دهد,بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن. یک مثال کاربردی اجزای کار را به شما نشان می‌دهد.

فرض کنید می‌خواهید تکه اطلاعات زیر را فشرده کنید:
ACDABA

از آنجایی که ۶ کاراکتر داریم، این متن ۶ بایت یا ۴۸ بیت می‌باشد. با رمزگذاری هافمن، فایل برای بیشترین تکرار ظاهر شدن نمادها (در این مثال نماد A سه بار تکرار می‌شود) جستجو می‌شود و
سپس یک درخت ساخته می‌شود که نمادها را با رشته بیت‌های کوتاه‌تر جایگزین می‌کند. در این حالت خاص الگوریتم از جدول جایگزینی زیر استفاده می‌کند:
A=0 , B=10 , C=110 , D=111.

اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می‌آیند:
01101110100

این به این معنی است که ۱۱ بیت به جای ۴۸ بیت مصرف شد. در این مثال خاص نسبت فشرده سازی ۴ به ۱ می‌باشد.
رمزگذاری هافمن به دو روش مختلف می‌تواند بهینه‌تر شود:
1. کد هافمن انطباقی (Adaptive Huffman code) به صورت پویا کلمات کد را با توجه به تغییر احتمال وقوع نمادها تغییر می‌دهد.
2. فشرده سازی گستردهٔ هافمن (Extended Huffman Compression) می‌تواند گروهی از نمادها را نسبت به یک نماد رمزگذاری کند.

این روش می‌تواند بین ۲۰% تا ۹۰% اطلاعات را فشرده کند.

این الگوریتم فشرده سازی اساسا برای فشرده سازی متون و فایل‌های برنامه سودمند است.

کد گذاری به روش هافمن

کد گذاری به روش هافمن، روشی است برای بهینه سازی مقدار حجم استفاده شده برای نگهداری داده‌های معلوم.

همانطور که می‌دانید، هر کاراکتری در کامپیوتر با یک کد (با استاندارد اسکی بین ۰ تا ۲۵۵) نمایش داده می‌شود، فرض کنید برای نمایش حرف A از عدد ۶۵ استفاده شود، عدد ۶۵ در مبنای ۲ (که مبنای ذخیره سازی کامپیوترهای رقمی است) به صورت ۱۰۰۰۰۰۱ در خواهد آمد و در نتیجه به ۷ بیت فضا برای ذخیره سازی نیاز دارد.
در این صورت رشته ی AAAAAAAA که متشکل از ۸ حرف A است نیاز به فضایی معادل ۸*۷=۵۶ بیت یا به بیان ساده‌تر ۷ بایت دارد.
دلیل اینکه ما کد ۶۵ را برای حرف A انتخاب کردیم این است که (در استاندارد Ascii) 254 کاراکتر مجاز دیگر به جز A برای کامپیوترها در نظر گرفته شده است. اما در رشته فوق از آنجا که می‌دانیم فقط یک نوع کاراکتر به کار رفته است، می‌توانیم این کد را به طور قراردادی به کد کوتاهتری (مثلا ۱) تغییر دهیم، در این صورت رشته ی فوق در فضایی به طول ۸*۱=۸ بیت یا به بیان ساده‌تر ۱ بایت قابل ذخیره سازی است.

و اما اینکه چگونه کد جدید (در این مثال ۱ به جای ۶۵) را به دست بیاوریم توسط روش Huffman بیان می‌شود.

روش هافمن:

۱- چگالی هر کاراکتر را محاسبه می‌کنیم (تعداد دفعات حضور کاراکتر در متن مورد نظر).
2- دو کاراکتر با کمترین میزان تکرار (چگالی) را انتخاب می‌کنیم.
3- کاراکترهای مرحله ۲ را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی دو کاراکتر فوق است جایگزین می‌کنیم.
4- تا زمانی که فقط یک کاراکتر باقی مانده باشد، به مرحله ۲ می‌رویم.
5- از عملیات فوق یک درخت حاصل می‌شود، بر روی این درخت هر مسیر به سمت چپ با ۰ و هر مسیر به سمت راست با ۱ وزن دهی می‌شود.
6- کد هر کاراکتر با کنار هم گذاشتن وزن‌ها از ریشه تا آن کاراکتر به دست می‌آید.

درعلوم کامپیوتر و تئوری اطلاعات، کد‌گذاری هافمن یک الگوریتم کد‌گذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است.

این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا به دست می‌آید. این روش به‌وسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

در کدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

هافمن موفق شد کارآمدترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با آن‌هایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.

برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری ASCII. کد گذاری هافمن روشی متداول برای ایجاد کد‌های بدون پیشوند است به‌طوری‌که عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن به دست نیامده باشد.

اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی توانایی بالاتری در فشرده سازی دارند.

تعریف مساله
پیدا کنید: کد دودویی بدون پیشوند، (مجموعه‌ای از کدها) با کمترین امید ریاضی برای طول کد.(به طور معادل، درختی با کمترین مسیر وزن دار)
تاریخچه در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند. استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمدترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کند که ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودویی مرتب شده بر حسب تکرار(frequency) و توانست اثبات کند که این کارآمدترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.

منبع: hsu.ac.ir

 برای اطلاع از فن‌آوری‌های نوین ارتباطی شبکه‌های وایرلس و مایکروویو و مراکز تلفنی تحت شبکه از کانال تلگرامی ما به آدرس‌های Wireless_tech@و Voip_Tech@  دیدن فرمایید.