کدگذاری هافمن انطباقی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

کدگذاری هافمن انطباقی (به انگلیسی: Adaptive Huffman coding) (یا کدگذاری هافمن پویا) یک تکنیک کدگذاری انطباقی بر پایه ی کدگذاری هافمن است. وقتی اطلاعات در حال انتقال هستند، این نوع کدگذاری، بدون داشتن دانش اولیه از توزیع منبع، کدگذاری با یک بار خواندن و انطباق با تغییر شرایط در اطلاعات را ممکن می کند. مزیت یک بار خواندن این است که منبع می تواند به صورت در لحظه کدگذاری شود. هر چند به این ترتیب به خطاهای انتقال حساس تر می شود. چون حتی از دست دادن یک بیت از اطلاعات کل کد را خراب می کند.

الگوریتم ها[ویرایش]

تعداد زیادی روش پیاده سازی وجود دارد. که قابل توجه ترینشان، FGK (Faller-Gallager-Knuth) و الگوریتم ویتر هستند.

الگوریتم Vitter[ویرایش]

کد، ساختار درختی ای دارد که در آن هر گره، دارای وزن مشخص و شماره ی یکتا است. عدد ها پایین می روند و از راست به چپ هستند.
وزن ها باید خاصیت برادری را دارا باشند؛ که این حالت زمانی ایجاد میشود که گره ها طوری لیست شوند که وزن هر گره در قیاس با گره مجاور کاهش یابد. مثلا اگر A گره والد B و C فرزند B باشد، وزن A> وزن B> وزن C است.
وزن صرفا تعداد نمادهای منتقل شده است که نشانه ای از کدهاییست که با فرزندان گره ها در ارتباط هستند.
تعدادی کد با وزن یکسان یک بلوک را می سازند.
برای به دست آوردن کد هر گره در درخت دوتایی، می توانیم تمام مسیر از ریشه تا گره را طی کنیم.برای مثال اگر به راست برویم یک و اگر به چپ برویم صفر نوشته میشود.ما به روشی عمومی و پیشرو (مستقیم/ساده) برای انتقال کاراکترهایی که هنوز منتقل نشده اند، (NYT) نیاز داریم. برای مثال می توانیم از انتقال عددهای دو رقمی برای هر نماد در الفبا استفاده کنیم.
رمزگذار و رمزگشا از یک گره ی ریشه شروع میشود که بیشترین شماره را دارد و در ابتدا گره ی NYT ماست.وقتی ما سمبل NYT را منتقل می کنیم باید ابتدا کد گره ی NYT و سپس کد عمومی آن را منتقل کنیم.برای هر سمبلی که در درخت وجود دارد ما باید تنها کد برگ آن را وارد کنیم. برای هر کاراکتری که منتقل می شود باید هم فرستند و هم گیرنده به عملیات روز رسانی را انجام دهند.

  1. اگر کاراکتر فعلی NYT است، به گره ی NYT دو گره ی فرزند اضافه کنید.یکی گره ی NYT جدید و دیگری گره ی برگ کاراکتر ما می شود.وزن گره ی برگ جدید و NYT قدیمی را افزایش دهید و به گام 4 بروید. اگر نه، به گره ی برگ نماد بروید.
  2. اگر گره بالاترین عدد را در بلوک ندارد، آن را با گره دارای بالاترین عدد عوض کنید.مگر اینکه گره ی والدش باشد.
  3. وزن گره ی فعلی را افزایش دهید.
  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.

پیوند به بیرون[ویرایش]