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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در حوزهٔ فشرده سازی داده، رمزگذاری شانون-فانو، که بعد از کلود شانون و رابرت فانو این چنین نامیده شد، تکنیکی است برای ایجاد یک رمز پیشوندی بر مبنای مجموعه‌ای از نمادها و احتمالات (تخمین زده شده یا اندازه‌گیری شده). این تکنیک نیمه بهینه است چرا که مانند رمزگذاری هافمن به کمترین طول قابل انتظار کلمات رمز نمی‌رسد؛ با این حال بر خلاف رمزگذاری هافمن، تضمین می‌کند که تمام طول‌های کلمات رمز در یک بیت از مقدار تئوری ایده‌آل –logP(x) جای می‌گیرد. این روش در "نظریهٔ ریاضیِ ارتباطات"، مقاله شانون در سال ۱۹۴۸ در معرفی حوزهٔ نظریه اطلاعات مطرح شده است. این روش بعدها به فانو که آن را به عنوان یک گزارش روشی منتشر کرد، نسبت داده شد. رمزگذاری شانون-فانو نباید با رمزگذاری شانون اشتباه شود که روشی است برای اثبات نظریه رمزگذراری بدون اختلال شانون و همچنین نباید آن را با رمزگذاری شانون-فانو-الیاس (که به رمزگذاری الیاس معروف است) اشتباه گرفت که پیش ساز رمزگذاری محاسباتی است.

در رمزگذاری شانون-فانو، نمادها به ترتیب احتمال از زیاد به کم مرتب شده‌اند و پس از آن به دو مجموعه که احتمال کلشان تا حد ممکن به هم نزدیک است تقسیم می‌شوند. سپس اولین رقم رمز همهٔ نمادها به آن‌ها اختصاص داده می‌شود؛ نمادها در مجموعهٔ اول "۰" و در مجموعهٔ دوم "۱" می‌گیرند. تا زمانی که مجموعه‌ای با بیش از یک عضو باقی بماند، همین فرایند برای تعیین ارقام متوالی رمزهایشان، روی آن‌ها تکرار می‌شود. وقتی یک مجموعه به یک نماد کاهش پیدا کند بدان معناست که رمز آن نماد کامل است و پیشوند هیچ رمزِ نماد دیگری را تشکیل نمی‌دهد. این الگوریتم کدگذاری‌های با طول متغیر نسبتاً کارامدی تولید می‌کند. وقتی دو مجموعهٔ کوچک‌تر که با یک تقسیم بندی ایجاد شده‌اند در واقع دارای احتمال برابری هستند، یک بیت اطلاعاتی که برای تمایز آن‌ها استفاده می‌شود، به بهینه ترین نحو به کار گرفته می‌شود. متأسفانه شانون-فانو همیشه پیشوند رمزهای بهینه تولید نمی‌کند؛ مجموعهٔ احتمالات {۰٫۳۵،۰٫۱۷،۰٫۱۷،۰٫۱۶،۰٫۱۵} مثالی است که به آن رمزهای نابهینه‌ای توسط رمزگذاری شانون-فانو اخصاص داده می‌شود.

به همین دلیل، شانون-فانو تقریباً هیچ وقت استفاده نمی‌شود. رمزگذاری هافمن تقریباً از نظر محاسباتی ساده است و تحت محدودیت‌هایی که هر نماد با یک رمز متشکل از تعداد درست و جدایی ناپذیری از بیت‌ها نمایش داده می‌شود، رمزهایی پیشوندی تولید می‌کند که همیشه به کمترین طول قابل انتظار کلمات رمز می‌رسند. از آن جایی که رمزها انتها به انتها در توالی‌های بلند دسته می‌شوند این محدودیتی است که اغلب غیر ضروری است. اگر گروه‌های رمزها را یک جا در نظر بگیریم، رمزگذاری نماد به نماد هافمن فقط وقتی بهینه است که احتمالات نمادها مستقل بوده و توانی از یک دوم باشند، مثلاً n(2/1). در اکثر شرایط، رمزگذاری محاسباتی می‌تواند در مجموع فشرده سازی بیشتری نسبت به هافمن یا شانون-فانو تولید کند چرا که می‌تواند در تعداد کوچکی از بیت‌ها کدگذاری کند که به طور دقیق تری محتوای اطلاعاتی واقعی نماد را تقریب بزند. با این حال آن میزان که هافمن جایگزین شانون-فانو شده است رمزگذاری محاسباتی جای هافمن را نگرفته است چرا که هم رمزگذاری محاسباتی از لحاظ محاسبات سنگین تر است و هم توسط چند حق امتیاز انحصاری پوشش داده می‌شود.

رمزگذاری شانون-فانو در روش فشرده سازی IMPLODE که بخشی از فرمت فایل ZIP است، استفاده می‌شود.[۱]

الگوریتم شانون فانو[ویرایش]

  1. برای یک لیست داده شده از نمادها، یک لیست متناظر از احتمال‌ها یا فراوانی وقوع بساز به طوری که فراوانی نسبی وقوع هر نماد معلوم باشد.
  2. لیست نمادها را بر اساس فراوانیشان مرتب کن، به طوری که بیشترین وقوع نمادها از نظر فراوانی در سمت چپ و کمترین آن در سمت راست.
  3. لیست را به دو بخش تقسیم کن، به طوری که جمع فراوانی‌های قسمت چپ تا حد ممکن نزدیک به جمع فراوانی‌های قسمت راست باشد.
  4. برای قسمت چپ لیست رقم دودویی ۰ گذاشته می‌شود و برای قسمت راست رقم ۱. این یعنی این که رمزها در بخش اول برای نمادها همگی با ۰ آغاز می‌شوند و رمزها در بخش دوم تماماً با ۱ آغاز می‌شود.
  5. گام‌های ۳ و ۴ را به صورت بازگشتی برای هر کدام از دو نصف‌ها اعمال کن، گروه‌ها را دوباره تقسیم کن و بیت‌ها را به رمزها اضافه کن تا هر نماد به یک برگ رمز در درخت متناظر شود.

مثال[ویرایش]

الگوریتم شانون-فانو

در زیر ساختار کد شانون را برای تعداد کمی از حروف نشان می‌دهیم. پنج نماد با فراوانی‌ها زیر می‌توانند به شکل زیر کد شوند:

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

مثال[ویرایش]

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

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

نماد 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.}

یادداشت[ویرایش]

  1. "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 2007-09-28. 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." 

منابع[ویرایش]