Алгоритм Шеннона Фано. 
Алгоритм Шеннона-Фано

Алгоритм Шеннона-Фано — один з перших алгоритмів стиснення, який сформулювали американські вчені Шеннон і Фано. Даний метод стиснення має велику схожість з алгоритмом Хаффмана, який з’явився на кілька років пізніше. Алгоритм використовує коди змінної довжини: символ, який часто зустрічається, кодується кодом меншої довжини, а той що рідше зустрічається — кодом більшої довжини. Коди Шеннона-Фано префіксні, тобто ніяке кодове слово не є префіксом будь-якого іншого. Ця властивість дозволяє однозначно декодувати будь-яку послідовність кодових слів.

Кодування Шеннона-Фано (англ. Shannon-Fano coding) — алгоритм префіксного неоднорідного кодування. Відноситься до ймовірнісних методів стиснення (точніше, методів контекстного моделювання нульового порядку). Подібно алгоритму Хаффмана, алгоритм Шеннона-Фано використовує надмірність повідомлення, укладених в неоднорідному розподілі частот його символів (первинного) алфавіту, тобто замінює коди символів, які частіше використовуються, короткими двійковими послідовностями, а коди більш рідкісних символів — більш довгими двійковими послідовностями.

Алгоритм був незалежно один від одного розроблений Шенноном (публікація «Математична теорія зв’язку», 1948 рік) і, пізніше, Фано (опубліковано як технічний звіт).

Код Шеннона-Фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Їм відповідають вершини третього рівня. Якщо підмножина містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Подібним чином поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0.

Відмінності між кодм Хаффмана та кодом Шеннона-Фано:

• · Алгоритм Хаффмана рухається від листків до кореня, а алгоритм Ш-Ф, використовуючи ділення, рухається від кореня до листків
• · На деяких послідовностях можуть сформуватися неоптимальні коди Шеннона-Фано, тому більш ефективним вважається стиснення методом Хаффмана

алгоритм кодування шеннон фано.