رمزگذاری شانون-فانو
From Wikipedia, the free encyclopedia
در حوزهٔ فشرده سازی داده ها، کدینگ یا کدگذاری شانون-فانو، که به افتخار کلود شانون و رابرت فانو این چنین نامیده شده، تکنیکی است، برای ایجاد یک کد پیشوندی (Prefix Code)، بر مبنای مجموعهای از نمادها و احتمالات (تخمین زده شده یا اندازهگیری شده). این تکنیک نیمه بهینه است؛ چرا که مانند کدگذاری هافمن ،به کمترین طول قابل انتظار کلمات کد (Codewords) نمیرسد؛ با این حال بر خلاف کدگذاری هافمن، تضمین میکند که تمام طولهای کلمات کد در یک بیت از مقدار تئوری ایدهآل –logP(x) جای میگیرد. این روش در «نظریهٔ ریاضیِ ارتباطات»، مقاله شانون در سال ۱۹۴۸ در معرفی حوزهٔ نظریه اطلاعات مطرح شدهاست. این روش بعدها به فانو نسبت داده شد. کدگذاری شانون-فانو نباید با کدگذاری شانون اشتباه شود که روشی است برای اثبات نظریه کدگذاری بدون اختلال شانون و همچنین نباید آن را با کدگذاری شانون-فانو-الیاس (که به کدگذاری الیاس معروف است) اشتباه گرفت که پیش ساز کدگذاری محاسباتی است.
![]() | برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (مه ۲۰۱۴) |
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (مه ۲۰۱۴) |
در کدگذاری شانون-فانو، نمادها به ترتیب احتمال از زیاد به کم مرتب شدهاند؛ و پس از آن به دو مجموعه که احتمال کل شان تا حد ممکن به هم نزدیک است تقسیم میشوند. سپس اولین رقم کد همهٔ نمادها به آنها اختصاص داده میشود؛ نمادها در مجموعهٔ اول "۰" و در مجموعهٔ دوم "۱" میگیرند. تا زمانی که مجموعهای با بیش از یک عضو باقی بماند، همین فرایند برای تعیین ارقام متوالی کدهایشان، روی آنها تکرار میشود. وقتی یک مجموعه به یک نماد کاهش پیدا کند بدان معناست که کد آن نماد کامل است و پیشوند هیچ کدِ نماد دیگری را تشکیل نمیدهد. این الگوریتم کدگذاریهای با طول متغیر نسبتاً کارامدی تولید میکند. وقتی دو مجموعهٔ کوچکتر که با یک تقسیمبندی ایجاد شدهاند در واقع دارای احتمال برابری هستند، یک بیت اطلاعاتی که برای تمایز آنها استفاده میشود، به بهینهترین نحو به کار گرفته میشود. متأسفانه شانون-فانو همیشه پیشوند کدهای بهینه تولید نمیکند؛ مجموعهٔ احتمالات {۰٫۳۵٬۰٫۱۷٬۰٫۱۷٬۰٫۱۶٬۰٫۱۵} مثالی است که به آن کدهای نابهینهای توسط کدگذاری شانون-فانو اخصاص داده میشود.
به همین دلیل، شانون-فانو تقریباً هیچ وقت استفاده نمیشود. کدگذاری هافمن تقریباً از نظر محاسباتی ساده است و تحت محدودیتهایی که هر نماد با یک کد متشکل از تعداد درست و جدایی ناپذیری از بیتها نمایش داده میشود، کدهایی پیشوندی تولید میکند که همیشه به کمترین طول قابل انتظار کلمات کد میرسند. از آن جایی که کدها انتها به انتها در توالیهای بلند دسته میشوند این محدودیتی است که اغلب غیرضروری است. اگر گروههای کدها را یک جا در نظر بگیریم، کدگذاری نماد به نماد هافمن فقط وقتی بهینه است که احتمالات نمادها مستقل بوده و توانی از یک دوم باشند، مثلاً n(2/1). در اکثر شرایط، کدگذاری محاسباتی میتواند در مجموع فشردهسازی بیشتری نسبت به هافمن یا شانون-فانو تولید کند چرا که میتواند در تعداد کوچکی از بیتها کدگذاری کند که بهطور دقیق تری محتوای اطلاعاتی واقعی نماد را تقریب بزند. با این حال آن میزان که هافمن جایگزین شانون-فانو شدهاست کدگذاری محاسباتی جای هافمن را نگرفتهاست چرا که هم کدگذاری محاسباتی از لحاظ محاسبات سنگین تر است و هم توسط چند حق امتیاز انحصاری پوشش داده میشود.
کدگذاری شانون-فانو در روش فشردهسازی IMPLODE که بخشی از فرمت فایل ZIP است، استفاده میشود.[1]