کدگذاری آنتروپی

کدگذاری^[۱] آنتروپی^[۲] (به انگلیسی: Entropy encoding) یا کدگذاری مبتنی بر آنتروپی نوعی طرح فشرده‌سازی بی‌اتلاف داده است که از نوع ویژگی‌های رسانه انتقال داده مستقل است.

در یکی از انواع اصلی کدگذاری آنتروپی، یک «کد بدون‌پیشوند منحصربه‌فرد» را برای هر نماد منحصربه‌فردی که در ورودی رخ می‌دهد، ساخته و انتساب می‌دهد. سپس کدگذارهای آنتروپی با عمل جایگذاری نمادهای ورودی (با طول ثابت) با کدواژه (به انگلیسی: codeword) بدون پیشوند (با طول متغیر)، به عنوان خروجی، داده را فشرده سازی می‌کنند. طول هر کدواژه به صورت تقریبی با منفی لگاریتم احتمال وقوع آن کدواژه متناسب است. در نتیجه این کار، پرکاربردترین نمادها از کوتاه‌ترین کدها استفاده می‌کنند.

بر اساس قضیه کدینگ منبع شانون، طول کد بهینه برای یک نماد برابر −log_bP است، که در آن b برابر تعداد نمادهایی است که از آن برای ساخت کدهای خروجی استفاده می‌شود، و P برابر احتمال نماد ورودی است.

دو تا از فنون کدگذاری آنتروپی مشهور، «کدگذاری هافمن» و «کدگذاری حسابی» هستند.^[۳] اگر ویژگی‌های آنتروپی تقریبی جریان داده را از قبل بدانیم (مخصوصا برای فشرده سازی سیگنال)، ممکن است که استفاده از «کد ایستای ساده‌تر» مفید باشد. کدهای ایستا شامل کدهای جهانی (مثل کدگذاری گاما الیاس یا کدگذاری فیبوناچی) و کد گولومب (مثل کدگذاری یگانی و کدگذاری رایس) می‌باشند.

از سال ۲۰۱۴، فشرده‌سازهای داده شروع به استفاده از خانواده سامانه‌های عددی نامتقارن از فنون کدگذاری آنتروپی کردند، در این تکنینک‌ها، از ترکیبی از نسبت فشرده‌سازی در کدگذاری حسابی با هزینه پردازشی مشابه کدگذاری هافمن استفاده می‌شود.

آنتروپی به عنوان اندازه مشابهت

علاوه بر این کاربرد (استفاده از کدگذاری آنتروپی به عنوان راهی برای فشرده‌سازی داده دیجیتالی)، کاربرد دیگر آن این است که از کدگذاری آنتروپی برای اندازه‌گیری میزان مشابهت بین «جریان داده» و «کلاس‌های داده از قبل موجود» استفاده می‌شود. این کار از طریق ایجاد یک کدگذار/فشرده‌ساز آنتروپی برای هر کلاس داده انجام می‌شود، سپس داده ناشناخته به صورت داده غیرفشرده به هر یک از این فشرده‌سازها خوراک‌دهی می‌شود، سپس آن داده کلاس‌بندی می‌شود، یعنی خروجی همه فشرده‌سازها بررسی می‌شود و فشرده‌سازی که بیشترین فشرده‌سازی را انجام دهد، به عنوان کلاس داده انتخاب می‌شود. کدگذاری که بهترین فشرده‌سازی را انجام بدهد، احتمالاً همان کدگذاری است که بر اساس داده آموزش یافته و همچنین بیشترین شباهت را با داده ناشناخته دارد.

پانویس

↑ «کُدگذاری» [رایانه و فناوری اطلاعات] هم‌ارزِ «coding»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر دوم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۷-۰ (ذیل سرواژهٔ کُدگذاری)
↑ «آنتروپی» [شیمی، فیزیک] هم‌ارزِ «entropy»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر اول. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۱-۱ (ذیل سرواژهٔ آنتروپی)
↑ Huffman, David (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE. Institute of Electrical and Electronics Engineers (IEEE). 40 (9): 1098–1101. doi:10.1109/jrproc.1952.273898. ISSN 0096-8390.

منابع

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

[1] «کُدگذاری» [رایانه و فناوری اطلاعات] هم‌ارزِ «coding»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر دوم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۷-۰ (ذیل سرواژهٔ کُدگذاری)

[2] «آنتروپی» [شیمی، فیزیک] هم‌ارزِ «entropy»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر اول. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۱-۱ (ذیل سرواژهٔ آنتروپی)

[Huffman_1952_pp._1098–1101-3] Huffman, David (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE. Institute of Electrical and Electronics Engineers (IEEE). 40 (9): 1098–1101. doi:10.1109/jrproc.1952.273898. ISSN 0096-8390.

[۱]

[۲]

[۳]