نویسنده: MF

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

تاریخچه:

در سال 1951 دیوید هافمن در کلاس درس " تئوری اطلاعات" در دانشگاهMIT، بین دادن امتحان پایانی و یا تحقیق درباره پیدا کردن کارآمدترین کد دودویی یکی را بایستی انتخاب می کرد.هافمن ناتوان در پیدا کردن کارآمدترین روش کد دودویی، تصمیم گرفت خود روشی را ابداع کند.روش هافمن، استفاده از درخت دودویی مرتب شده با استفاده از تکرار بود. که بجای ساخته شدن از بالا به پایین؛ از پایین به بالا ساخته می شد.انواع مختلفی از کدگذاری هافمن وجود دارد.{کدهافمن با طول محدود--کد هافمن انطباقی و...}.

همانطور که می دانید، در کامپیوتر برای هر کاراکتری، یک کد (با استاندارد اسکی) بین 0 تا 255 در نظر گرفته می شود.که به هفت بیت فضا نیاز دارد.مثلا برای نمایش حرف A از عدد 65 استفاده می شود.که در مبنای 2 به صورت 1000001درخواهد آمد و در نتیجه برای ذخیره شدن به 7 بیت فضا نیاز دارد.که در این صورت رشته AAAAAAAAکه متشکل از 8 حرف A است به فضایی معادل 8*7=56 بیت یا به بیان ساده تر 7 بایت نیاز دارد.

در استاندارد اسکی 254 کاراکتر مجاز دیگر به جز Aوجود دارد.اما در رشتهAAAAAAAAفقط یک نوع کاراکتر بکار رفته.می توان این کد را به طور قراردادی به کد کوتاهتری (مثلا1) تغییر دهیم. در این صورت رشته ی فوق در فضایی به طول 8*1=8 بیت یا به بیان ساده تر 1 بایت قابل ذخیره سازی است.

و اما اینکه چگونه کد جدید (در این مثال 1 به جای 65) را به دست بیاوریم توسط روش Huffman بیان میشود.

1-روش هافمن بصورت توضیحی:

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

2-روش هافمن با شکل:

1-عددی که بالای هر کاراکتر نوشته شده است نشان دهنده تعداد دفعات تکرار آن کاراکتر در رشته مورد نظر است.

2-m,w,c,h,u کمترین تکرار را دارند؛ ما مجازیم هرکدام از دو زوجی که کمترین مقدار را دارند دو به دو در نظر بگیریم..پس از این مرحله چگالی ها = 3-3-2-2-3-2-1-2-4خواهد بود(اعداد پر رنگ جایگزین جدید هستند)

3-سپس چگالی ها 3-3-4-3-3-2-4خواهد شد.

و سپس چگالی ها 6-7-5-4خواهد شد.

(همینطور ادامه میدهیم....)؛ و تا مرحله پایانی ادامه می دهیم، پس از اتمام این مرحله تنها عدد 22 باقی خواهد ماند و دیگر نمیتوانیم جفتی برای ادامه دادن الگوریتم پیدا کنیم.

3-کد فشرده سازی هافمن:

یعنی اول چک میکنه که ببینه آیا گره فرزند چپ وجو داره؟ اگه داره تابع رو مجددا روی فرزند سمت چپ صدا میزنه، بعد اگه فرزند سمت راست داره روی فرزند سمت راست صدا میزنه مثلا برای درخت بالا، حاصل کار به شکل:

A, C, E, D, B, H, I, G, F خواهد بود. یعنی اول چپ ترین فرزند، بعدش چپ ترین فرزند راست، بعدش چپ ترین فرزند راست راست و...

در این روش کاراکتر‌های پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

توضیح بیشتر:

نکته: (هر حرکت به چپ 0 و هر حرکت به راست 1)

با دنبال کردن مسیر از راس تا کاراکترها(ریشه تا برگ ها) کد های جدید به دست خواهند آمد؛ کدهای جایگزین به دست آمده برای این مثال به شکل زیر است:

E: 00

M: 0100

W: 0101

C: 0110

H: 01110

U: 01111

N: 100

I: 1010

T: 1011

_: 110

S: 111

همینطور که مشاهده می کنید.به حرف Eکه تعداد تکرار بیشتری داشته کد کوچکتر 00 اختصاص داده شده.و از این پس در این کد نوشته ای که به روش هافمن فشرده سازی شده حرف E با کد 00 شناخته می شود.نه با کدِ اسکی آن.