کدهای هافمن چه هستند؟

کدهای هافمن نوعی کد پیشوندی هستند که برای انتقال بهینه اطلاعات استفاده می‌شوند. منظور از انتقال بهینه اطلاعات استفاده از کمترین bit ممکن برای منتقل کردن اطلاعات مورد نظر است. به بیان دیگر، الگوریتم هافمن برای تبدیل داده‌ها به کدهای هافمن، نوعی الگوریتم فشرده‌سازی است. فشرده‌سازی اطلاعات، بخشی از نظریه اطلاعات است که حدودا در دهه ۱۹۴۰ میلادی توسط شانون پایه‌گذاری شد.کدهای هافمن مبتنی بر دو مشاهده بودنددر یک کد بهینه، علائمی که بیشتر تکرار می‌شوند، کوتاه‌تر از (تعداد bit کمتری دارند) علائمی که کمتر تکرار می‌شوند.در یک کد بهینه، دو علامتی که کمتر از همه تکرار می‌شوند، طول یکسانی دارند.مشاهده اول بنظر منطقی است. فرض کنید می‌خواهیم کلمه Hello را کد کنیم. اگر کد ما به نحو زیر باشد قاعدتا خیلی جالب نیست:H --> 11 e --> 10 l --> 01 o --> 00اگر بخواهیم کلمه Hello را با کد بالا کدگذاری کنیم خروجی کار رشته زیر می‌شود:1110010100طول رشته بالا ۱۰ بیت است. اما وقتی می‌دانیم حرف l، در کلمه ۲ بار تکرار شده، منطقی‌تر این است که این حرف طول کمتری داشته باشد. پس سعی می‌کنیم کد را تغییر دهیم تا اندکی بهینه‌تر شود. H --> 01 e --> 00 l --> 1 o --> 011کد شده کلمه Hello بر اساس کد بالا رشته زیر می‌شود:010011011که طول این کد ۹ بیت است. پس اگر علامتی که بیشتر تکرار می‌شود، طولانی‌تر از علامتی باشد که کمتر تکرار می‌شود، کد ما بهینه نیست. چون با جابجا کردن این دو علامت، کد ما بهینه‌تر می‌شود. لذا برای بهینه بودن کد، این قاعده ضروری است.درمورد مشاهده دوم، باید اندکی بیشتر دست و پا زد تا واضح‌تر شود. فرض کنیم کدی بهینه داریم. ۲ علامتی که کمترین تکرار را دارند را در نظر بگیریم a و b. فرض می‌کنیم این دو علامت هم‌اندازه نیستند. وقتی هم‌اندازه نیستند پس قاعدتا یکی از دیگری k بیت طولانی‌تر است. فرض می‌کنیم طول a بیشتر است.length (a) = length (b) + kحالا از آنجایی که می‌دانیم این کدها پیشوندی هستند (یعنی هیچ‌کدام پیشوند دیگری نیستند) می‌توانیم k بیت اضافه علامت a را حذف کنیم، و نگران متمایز بودن آن با باقی علائم نشویم. پس کد جدیدی می‌توانیم داشته باشیم که تعداد بیت‌های تشکیل دهنده علامت a کمتر است. لذا کد قبلی بهینه نبود.یک قاعده دیگر را هم باید لحاظ کنیم در مورد کدهای فاهمندو علامت با کمترین تکرار (مثل a و b) در مثال بالا، باید فقط در بیت آخر خود متمایز باشند. یعنی اگر m را رشته بیت‌های سازنده a بدانیم. و n را رشته بیت‌های سازنده b بدانیم، داریم: s + `1` = m s + `0` = nیعنی s رشته بیتی بود که فقط با افزودن یک بیت دیگر به آن، یا به m تبدیل می‌شد یا به n. این قاعده، ۲ مشاهده ابتدائی ما را نقض نمی‌کند، لذا مشکلی نیست.خب حالا چه کنیم؟ابتدا فرض می‌کنیم می‌خواهیم رشته "Hello mello" را با الگوریتم هافمن، کد کنیم. برای شروع باید جدولی داشته باشیم به شکل زیر:letter | probability | code-word _______________________________ `l` | 0.4 | C(l) `o` | 0.2 | C(o) `e` | 0.2 | C(e) `H` | 0.1 | C(H) `m` | 0.1 | C(m) طبق دو مشاهده‌ای که بالاتر گفته شد، می‌دانیم که طول C(H) و C(m) برابر است. چون هر دو کم تکرار ترین حروف هستند. و طبق فرض میدانیم که این دو کد، فقط در بیت آخر باهم تفاوت دارند. پس داریم:C(H) = a + `0` C(m) = a + `1`حالا برای حذف کردن یکی از این حروف، دو حرف H و m را ترکیب می‌کنیم، و جای آن، بخش مشترک این دو حرف، یعنی a را، قرار می‌دهیم. با این تغییر، جدول ما در مرحله بعد به صورت زیر می‌شود:letter | probability | code-word _______________________________ `l` | 0.4 | C(l) `o` | 0.2 | C(o) `e` | 0.2 | C(e) X | 0.2 | a همان‌طور که مشاهده می‌کنید، احتمال وجود حرف X (حرفی که در واقع وجود ندارد، ترکیبی است از حروف H و m) ۰.۲ است، یعنی مجموع احتمال حروف H و m. دقیقا همان کار را برای جدول دوم تکرار می‌کنیم. می‌دانیم که ۲ حرف آخر با کمترین احتمال، طول یکسانی دارند و تنها تفاوتشان، آخرین بیت است. پس دوباره خواهیم داشت:a = b + `1` C(e) = b + `0`در اینجا b بخش مشترک دو رشته بیت a و C(e) است. بر اساس دو تساوی بالا، می‌توانیم برسیم به:C(H) = a + `0` = b + `10` C(m) = a + `1` = b + `11`دیدیم که الان یک مرحله پیشرفت کردیم. از کدهای کاراکترهای H و m الان ۲ بیت داریم. حالا دوباره همان مرحله را تکرار می‌کنیم. ترکیب دو عنصر پایینی با یک‌دیگر.letter | probability | code-word _______________________________ `l` | 0.4 | C(l) Y | 0.4 | b `o` | 0.2 | C(o)و با توجه به یکسان بودن طول دو عنصر آخر داریم:b = c + `1` C(o) = c + `0`که در وهله بعد:C(H) = b + `10` = c + `110` C(m) = b + `11` = c + `111` C(e) = b + `0` = c + `10`با تکرار کردن همین الگو، در مرحله بعد جدول به شکل زیر خواهد شد:letter | probability | code-word _______________________________ Z | 0.6 | c `l` | 0.4 | C(l) که در مرحله آخر داریم:c = d + `1` C(l) = d + `0` که خب نتیجه میگیریم:C(H) = c + `110` = d + `1110` C(m) = c + `111` = d + `1111` C(e) = c + `10` = d + `110` C(o) = c + `0` = d + `10` C(l) = d + `0`حالا همه حروف را بر حسب d داریم. فرض می‌کنیم d رشته‌ای تهی یا خالی است. در این صورت کد ما به صورت زیر خواهد شد:letter | probability | code-word _______________________________ `l` | 0.4 | 0 `o` | 0.2 | 10 `e` | 0.2 | 110 `H` | 0.1 | 1110 `m` | 0.1 | 1111 طبق قاعده دو حرف با کمترین احتمال، طول یکسان دارند و تنها بیت آخرشان متمایز است. همچنین حروف با احتمال بیشتر، طول کمتری دارند. به علاوه این کد، کد پیشوندی نیز هست. یعنی هیچ کلمه‌ای، پیشوند کلمه دیگر نیست. حالا می‌توانیم "Hello mello" را کدگذاری کنیم:1110,110,0,0,10,1111,110,0,0,10که خب چون کد پیشوندی است، نیازی به حروف جدا کننده ندارد لذا داریم:1110110001011111100010۳ نکته در انتها لازم به ذکر است.اول اینکه خودم متوجه هستم که کاراکتر فاصله را در فشرده سازی لحاظ نکردم. برای سادگی بود :)دوم اینکه حروف a، b، c و d هیچ‌کدام حرفی از داده‌ای که باید منتقل می‌شد نبودند. این‌ها صرفا علامتی برای نشان دادن رشته بیت‌های مشترک بودند.سوم هم اینکه خودم می‌دانم به شدت افتضاح و ناقص این الگوریتم را توضیح دادم. در واقع اصلا توضیح داده نشد، صرفا یک مثال از آن را حل کردیم. برای اطلاعات بیشتر شما را به فصل ۳ از کتاب Introduction to data compression ارجاع می‌دهم. خیلی کامل خوب همه چیز توضیح داده شده. وقت خودتان را با خواندن دوباره مهملاتی که اینجا نوشتم هدر ندهید!