کدهای هافمن نوعی کد پیشوندی هستند که برای انتقال بهینه اطلاعات استفاده می‌شوند. منظور از انتقال بهینه اطلاعات استفاده از کمترین 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
۳ نکته در انتها لازم به ذکر است.
