کد هافمن برای کنکور: از ایدهٔ حریصانه تا تست سری هندسی

مسئله دقیقاً چیست؟

چند نماد داری که هر کدام بسامد یا وزنی دارند و می‌خواهی به هر کدام یک کد دودویی بدهی. دو شرط داری: هیچ کدی پیشوند کد دیگری نباشد تا رشتهٔ بیت‌ها بدون جداکننده قابل خواندن باشد، و مجموع «وزن × طول کد» کمترین مقدار ممکن شود. هر کد پیشوندی را می‌شود با یک درخت دودویی نشان داد: نمادها برگ‌ها هستند و طول کد هر نماد همان عمق برگش است.

الگوریتم در یک نگاه

همهٔ نمادها را در یک صف اولویت (هیپ کمینه) بگذار. تا وقتی بیشتر از یک عنصر مانده، دو عنصر با کمترین وزن را بیرون بکش، یک گرهٔ تازه بساز که این دو فرزندش باشند و وزنش مجموع وزن آن دو باشد، و گرهٔ تازه را به صف برگردان. آخرین عنصر باقی‌مانده ریشهٔ درخت است. با n نماد دقیقاً n−۱ ادغام انجام می‌شود.

یک مثال کامل

وزن‌ها را ۱، ۲، ۴ و ۸ بگیر. قدم‌به‌قدم پیش برو و بعد از هر ادغام ببین چه چیزی در صف مانده است.

حالا عمق هر برگ را بخوان: ۸ مستقیم زیر ریشه است، پس کدش یک بیت است. ۴ دو بیت، و ۲ و ۱ هر دو سه بیت. هزینهٔ کل می‌شود ۸×۱ + ۴×۲ + ۲×۳ + ۱×۳ = ۲۵.

ترفندی که در تست وقت می‌خرد: هزینه = جمع ادغام‌ها

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

در مثال بالا، ۳ + ۷ + ۱۵ = ۲۵؛ همان عدد، بدون کشیدن درخت. سر جلسه، وقتی گزینه‌ها فقط عدد هزینه‌اند، همین کافی است.

چرا حریصانه جواب می‌دهد؟

دو نمادی که کمترین وزن را دارند، در دست‌کم یک درخت بهینه، دو برگ هم‌سطح در عمیق‌ترین سطح‌اند. دلیلش یک جابه‌جایی ساده است: اگر نماد کم‌وزن‌تری بالاتر از نماد پروزن‌تری نشسته باشد، جابه‌جا کردنشان هزینه را زیاد نمی‌کند. پس می‌شود این دو را با خیال راحت ادغام کرد و با یک نماد کمتر، همان مسئله را دوباره حل کرد. این «انتخاب حریصانه + زیرمسئلهٔ کوچک‌تر» همان الگویی است که در بقیهٔ الگوریتم‌های حریصانه، مثل کراسکال و پریم، هم می‌بینی.

حالت سری هندسی: درخت زنجیری

حالا وزن‌ها را ۱، ۲، ۴، ۸، …، 2^(n−1) بگیر. نکته این است که مجموع همهٔ وزن‌های قبلی همیشه یکی کمتر از وزن بعدی است: ۱ + ۲ = ۳ که از ۴ کمتر است، ۱ + ۲ + ۴ = ۷ که از ۸ کمتر است، و الی آخر. یعنی گرهٔ تازه‌ای که هر بار می‌سازی، همیشه جزو دو کوچک‌ترین صف می‌ماند و با وزن بعدی ادغام می‌شود. نتیجه یک درخت کج و زنجیری است.

قاعدهٔ کلی: بزرگ‌ترین وزن کد یک‌بیتی می‌گیرد، هر وزن کوچک‌تر یک بیت بیشتر، و دو وزن کوچک‌تر هر دو n−۱ بیت. هزینه هم از ترفند قبلی می‌آید: ۳ + ۷ + ۱۵ + ۳۱ = ۵۶. بسامدهای فیبوناچی (۱، ۱، ۲، ۳، ۵، ۸) هم دقیقاً همین شکل زنجیری را می‌سازند؛ امتحانش کن.

سه اشتباه رایج در تست‌ها

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

نه. وقتی دو وزن برابر داری، انتخاب اینکه کدام را اول ادغام کنی آزاد است و درخت‌های متفاوتی به دست می‌آید. مثلاً با وزن‌های ۱، ۱، ۲ و ۲: بعد از ادغام دو تا ۱، سه عنصر با وزن ۲ داری. اگر گرهٔ تازه را با یکی از ۲ها ادغام کنی، طول کدها ۳، ۳، ۲ و ۱ می‌شود. اگر دو ۲ اصلی را با هم ادغام کنی، همه ۲ بیتی می‌شوند. هزینهٔ هر دو ۱۲ است. پس گزاره‌ای مثل «بلندترین کد هافمن این مجموعه ۳ بیت است» لزوماً درست نیست.

فقط دو نماد کم‌وزن‌تر بلندترین کد را دارند؟

در درختی که هافمن می‌سازد، دو نماد کم‌وزن‌تر اولین ادغام‌اند، پس برادرند و کدشان هم‌طول است؛ و همیشه یک درخت بهینه هست که آن‌ها را در عمیق‌ترین سطح بگذارد. ولی گزینه‌ای که بگوید «فقط همین دو» بلندترین کد را دارند معمولاً غلط است: در مثال وزن‌های ۱، ۱، ۲ و ۲، در یکی از دو درخت هر چهار نماد کد دوبیتی دارند.

زمان اجرای هافمن همیشه O(n log n) است؟

با هیپ، n−۱ بار دو عنصر برداشته و یکی اضافه می‌شود و هر کدام O(log n) هزینه دارد، پس کل کار O(n log n) است. ولی اگر وزن‌ها از قبل مرتب باشند، با دو صف ساده (یکی برای برگ‌ها، یکی برای گره‌های تازه که خودبه‌خود مرتب ساخته می‌شوند) می‌شود O(n) هم انجامش داد.

خودت امتحان کن

وزن‌ها ۲، ۳، ۵، ۷ و ۱۱ هستند. بدون کشیدن درخت، هزینهٔ کد هافمن را حساب کن. بعد درخت را بکش و طول کد هر نماد را بنویس. جواب را پایین‌تر گذاشته‌ام؛ اول خودت حل کن.

جواب: ادغام‌ها ۲+۳ = ۵، بعد ۵+۵ = ۱۰، بعد ۷+۱۰ = ۱۷، بعد ۱۱+۱۷ = ۲۸. هزینه = ۵ + ۱۰ + ۱۷ + ۲۸ = ۶۰. طول کدها: ۱۱ یک بیت، ۷ دو بیت، ۵ سه بیت، و ۲ و ۳ هر کدام چهار بیت. این هم درختی زنجیری است، چون گرهٔ تازه در هر قدم جزو دو عنصر کوچک صف می‌ماند: ۵ کنار ۵، بعد ۱۰ کنار ۷، بعد ۱۷ کنار ۱۱.

سؤال‌هایی که احتمالاً داری

هافمن در کدام درس کنکور می‌آید؟

در بخش الگوریتم‌های حریصانه. در مجموعه‌های ۱۲۷۷ و ۱۲۷۶ این بخش زیر عنوان «داده‌ساختارها و الگوریتم‌ها» است و در ۱۲۰۹ زیر «طراحی الگوریتم‌ها».

لازم است اثبات بهینه بودن را حفظ کنم؟

حفظ کردن نه، فهمیدن ایده‌اش بله. تست‌های «کدام گزاره لزوماً درست است» دقیقاً از همین استدلال جابه‌جایی و برادر بودن دو نماد کم‌وزن‌تر ساخته می‌شوند.

کد هافمن همیشه از کد با طول ثابت بهتر است؟

هیچ‌وقت بدتر نیست، چون کد با طول ثابت هم یک درخت دودویی است و هافمن کمترین هزینه را بین همهٔ درخت‌ها پیدا می‌کند. ولی اگر همهٔ وزن‌ها برابر باشند و تعداد نمادها توانی از ۲ باشد، هر دو یک هزینه دارند.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم و الگوریتم‌های حریصانه، از هافمن تا درخت پوشای کمینه، بخشی از دورهٔ طراحی الگوریتم من‌اند؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. از ۱۲ تست داده‌ساختار و الگوریتم کنکور ۱۴۰۵، نُه‌تا پیش‌تر در کلاس کار شده بود؛ سند این مقایسه در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

سه مجموعه وزن برای خودت بساز: یکی سری هندسی، یکی با وزن‌های برابر و یکی دلخواه. برای هر کدام هزینه را یک بار با جمع ادغام‌ها و یک بار با عمق برگ‌ها حساب کن. اگر هر دو بار یک عدد درآمد، این مبحث را بلدی.