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

در حوزهٔ فشرده سازی داده ها، کدینگ یا کدگذاری شانون-فانو، که به افتخار کلود شانون و رابرت فانو این چنین نامیده شده، تکنیکی است، برای ایجاد یک کد پیشوندی (Prefix Code)، بر مبنای مجموعه‌ای از نمادها و احتمالات (تخمین زده شده یا اندازه‌گیری شده). این تکنیک نیمه بهینه است؛ چرا که مانند کدگذاری هافمن ،به کمترین طول قابل انتظار کلمات کد (Codewords) نمی‌رسد؛ با این حال بر خلاف کدگذاری هافمن، تضمین می‌کند که تمام طول‌های کلمات کد در یک بیت از مقدار تئوری ایده‌آل –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 تعداد بیت میانگین برابر است با:

{\frac {2\,{\text{bits}}\cdot (15+7+6)+3\,{\text{bits}}\cdot (6+5)}{39\,{\text{symbols}}}}\approx 2.28\,{\text{bits per symbol.}}

الگوریتم هافمن

الگوریتم شانون-فانو همیشه کد بهینه را تولید نمی‌کند. در ۱۹۵۲ دیوید هافمن الگوریتم متفاوتی را ارائه داد که همیشه و برای هر مقادیری از احتمال‌ها درخت بهینه را تولید می‌کند. درخت شانو-فانو از ریشه به سمت برگ‌ها ساخته می‌شود درحالی که الگوریتم هافمن در جهت مخالف و از برگ به سمت ریشه کار می‌کند.

به ازای هر نماد برگی ایجاد کن و آن را به تعداد اتفاق افتادن آن اضافه کن
تا وقتی بیش از یک گره در صف موجود است مراحل زیر را انجام بده:
1. دو گره که کمترین فراوانی را دارند از صف حذف کن.
2. ۰ و ۱ را به ترتیب به ابتدای کدی که قبلاً با این گره‌ها نسبت داده شده بود اضافه می‌کنیم.
3. یک گره داخلی جدید ایجاد می‌کنیم که این دو گره فرزندان آن باشند و احتمال آن را نیز برابر جمع احتمال این دو گره قرار می‌دهیم.
4. این گره جدید را به صف اضافه می‌کنیم.
گره باقی‌مانده ریشه است و درخت کامل شده‌است.

مثال

الگوریتم هافمن

از همان فراوانی‌هایی که در بالا در مثال شانون-فانو استفاده کرده‌استفاده می‌کنیم:

نماد	A	B	C	D	E
شمار	۱۵	۷	۶	۶	۵
احتمال	۰٫۳۸۴۶۱۵۳۸	۰٫۱۷۹۴۸۷۱۸	۰٫۱۵۳۸۴۶۱۵	۰٫۱۵۳۸۴۶۱۵	۰٫۱۲۸۲۰۵۱۳

در این حالت D و E کمترین فراوانی را دارند پس ۰ و ۱ را به ترتیب به آن‌ها اختصاص می‌دهیم و آن‌ها را در یک گره جدید با احتمال جمع احتمال آن دو ۰٫۲۸۲۰۵۱۲۸ تجمیع می‌کنیم. اکنون کوچکترین جفت B و C هستند پس ۰ و ۱ را به آن‌ها اختصاص می‌دهیم و آن‌ها را در یک گره جدید با احتمال مجموع احتمال آن‌ها ۰٫۳۳۳۳۳۳۳۳ تجمیع می‌کنیم. حالا برگ‌های BC و DE کمترین احتمال‌ها را دارند پس ۰ و ۱ به ابتدای کدهای آن‌ها اضافه می‌شود و آن دو با هم تجمیع می‌گردند. اکنون فقط A و BCDE باقی مانده‌اند که ۰ و۱ را بترتیب به ابتدای کد آن‌ها اضافه می‌کنیم و بعد آن‌ها را تجمیع می‌کنیم. اکنون تنها یک گره باقی‌مانده الگوریتم ما پایان یافته‌است.

این بار طول کدها برای نمادها مختلف ۱ بیت برای A و ۳ بیت برای بقیه نماد هاست.

نماد	A	B	C	D	E
کد	۰	۱۰۰	۱۰۱	۱۱۰	۱۱۱

با داشتن ۱ بیت برای A و ۳ بیت برای B,C،D,E میانگین طول کد برابر است با:

{\frac {1\,{\text{bit}}\cdot 15+3\,{\text{bits}}\cdot (7+6+6+5)}{39\,{\text{symbols}}}}\approx 2.23\,{\text{bits per symbol.}}

یادداشت

↑ "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 2007-09-28. Archived from the original on 5 December 2014. Retrieved 2008-01-06. The Imploding algorithm is actually a combination of two distinct algorithms. The first algorithm compresses repeated byte sequences using a sliding dictionary. The second algorithm is used to compress the encoding of the sliding dictionary output, using multiple Shannon–Fano trees.

منابع

Shannon, C.E. (July 1948). "A Mathematical Theory of Communication" (PDF). Bell System Technical Journal. 27: 379–423. Archived from the original (PDF) on 15 July 1998. Retrieved 25 May 2014.
Fano, R.M. (1949). "The transmission of information". Technical Report No. 65. Cambridge (Mass.), USA: Research Laboratory of Electronics at MIT.

[appnote-1] "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 2007-09-28. Archived from the original on 5 December 2014. Retrieved 2008-01-06. The Imploding algorithm is actually a combination of two distinct algorithms. The first algorithm compresses repeated byte sequences using a sliding dictionary. The second algorithm is used to compress the encoding of the sliding dictionary output, using multiple Shannon–Fano trees.