رمزگذاری شانون-فانو

در حوزه فشرده سازی داده، رمزگذاری شانون-فانو ، که بعد از کلود شانون و رابرت فانو این چنین نامیده شد، تکنیکی است برای ایجاد یک رمز پیشوندی بر مبنای مجموعه‌ای از نمادها و احتمالات (تخمین زده شده یا اندازه‌گیری شده). این تکنیک نیمه بهینه است چرا که مانند رمزگذاری هافمن به کمترین طول قابل انتظار کلمات رمز نمی‌رسد؛ با این حال بر خلاف رمزگذاری هافمن، تضمین می‌کند که تمام طول‌های کلمات رمز در یک بیت از مقدار تئوری ایده‌آل –logP(x) جای می‌گیرد. این روش در «نظریه ریاضی ارتباطات»، مقاله شانون در سال ۱۹۴۸ در معرفی حوزه نظریه اطلاعات مطرح شده‌است. این روش بعدها به فانو که آن را به عنوان یک گزارش روشی منتشر کرد، نسبت داده شد. رمزگذاری شانون-فانو نباید با رمزگذاری شانون اشتباه شود که روشی است برای اثبات نظریه رمزگذراری بدون اختلال شانون و همچنین نباید آن را با رمزگذاری شانون-فانو-الیاس (که به رمزگذاری الیاس معروف است) اشتباه گرفت که پیش ساز رمزگذاری محاسباتی است.
در رمزگذاری شانون-فانو، نمادها به ترتیب احتمال از زیاد به کم مرتب شده‌اند و پس از آن به دو مجموعه که احتمال کلشان تا حد ممکن به هم نزدیک است تقسیم می‌شوند. سپس اولین رقم رمز همه نمادها به آن‌ها اختصاص داده می‌شود؛ نمادها در مجموعه اول "۰" و در مجموعه دوم "۱" می‌گیرند. تا زمانی که مجموعه‌ای با بیش از یک عضو باقی بماند، همین فرایند برای تعیین ارقام متوالی رمزهایشان، روی آن‌ها تکرار می‌شود. وقتی یک مجموعه به یک نماد کاهش پیدا کند بدان معناست که رمز آن نماد کامل است و پیشوند هیچ رمز نماد دیگری را تشکیل نمی‌دهد.
این الگوریتم کدگذاری‌های با طول متغیر نسبتا کارامدی تولید می‌کند. وقتی دو مجموعه کوچک‌تر که با یک تقسیم‌بندی ایجاد شده‌اند در واقع دارای احتمال برابری هستند، یک بیت اطلاعاتی که برای تمایز آن‌ها استفاده می‌شود، به بهینه‌ترین نحو به کار گرفته می‌شود. متاسفانه شانون-فانو همیشه پیشوند رمزهای بهینه تولید نمی‌کند؛ مجموعه احتمالات {۰٫۳۵،۰٫۱۷،۰٫۱۷،۰٫۱۶،۰٫۱۵ مثالی است که به آن رمزهای نابهینه‌ای توسط رمزگذاری شانون-فانو اخصاص داده می‌شود.
به همین دلیل، شانون-فانو تقریبا هیچ وقت استفاده نمی‌شود. رمزگذاری هافمن تقریبا از نظر محاسباتی ساده است و تحت محدودیت‌هایی که هر نماد با یک رمز متشکل از تعداد درست و جدایی ناپذیری از بیت‌ها نمایش داده می‌شود، رمزهایی پیشوندی تولید می‌کند که همیشه به کمترین طول قابل انتظار کلمات رمز می‌رسند. از آن جایی که رمزها انتها به انتها در توالی‌های بلند دسته می‌شوند این محدودیتی است که اغلب غیرضروری است. اگر گروه‌های رمزها را یک جا در نظر بگیریم، رمزگذاری نماد به نماد هافمن فقط وقتی بهینه است که احتمالات نمادها مستقل بوده و توانی از یک دوم باشند، مثلا n(2/1). در اکثر شرایط، رمزگذاری محاسباتی می‌تواند در مجموع فشرده‌سازی بیشتری نسبت به هافمن یا شانون-فانو تولید کند چرا که می‌تواند در تعداد کوچکی از بیت‌ها کدگذاری کند که به‌طور دقیق‌تری محتوای اطلاعاتی واقعی نماد را تقریب بزند. با این حال آن میزان که هافمن جایگزین شانون-فانو شده‌است رمزگذاری محاسباتی جای هافمن را نگرفته‌است چرا که هم رمزگذاری محاسباتی از لحاظ محاسبات سنگین‌تر است و هم توسط چند حق امتیاز انحصاری پوشش داده می‌شود.
رمزگذاری شانون-فانو در روش فشرده‌سازی IMPLODE که بخشی از فرمت فایل ZIP است، استفاده می‌شود.
الگوریتم شانون فانو
برای یک لیست داده شده از نمادها، یک لیست متناظر از احتمال‌ها یا فراوانی وقوع بساز به‌طوری‌که فراوانی نسبی وقوع هر نماد معلوم باشد.
لیست نمادها را بر اساس فراوانیشان مرتب کن، به‌طوری‌که بیشترین وقوع نمادها از نظر فراوانی در سمت چپ و کمترین آن در سمت راست.
لیست را به دو بخش تقسیم کن، به‌طوری‌که جمع فراوانی‌های قسمت چپ تا حد ممکن نزدیک به جمع فراوانی‌های قسمت راست باشد.
برای قسمت چپ لیست رقم دودویی ۰ گذاشته می‌شود و برای قسمت راست رقم ۱. این یعنی این که رمزها در بخش اول برای نمادها همگی با ۰ آغاز می‌شوند و رمزها در بخش دوم تماما با ۱ آغاز می‌شود.
گام‌های ۳ و ۴ را به صورت بازگشتی برای هر کدام از دو نصف‌ها اعمال کن، گروه‌ها را دوباره تقسیم کن و بیت‌ها را به رمزها اضافه کن تا هر نماد به یک برگ رمز در درخت متناظر شود.
مثال
الگوریتم شانون-فانو
در زیر ساختار کد شانون را برای تعداد کمی از حروف نشان می‌دهیم.
پنج نماد با فراوانی‌ها زیر می‌توانند به شکل زیر کد شوند:
نماد
A
B
C
D
E
شمار
۱۵
۷
۶
۶
۵
احتمال
۰٫۳۸۴۶۱۵۳۸
۰٫۱۷۹۴۸۷۱۸
۰٫۱۵۳۸۴۶۱۵
۰٫۱۵۳۸۴۶۱۵
۰٫۱۲۸۲۰۵۱۳
همه نمادها را به ترتیب فروانی‌هایشان از چپ به راست مرتب می‌کنیم. (مانند شکل a). خط جداکننده را بین نماد B و C قرار می‌دهیم. مجموع فراوانی سمت چپ ۲۲ و مجموع فروانی سمت راست ۱۷ می‌شود. این کمترین مقدار اختلاف بین مجموع فراوانی‌های دو دسته است.
با این تقسیم‌بندی کد A و B با صفر و کد C و D و E با یک شروع می‌شوند که در شکل b نمایش داده شده‌است. سپس در نیمه چپ درخت روی A و B یک تقسیم‌بندی جدید انجام می‌دهیم که A در برگ با کد ۰۰ قرار می‌گیرد و B در برگ دیگر با کد ۰۱.
بعد از چهار بار انجام روند تقسیم‌بندی درخت نهایی به دست می‌آید. در درخت نهایی سه تا از نمادها با بیشترین فراوانی با ۲ بیت و ۲ تا از نمادها با فراوانی کمتر با ۳ بیت کد شده‌اند که در جدول زیر نمایش داده شده‌است.
نماد
A
B
C
D
E
رمز
۰۰
۰۱
۱۰
۱۱۰
۱۱۱
با داشتن ۲ بیت برای A و B و C و ۳ بیت برای D و E تعداد بیت میانگین برابر است با:
الگوریتم هافمن
الگوریتم شانون-فانو همیشه کد بهینه را تولید نمی‌کند. در ۱۹۵۲ دیوید هافمن الگوریتم متفاوتی را ارائه داد که همیشه و برای هر مقادیری از احتمال‌ها درخت بهینه را تولید می‌کند. درخت شانو-فانو از ریشه به سمت برگ‌ها ساخته می‌شود درحالی که الگوریتم هافمن در جهت مخالف و از برگ به سمت ریشه کار می‌کند.
به ازای هر نماد برگی ایجاد کن و آن را به تعداد اتفاق افتادن آن اضافه کن
تا وقتی بیش از یک گره در صف موجود است مراحل زیر را انجام بده:
دو گره که کمترین فراوانی را دارند از صف حذف کن.
۰ و ۱ را به ترتیب به ابتدای کدی که قبلا با این گره‌ها نسبت داده شده بود اضافه می‌کنیم.
یک گره داخلی جدید ایجاد می‌کنیم که این دو گره فرزندان آن باشند و احتمال آن را نیز برابر جمع احتمال این دو گره قرار می‌دهیم.
این گره جدید را به صف اضافه می‌کنیم.
گره باقی‌مانده ریشه است و درخت کامل شده‌است.
مثال
الگوریتم هافمن
از همان فراوانی‌هایی که در بالا در مثال شانون-فانو استفاده کرده‌استفاده می‌کنیم:
نماد
A
B
C
D
E
شمار
۱۵
۷
۶
۶
۵
احتمال
۰٫۳۸۴۶۱۵۳۸
۰٫۱۷۹۴۸۷۱۸
۰٫۱۵۳۸۴۶۱۵
۰٫۱۵۳۸۴۶۱۵
۰٫۱۲۸۲۰۵۱۳
در این حالت D و E کمترین فراوانی را دارند پس ۰ و ۱ را به ترتیب به آن‌ها اختصاص می‌دهیم و آن‌ها را در یک گره جدید با احتمال جمع احتمال آن دو ۰٫۲۸۲۰۵۱۲۸ تجمیع می‌کنیم. اکنون کوچکترین جفت B و C هستند پس ۰ و ۱ را به آن‌ها اختصاص می‌دهیم و آن‌ها را در یک گره جدید با احتمال مجموع احتمال آن‌ها ۰٫۳۳۳۳۳۳۳۳ تجمیع می‌کنیم. حالا برگ‌های BC و DE کمترین احتمال‌ها را دارند پس ۰ و ۱ به ابتدای رمزهای آن‌ها اضافه می‌شود و آن دو با هم تجمیع می‌گردند. اکنون فقط A و BCDE باقی مانده‌اند که ۰ و۱ را بترتیب به ابتدای رمز آن‌ها اضافه می‌کنیم و بعد آن‌ها را تجمیع می‌کنیم. اکنون تنها یک گره باقی‌مانده الگوریتم ما پایان یافته‌است.
این بار طول کدها برای نمادها مختلف ۱ بیت برای A و ۳ بیت برای بقیه نماد هاست.
نماد
A
B
C
D
E
رمز
۰
۱۰۰
۱۰۱
۱۱۰
۱۱۱
با داشتن ۱ بیت برای A و ۳ بیت برای B,C،D,E میانگین طول کد برابر است با:
یادداشت