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