کدگذاری هافمن انطباقی
کدگذاری هافمن انطباقی (به انگلیسی: Adaptive Huffman coding) (یا کدگذاری هافمن پویا) یک تکنیک کدگذاری انطباقی بر پایهٔ کدگذاری هافمن است. وقتی اطلاعات در حال انتقال هستند، این نوع کدگذاری، بدون داشتن دانش اولیه از توزیع منبع، کدگذاری با یک بار خواندن و انطباق با تغییر شرایط در اطلاعات را ممکن می‌کند. مزیت یک بار خواندن این است که منبع می‌تواند به صورت در لحظه کدگذاری شود. هر چند به این ترتیب به خطاهای انتقال حساس تر می‌شود. چون حتی از دست دادن یک بیت از اطلاعات کل کد را خراب می‌کند.
الگوریتم ها
[ویرایش]تعداد زیادی روش پیاده‌سازی وجود دارد. که قابل توجه ترینشان، FGK (Faller-Gallager-Knuth) و الگوریتم ویتر هستند.
الگوریتم Vitter
[ویرایش]کد، ساختار درختی ای دارد که در آن هر گره، دارای وزن مشخص و شمارهٔ یکتا است. عددها پایین می روند و از راست به چپ هستند.
وزن‌ها باید خاصیت برادری را دارا باشند؛ که این حالت زمانی ایجاد می‌شود که گره‌ها طوری لیست شوند که وزن هر گره در قیاس با گره مجاور کاهش یابد. مثلا اگر A گره والد B و C فرزند B باشد، وزن A> وزن B> وزن C است.
وزن صرفا تعداد نمادهای منتقل شده‌است که نشانه ای از کدهاییست که با فرزندان گره‌ها در ارتباط هستند.
تعدادی کد با وزن یکسان یک بلوک را می سازند.
برای به دست آوردن کد هر گره در درخت دوتایی، می توانیم تمام مسیر از ریشه تا گره را طی کنیم.برای مثال اگر به راست برویم یک و اگر به چپ برویم صفر نوشته می‌شود.ما به روشی عمومی و پیشرو (مستقیم/ساده) برای انتقال کاراکترهایی که هنوز منتقل نشده اند، (NYT) نیاز داریم. برای مثال می توانیم از انتقال عددهای دو رقمی برای هر نماد در الفبا استفاده کنیم.
رمزگذار و رمزگشا از یک گرهٔ ریشه شروع می‌شود که بیشترین شماره را دارد و در ابتدا گرهٔ NYT ماست.وقتی ما سمبل NYT را منتقل می کنیم باید ابتدا کد گرهٔ NYT و سپس کد عمومی آن را منتقل کنیم.برای هر سمبلی که در درخت وجود دارد ما باید تنها کد برگ آن را وارد کنیم.
برای هر کاراکتری که منتقل می‌شود باید هم فرستند و هم گیرنده به عملیات روز رسانی را انجام دهند.
- اگر کاراکتر فعلی NYT است، به گرهٔ NYT دو گرهٔ فرزند اضافه کنید.یکی گرهٔ NYT جدید و دیگری گرهٔ برگ کاراکتر ما می‌شود.وزن گرهٔ برگ جدید و NYT قدیمی را افزایش دهید و به گام 4 بروید. اگر نه، به گرهٔ برگ نماد بروید.
- اگر گره بالاترین عدد را در بلوک ندارد، آن را با گره دارای بالاترین عدد عوض کنید.مگر اینکه گرهٔ والدش باشد.
- وزن گرهٔ فعلی را افزایش دهید.
- اگر گرهٔ ریشه نیست، به گره والد رفته و سپس به گام دوم بروید. ولی اگر ریشه است کار تمام شده.
مبادلهٔ گره‌ها به معنی مبادلهٔ وزن و نماد پاسخگو (مربوطه) است نه مبادله عددها.
مثال
[ویرایش]
- با یک درخت خالی شروع کنید.
- برای a یک کد دو رقمی منتقل کنید.
- NYT دو گرهٔ فرزند تولید می‌کند: 254 و 255.
- وزن را برای ریشه افزایش دهید.
- برای b ، 0 (برای NYT) و سپس کد دو رقمی اش را انتقال دهید.
- NYT دو فرزند تولید می‌کند.252 برای NYT و 253 برای گره بزگ. وزن‌ها را برای 253 و 254 و ریشه افزایش دهید. کد b ، 01 است.
- برای b دوم 01 را انتقال دهید.
- به گره برگ ، 253 بروید.ما یک بلوک از وزن 1 داریم و بزرگترین عدد در این بلوک 255 است.پس وزن و نماد گرهٔ 253 و 255 را مبادله کنید.وزن را افزایش دهید. به ریشه بروید و وزن ریشه را افزایش دهید.
- کد بعدی برای b 1 است و برای a الان 01 است که نشان دهندهٔ فرکانس است.
منابع
[ویرایش]- Vitter's original paper: J. S. Vitter, "Design and Analysis of Dynamic Huffman Codes", Journal of the ACM, 34(4), October 1987, pp 825–845.
- J. S. Vitter, "ALGORITHM 673 Dynamic Huffman Coding", ACM Transactions on Mathematical Software, 15(2), June 1989, pp 158–167. Also appears in Collected Algorithms of ACM.