اين الگوريتم كه توسط ديويد هافمن توسعه يافت، از يک جدول به نام «کد طول متغير» براي کد کردن داده‌ها استفاده مي‌کند. اطلاعات جدول کد طول متغير بر اساس احتمال وقوع يک کاراکتر در داده منبع به‌دست مي‌آيد.
کارکرد
اين الگوريتم يک داده را مي‌گيرد و سپس جدول طول متغير را بر اساس آن توليد مي‌کند. مثلا فرض کنيد داده ما رشته متني مثل «روزنامه جام‌جم هر روز صبح منتشر مي‌شود.» است، حالا بياييم جدول کد طول متغير را براي اين رشته محاسبه کنيم. کاراکتر فاصله 6 بار و کاراکتر (ز) 2 بار تکرار شده است و همين‌طور براي بقيه کاراکتر‌ها اين عدد را به‌دست مي‌آوريم. در نهايت يک جدول به‌دست مي‌آيد که مشخص مي‌کند هر کاراکتر در متن بالا چند بار تکرار شده است.
جدول شامل دو ستون است که يکي ستون آن کاراکتر و ديگري کد طول متغير است. ما داده‌هاي جدول را بر اساس کد طول متغير به‌صورت صعودي مرتب مي‌کنيم. سپس دو عنصر کوچکتر را انتخاب كرده و آنها را درون درختي قرار مي‌دهيم که برگ‌هاي آن، دو عدد و ريشه آن، مجموع کد طول متغير آن دو برگ است.
به فرض کد طول متغير دو کاراکتر اول مجموعه مرتب شده به‌ترتيب برابر 3 و 5 است. اين دو کاراکتر در يک درخت به ريشه‌اي با عدد 8 و يال سمت چپ برابر 3 و يال سمت راست برابر 5 قرار مي‌گيرند (به اين نکته بايد توجه داشته باشيد که در درخت حاصل از هر مرحله بايد يال سمت راست بزرگتر از يال سمت چپ باشد). حال عدد 8 را به عنوان اميد رياضي در نظر مي‌گيريم و بر اساس جدول طول متغير دوباره داده‌ها را مرتب مي‌کنيم و دوباره درخت متناظري درست مي‌کنيم که متشکل از اولين عنصر مرتب شده برابر 7 و درخت قبلي است.
در اين مرحله کاراکتري که طول کد متغير آن برابر 7 است در سمت چپ درختي قرار مي‌گيرد که ريشه آن برابر 15 است و سمت راست آن همان درختي است که در مرحله پيش ساختيم. آنقدر اين کار را ادامه مي‌دهيم تا به يک درخت برسيم.
نتايج حاصل از پيمايش درخت برابر کد هافمن هستند. در اين درخت يال سمت راست را برابر صفر و يال سمت چپ را برابر يک در نظر مي‌گيرند. فرض کنيد درختي مطابق شکل زير داشته باشيم:
کد هافمن مربوط به عدد a برابر 010 است، به اين دليل که ابتدا به سمت چپ رفته پس يک صفر داريم، سپس به سمت راست رفته پس يک داريم و دوباره به سمت چپ آمده و صفر داريم و نتيجه برابر 010 است.
براي اين که مراحل ايجاد کد هافمن را مشاهده کنيد به نشاني زير مراجعه كنيد:
http://upload.wikimedia.org/wikipedia/commons/a/ac/Huffman_huff_demo.gif
شبه کد الگوريتم هافمن
C نشان دهنده يک رشته اطلاعات است. ابتدا طول رشته را در N مي‌ريزيم. سپس براي اين رشته اطلاعاتي جدول کد طول متغير را محاسبه مي‌کنيم که اين عمل از مرتبه (O(n انجام مي‌شود. سپس براي دو کاراکتر اولي يک درخت تشکيل داده و بعد آن را در جاي مناسب خود در جدول قرار مي‌دهيم طوري که مرتب بودن بر اساس کد طول متغير همچنان حفظ شود. اين عمل از مرتبه (O(nLogn انجام مي‌پذيرد. در نهايت عنصر کوچک مجموعه را برمي‌گردانيم.
