Метод Шеннона – Фано
Оптимальне кодування
Теорема кодування Шеннона. Методи літературного оптимального кодування. Критерії оптимальності коду. Блокове кодування. Єдина система кодування текстової інформації.
Кодування,мінімізує надмірність коду,називається оптимальним.
Питання існування таких кодів становить суть однієї з основних теорем теорії інформації – теореми кодування, доведеної К. Шенноном. Наведемо одне з еквівалентних формулювань даної теореми.
Теорема кодування.Повідомлення довільного джерела інформації Z з ентропією H(Z)завжди можна закодувати послідовностями в алфавіті B,що складається з M символів,так,що середня довжина кодового слова буде як завгодно близька до величини,але не менше за неї.
Доказ цієї теореми через його складність не розглядається.
Теорема стверджує, що різницю можна зробити як завгодно малою. У цьому полягає завдання методів оптимального кодування.
Повернемося до розгляду алфавітного джерела інформації, що генерує повідомлення у символах алфавітуА. Оскільки надмірність коду задається формулою
,
Очевидно, що менше , тим оптимальніший код. Для зменшенняслід кодувати символи, що часто зустрічаються, більш короткими словами і навпаки. На дотриманні цієї вимоги ґрунтуються всі методи оптимального кодування. Крім того, для забезпечення декодування нерівномірного коду важливо дотримуватисяпринцип префіксності: жодне кодове слово не повинно бути початком іншого кодового слова.
Наведемо два найбільш відомих методи оптимального літерного кодування. Для простоти викладу візьмемо двійковий алфавіт як кодовий.
Крок 1. Упорядковуємо символи вихідного алфавіту у порядку незростання їх можливостей. (Записуємо їх у рядок.)
Крок 2. Не змінюючи порядку символів, ділимо їх у дві групи те щоб сумарні ймовірності символів у групах були по можливості рівні.
Крок 3. Приписуємо групі ліворуч "0", а групі праворуч "1" як елементи їх кодів.
Крок 4. Переглядаємо групи. Якщо кількість елементів у групі більше одного, йдемо на Крок 2. Якщо в групі один елемент, то побудова коду для нього завершена.
Мал. 4.1. Двійкове дерево, що відповідає кодуванню за методом Шеннона – Фано
Розглянемо роботу описаного алгоритму з прикладу кодування алфавіту , символи якого трапляються з ймовірностями (0,25; 0,05; 0,25; 0,1; 0,25; 0,1) відповідно. Результат кодування зображено на рис. 4.1.
Очевидно, що процес побудови коду в загальному випадку містить неоднозначність, тому що ми не завжди можемо поділити послідовність на два рівноймовірні підмножини. Або ліворуч, або праворуч сума ймовірностей буде більшою. Критерієм кращого варіанта є менша надмірність коду. Зауважимо також, що правильне зчитування коду від кореня дерева до символу забезпечить його префіксність.