|
Коли розмір підалфавіту стає рівним нулю або одиниці, то наступне подовження префіксних коду для відповідних йому символів первинного алфавіту не відбувається, таким чином, алгоритм привласнює різним символам префіксні коди різної довжини. На кроці ділення алфавіту існує неоднозначність, так як різниця сумарних ймовірностей <math>p_0 - p_1</math> може бути однакова для двох варіантів поділу (враховуючи, що всі символи первинного алфавіту мають ймовірність більше нуля).
== Алгоритм обчислення кодів Шеннона - Фано ==
Код Шеннона - Фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Їм відповідають вершини третього рівня. Якщо підмножина містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Подібним чином поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0, як у випадку коду Хаффмана.
При побудові коду Шеннона-Фано розбиття множини елементів може бути виробленообрано, взагалі кажучи, декількома способами. Вибір розбиття на рівні ''n'' може погіршити варіанти розбиття на наступному рівні (''n'' + 1) і призвести до неоптимальності коду в цілому. Іншими словами, оптимальна поведінка на кожному кроці шляху ще не гарантує оптимальності всієї сукупності дій. Тому код Шеннона-Фано не є оптимальним в загальному сенсі, хоча і дає оптимальні результати при деяких розподілах імовірностей. Для одного і того ж розподілу ймовірностей можна побудувати, взагалі кажучи, кілька кодів Шеннона - Фано, і всі вони можуть дати різні результати. Якщо побудувати всі можливі коди Шеннона - Фано для даного розподілу ймовірностей, то серед них будуть знаходитися і всі коди Хаффмана, тобто оптимальні коди.
=== Приклад кодового дерева ===
F - 010.
Кодування Шеннона-Фано є досить старим методом стиснення, і на сьогоднішній день вонавоно не представляє особливого практичного інтересу. У більшості випадків, довжина послідовності, стислійстиснутої за цим методом, дорівнює довжині стислійстиснутої послідовності з використанням кодування Хаффмана. Але на деяких послідовностях можуть сформуватися неоптимальні коди Шеннона-Фано, тому більш ефективним вважається стиснення методом Хаффмана.
== Література ==
|
