صفحه شخصی سورنا معروفی

هافمن در سال 1952 الگوريتمی ارائه داد که تونست به هر سمبل بر اساس تعداد تکرارش يک کد اختصاص بده بطوری که کد کوتاهتر برای سمبل با تعداد تکرار بيشتر و کد بلند تر برای سمبل با تعداد تکرار کمتر.
اين الگوريتم تو فشرده سازی بسيار مهم و کارا هستش (البته ميشه گفت بود) و خوب با آمدن الگوريتم arithmetic و قابليت پياده سازی اون ديگه کم کم هافمن کمتر استفاده شد.حالا تو قسمت های بعدی در موردش بيشتر ميگم.

اينجا يه مثالی براتون ميزنم از کتاب فشرده سازی آقای matt mahoney که فکر کنم بد نباشه.اگه زياد متوجه نشدين نگران نشيد و به خوندن ادامه بديد حتماً در آخر قضيه رو ميگيريد.(هنوز خيلی زوده برای نا اميد شدن!!!).

فرض کنيد ميخوايم عدد pi (همون که 3.14 هستش) رو فشرده کنيم و همون طور که ميدونيد اين عدد تمومی نداره و به صورت ...3.14159265358979323846264 هستش و همين طور هم ادامه داره.
حالا اگر احتمال وقوع هر کدوم از عدد های 0 تا 9 تو اين مجموعه برابر با 0.1 باشه و همه اين احتمالات هم از هم مستقل باشه (يعنی عدد بعدی بعد از مميز به احتمال 0.1 برابر 0 و به احتمال 0.1 برابر 1 و ... باشه و اين احتمالات از هم مستقل باشه.) ميتونيم 3 نوع نمايش BCD و هافمن و باينری رو به صورت زير داشته باشيم.

 			 Digit BCD   Huffman Binary
 			 ----  ----   ----   ----
  			  0   0000   000    0
 			  1   0001   001    1
 			   2   0010   010    10
 			   3   0011   011    11
 			    4   0100   100    100
 			    5   0101   101    101
 			    6   0110   1100   110
 			    7   0111   1101   111
 			     8   1000   1110   1000
 			     9   1001   1111   1001
 			   ---   ----   ----   ----
 		   	         bpc   4.0    3.4    not valid

خوب همين طور که ميبينيد نمايش BCD برای هر کاراکتر از 4 بيت استفاده ميکنه يعنی ميزان فشرده سازی 4 bpc هستش.
يعنی اگه ورودی مون به صورت يه فايل متنی باشه خوب خروجی مون 50% فشرده تر هستش يعنی تو ورودی ما برای نمايش هر رقم از 8 بيت استفاده ميکنيم(ascii text) ولی تو خروجی برای نمايش هر رقم از 4 بيت استفاده ميکنيم يعنی انگار هر 2 رقم رو تو يک byte ميتونيم نمايش بديم.اميد وارم که گرفته باشين.

خوب حالا ميرسيم به نمايش باينری خوب همين طور که ميبينيد اين خيلی بهتره يعنی تو بدترين حالت که رقم 9 داشته باشيم از 4 بيت استفاده ميکنه و تو بقيه حالت ها از 3 يا 2 يا حتی از 1 بيت استفاده ميکنه پس خيلی خوبه و ما ميتونيم خروجی رو به صورت زير نمايش بديم :

خوب اين روش باينری خيلی خوبه فقط يه مشکل داره که غير قابل استفاده ميکندش.چه مشکلی؟؟؟ خوب موقع decode کردن از کجا بفهميم که اول بايد 2 تا 1 برداريم بعد 1 دونه 1 برداريم بد 100 بر داريم و ...؟؟؟
پس چون اين روش قابل decode کردن نيست بدرد نميخوره.

خوب حالا ميرسيم به روش هافمن و همين طور که تو جدول بالا ميبينيد اين روش يه چيزی هستش بين باينری و BCD به اين ترتيب که تعداد بيت هاش از BCD کمتره و از باينری بيشتره ولی بر خلاف باينری به صورت منحصر به فرد decode ميشه.چه جوری؟؟؟؟الان ميگم.
فرض کنيد خروجی ما به صورت زير هستش :

خوب تمام نکته همين جاست.decoder شروع ميکنه به decode کردن به اين ترتيب که اول 1 بيت ميخونه و تو جدول چک ميکنه ببينه همچين کدی وجود داره يا نه اگه بود معادلش رو ميزاره(خوب ما ميدونيم که هيچ کد هافمنی تو جدول بالا معادل 0 نيست.). اين کار اونقدر تکرار ميشه تا کد های معتبر از جدول هافمن استخراج بشه و رقم معادل با اونها جايگزين بشه.مثلاً اولين کد معتبر همون 011 هستش که معادل رقم 3 هستش.و به همين ترتيب ادامه ميده تا تمام خروجی رو decode کنه.خوب حالا چند تا سؤال پيش مياد: 1.اين جدول رو از کجا بياريم؟؟؟
2.آيا decoder هم بايد حتماً اين جدول رو داشته باشه تا بتونه decode کنه؟؟؟؟
3.همه اين چرندياتی که گفتی چه ربطی به اون احتمال وقوع و اين چيزا داشت؟
خوب من تو قسمت بعدی جواب اين سؤالات رو ميدم.

فرض کنيد متنی که ميخوايم فشرده کنيم همون عدد pi هستش که در بالا نمايش داديم و فرض کنيد که احتمال وقوع هر رقم در ان 0.1 باشه به صورت زير داريم:

probability .1  .1  .1  .1  .1  .1  .1  .1  .1  .1
  digits     0   1   2   3   4   5   6   7   8   9

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

.4 / \ / \ / \ .2 .2 .2 .2 .2 / \ / \ / \ / \ / \ .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 0 1 2 3 4 5 6 7 8 9

.4 .4 / \ / \ / \ / \ / \ / \ .2 .2 .2 .2 .2 / \ / \ / \ / \ / \ .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 0 1 2 3 4 5 6 7 8 9

.6 / \ / \ / \ .4 .4 \ / \ / \ \ / \ / \ \ / \ / \ \ .2 .2 .2 .2 .2 / \ / \ / \ / \ / \ .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 0 1 2 3 4 5 6 7 8 9

در مرحله آخر که کوچکترين احتمال ها 0.4 و 0.6 هستند ساختن درخت هافمن ما به پايان ميرسد و حالا در اين مرحله به شاخه های سمت چپ 0 و به شاخه های سمت راست 1 ميدهيم که البته اين دلبخواهی است و برعکس هم ميتوان انجام داد.

1.0 / \ / \ / \ / \ 0 / \ 1 / \ / \ / .6 / / \ / 0 / \ 1 / / \ .4 .4 \ / \ / \ \ 0 / \ 1 0 / \ 1 \ / \ / \ \ .2 .2 .2 .2 .2 / \ / \ / \ / \ / \ .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 0 1 2 3 4 5 6 7 8 9

خوب پس اين از روش ساخت جدول هافمن و اينکه در حالت عادی decoder به اين جدول نياز داره پس بايد اين رو هم برای decoder فرستاد ولی اگر دقت کنيد ميبينيد که با فرستادن اطلاعات کمتری هم ميشه اين جدول رو تو decoder ساخت.(چرند گفتم امکان نداره اگه خودتونو پاره هم بکنيد از دقت نميتونيد ببينيد.)
يادتون هست گفتم مهم نيست که به شاخه های سمت چپ صفر بدين و به سمت راست يک و يا برعکس؟؟؟؟
خوب اگه برعکس کار کنيد اونوقت به يه سری کد هافمن جديد ميرسين و اين اصلاً مهم نيست چون چيزی که تو هافمن مهم هست فقط اينه که به سمبل به تکرار بيشتر کد کوتاه تری اختصاص داده بشه فقط و فقط همين.پس جدول زير هم يک جدول معتبر هستش.

Symbol Size Code ------ ---- ---- 0 3 000 1 3 001 2 3 010 3 3 011 8 3 100 9 3 101 4 4 1100 5 4 1101 6 4 1110 7 4 1111

خوب حالا ما بجای فرستادن همه جدول ميآيم فقط سمبل و سايز رو ميفرستيم(نگاه کنيد به جدول بالا.)اونوقت تو دکدر چی کار ميکنيم؟؟؟
1.کوچکترين سايز رو ميگيريم (در اينجا 3) و به همون تعداد صفر اختصاص ميديم(000)
2.برای سمبل بعدی اگه سايز ثابت موند(که اينجا ميمونه) يک واحد کد قبلی رو افزايش ميديم.(001).
3.اگه سايز يک دونه افزايش داشت(مثلاً از 3 به 4 رفت.)کد قبلی رو يک واحد افزايش ميديم و يک صفر هم به سمت راست آن اضافه ميکنيم(يعنی از لحاظ برنامه نويسی يک دونه شيفت به چپ ميديم.)(مثلاً اينجا ميشه 1100).
4.روند 2 و 3 رو ادامه ميديم تا سمبل ها تموم بشه.

اها فقط تنها نکته اي که مونده اينه که تو سالهای اخير ديگه هافمن زياد کارايی نداره چون روش های بهتری آمد که هم کارامد تر از هافمن بود هم عيب های هافمن رو بر طرف کرد.(کدوم عيب ها؟؟؟). فرض کنيد به جای عدد pi ميخواين يه ورودی ديگه رو فشرده کنيد مثلاً داريم:

همين طور که ميبينيد تمام ورودی ما در اينجا 0 و 1 هستش يعنی ورودی فقط 2 حالت داره و از اونجايی که 2 حالت رو ميشه با 1 بيت نمايش داد،پس هافمن چه کمکی ميتونه تو فشده سازی اين ورودی بکنه؟؟؟سعی کنيد يک درخت برای اين ورودی بسازيد اونوقت ميبينيد که هافمن هيچ کمکی نميتونه بکنه و اين يکی از اشکالت هافمن هستش که البته راه هايی برای نه کامل رفع کردن ولی بهتر شدن وجود داره و البته روش های فشرده سازی ديگر هم که اين مشکل رو خيلی وقته رفع کردن مثلاً يکی از روش های خيلی خوب arithmetic coding هستش که حالا بعداً در موردش حرف ميزنيم.

بعداً براتون يه پياده سازی به زبون cpp هم ميزارم که حال کنيد.اميدوارم که توضيحاتم کافی بوده باشه.اگه سؤالی بود email ام رو که دارين.

Sourena's personal page

(Huffman Coding) هافمن کدينگ