کدگذاری حسابی

کدگذاری حسابی (به انگلیسی: Arithmetic coding) نوعی کدگذاری براساس آنتروپی است که در فشرده‌سازی بی‌اتلاف داده استفاده می‌شود. در حالت عادی یک رشته از نویسه‌ها مثل کلمات "hello there" به این صورت کدگذاری می‌شود که برای هر نویسه، از تعداد ثابتی از بیت‌ها استفاده می‌شود (مثلاً کدگذاری ASCII از این روش استفاده می‌کند). اما موقعی که یک رشته به کدگذاری حسابی تبدیل می‌شود، نویسه‌های مکرر استفاده‌شونده، توسط بیت‌های کمتر و نویسه‌هایی که به صورت کمتر رخ می‌دهند، توسط بیت‌های بیشتری ذخیره می‌شوند. نتیجهٔ نهایی این نوع کدگذاری آن است که در مجموع از بیت‌های کمتری استفاده می‌شود.

تفاوت کدگذاری حسابی با کدگذاری هافمن

• در کدگذاری هافمن
  • ورودی به «نمادهای مولفه‌ای» جداسازی می‌شود، و هر «نماد» توسط یک «کد» جایگذاری می‌شود.
• در کدگذاری حسابی
  • «کل پیام» تبدیل به یک «عدد» می‌شود، که نوعی عدد با دقت دلخواه است و بین 0 و 1 قرار دارد. در این روش، «اطلاعات» به صورت یک «بازه» نمایش می‌یابند که این بازه دو عدد شروع و پایان دارد.

کدگذاری‌های امروزی

کدگذاری‌های امروزی که بر اساس آنتروپی هستند، سامانه‌های عددی نامتقارن نام دارند، و مزیت‌شان آن است که امکان پیاده‌سازی سریعتر را فراهم می‌سازند، زیرا روی یک «عدد طبیعی منفرد» به صورت مستقیم عمل می‌کنند، که این عدد نشان دهنده اطلاعات موجود است.

«هر تکرار» در کدگذاری حسابی با یک مثال

مثالی از یک گام در کدگذاری حسابی

در اینجا، یک مثال از کدگذاری حسابی آمده‌است که برای هر کدام از نمادهای "A"و "B" و "C" یک توزیع احتمال ثابت را فرض می‌کند. احتمال "A" برابر 50 درصد است، احتمال "B" برابر 33 درصد و احتمال "C" برابر 17 درصد است. بعلاوه ما فرض می‌کنیم که عمق بازگشتی در هر گام را می‌دانیم.

در گام اول "B" که داخل بازه [0.5, 0.83) قرار دارد را کدبندی می‌کنیم. عدد دودویی "0.10x" کوتاهترین کدی است که نمایش دهنده بازه‌ای است که کاملاً داخل بازه [0.5, 0.83) قرار دارد. در اینجا x یعنی ترتیبی اختیاری از بیت‌ها. در اینجا دو حالت حد نهایی برای این بازه وجود دارد.

• کمترین مقدار x، برابر صفر است، که نمایش دهنده سمت چپ بازه نمایش داده شده‌است. آن موقع سمت چپ بازه برابر dec(0.10) = 0.5 است.
• در بیشترین مقدار، x برابر تعداد بینهایتی یک است، که در اینجا حد بالایی برابر dec(0.11) = 0.75 می‌باشد.

بنابراین، "0.10x" نمایش دهنده بازه [0.5, 0.75) است، که داخل بازه [0.5, 0.83) قرار دارد.

در نهایت:

• قسمت "0." حذف می‌گردد، زیرا همه بازه‌ها با "0." شروع می‌شوند. قسمت "x" را هم نادیده می‌گیریم، زیرا مهم نیست که چه ترتیب بیتی را نمایش بدهد، هر چیزی را نمایش بدهد، ما هنوز در بازه [0.5, 0.75) قرار داریم.

شبه‌کد با یک مثال

کدگذاری حسابی برای پیام "WIKI" در شکل رو برو نمایش داده شده است:

1- فرکانس حروف را پیدا می‌کنیم.

2- بازه [0, 1) را به نسبت فرکانس‌ها تقسیم‌بندی می‌کنیم.

3- بازه متناسب به صورت تکراری به این صورت انتخاب می‌شود

5. برای هر حرف در داخل پیام، بازه را تقسیم‌بندی کنید.

6. هر مقداری که در «بازه نهایی» قرار بگیرد، به عنوان نمایش‌دهنده پیام انتخاب می‌شود.

2*- تقسیم‌بندی و مقدار به دست آمده برای پیام در اینجا قرار دارد.

6*. برای "KIWI" این کار انجام شده‌است.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Arithmetic coding». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۰ اکتبر ۲۰۲۰.