Перегляд вихідного коду сторінки Алгоритм Шеннона — Фано

[[Файл:Fano-en.svg|thumb|300x300px|Приклад кодування 6 символів.]]
'''Алгоритм Шеннона — Фано'''&nbsp;— один з перших алгоритмів [[Стиснення даних|стиснення]], який сформулювали американські вчені [[Клод Шеннон|Шеннон]] і [[Роберт Фано|Фано]]. Даний метод стиснення має велику схожість з [[Код Хаффмана|алгоритмом Хаффмана]], який з'явився на кілька років пізніше. Алгоритм використовує коди змінної довжини: символ, який часто зустрічається, кодується кодом меншої довжини, а той що рідше зустрічається&nbsp;— кодом більшої довжини. Коди Шеннона — Фано префіксні, тобто ніяке кодове слово не є [[префіксний код|префіксом]] будь-якого іншого. Ця властивість дозволяє однозначно декодувати будь-яку послідовність кодових слів.

== Основні відомості ==

''Кодування Шеннона — Фано'' ({{lang-en|Shannon-Fano coding}})&nbsp;— алгоритм префіксного неоднорідного кодування. Відноситься до [[Ймовірність|ймовірнісних]] методів стиснення (точніше, методів [[Контекстне моделювання|контекстного моделювання]] нульового порядку). Подібно [[Код Хаффмана|алгоритму Хаффмана]], алгоритм Шеннона — Фано використовує надмірність повідомлення, укладених в неоднорідному розподілі частот його символів ([[Первинний алфавіт|первинного]]) алфавіту, тобто замінює коди символів, які частіше використовуються, короткими двійковими послідовностями, а коди більш рідкісних символів&nbsp;— більш довгими двійковими послідовностями.

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

== Основні етапи ==

# Символи первинного алфавіту m<sub>1</sub> виписують в порядку зменшення ймовірностей.
# Символи отриманого алфавіту ділять на дві частини, сумарні ймовірності символів яких максимально близькі один одному.
# У префіксному коді для першої частини алфавіту присвоюється [[Двійкова система числення|двійкова]] цифра «0», другої частини&nbsp;— «1».
# Отримані частини рекурсивно діляться і їх частинам призначаються відповідні двійкові цифри в префіксному коді.

Коли розмір підалфавіту стає рівним нулю або одиниці, то наступне подовження префіксних коду для відповідних йому символів первинного алфавіту не відбувається, таким чином, алгоритм привласнює різним символам префіксні коди різної довжини. На кроці ділення алфавіту існує неоднозначність, так як різниця сумарних ймовірностей <math>p_0 - p_1</math> може бути однакова для двох варіантів поділу (враховуючи, що всі символи первинного алфавіту мають ймовірність більше нуля).

== Алгоритм обчислення кодів Шеннона — Фано ==
[[Файл:ShannonCodeAlg.svg|300px|міні|Кодування Шеннона — Фано]]
Код Шеннона — Фано будується за допомогою дерева. Побудова цього дерева починається від кореня. Вся множина кодованих елементів відповідає кореню дерева (вершині першого рівня). Воно розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Ці підмножини відповідають двом вершинам другого рівня, які з'єднуються з коренем. Далі кожна з цих підмножин розбивається на дві підмножини з приблизно однаковими сумарними ймовірностями. Їм відповідають вершини третього рівня. Якщо підмножина містить єдиний елемент, то йому відповідає кінцева вершина кодового дерева; така підмножина розбиттю не підлягає. Подібним чином поступаємо до тих пір, поки не отримаємо всі кінцеві вершини. Гілки кодового дерева розмічаємо символами 1 і 0, як у випадку [[код Хаффмана|коду Хаффмана]].

При побудові коду Шеннона — Фано розбиття множини елементів може бути обрано, взагалі кажучи, декількома способами. Вибір розбиття на рівні ''n'' може погіршити варіанти розбиття на наступному рівні (''n'' + 1) і призвести до неоптимальності коду в цілому. Іншими словами, оптимальна поведінка на кожному кроці шляху ще не гарантує оптимальності всієї сукупності дій. Тому код Шеннона — Фано не є оптимальним в загальному сенсі, хоча і дає оптимальні результати при деяких розподілах імовірностей. Для одного і того ж розподілу ймовірностей можна побудувати, взагалі кажучи, кілька кодів Шеннона — Фано, і всі вони можуть дати різні результати. Якщо побудувати всі можливі коди Шеннона — Фано для даного розподілу ймовірностей, то серед них будуть знаходитися і всі коди Хаффмана, тобто оптимальні коди.

=== Приклад кодового дерева ===

Вихідні символи:
* A (частота входження 50)
* B (частота входження 39)
* C (частота входження 18)
* D (частота входження 49)
* E (частота входження 35)
* F (частота входження 24)
{| class="wikitable"
! ||  ||  || ABCDEF(215) || || ||
|-
|  ||  || ABC(107) ||  || DEF(108)|| ||
|-
| A(50)||  || BC(57) ||  || EF(59)|| ||D(49)
|-
|  || B(39)|| C(18) ||  || E(35)||F(24) ||
|}

Отриманий код: A&nbsp;— 11,
B&nbsp;— 101,
C&nbsp;— 100,
D&nbsp;— 00,
E&nbsp;— 011,
F&nbsp;— 010.

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

== Література ==
* {{книга |автор =[[Яглом Аківа Мойсейович|А.&nbsp;М.&nbsp;Яглом]], [[Яглом Ісаак Мойсейович|И.&nbsp;М.&nbsp;Яглом]]|частина =|заголовок =Вероятность и информация|оригінал = |посилання = |відповідальний =|видання =Издание третье, переработанное и дополненное|місце = Москва|видавництво =Наука|рік = 1973|том = |сторінки =|сторінок= 512|серія = |isbn =|тираж =|ref=}} {{ref-ru}}
* ''C.&nbsp;E.&nbsp;Shannon'' [http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf A Mathematical Theory of Communication] {{Webarchive|url=https://web.archive.org/web/19980715013250/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf |date=15 липня 1998 }} // Bell System Technical Journal.&nbsp;— №&nbsp;27.&nbsp;— July 1948.&nbsp;— P. 379—423. {{ref-en}}
* ''R.&nbsp;M.&nbsp;Fano'' The transmission of information // Technical Report.&nbsp;— №&nbsp;65.&nbsp;— Cambridge (Mass., USA): Research Laboratory of Electronics at MIT, 1949.&nbsp;— P. 51. {{ref-en}}

{{refimprove|дата=грудень 2015}}
{{Алгоритм-доробити}}
{{Методи стиснення даних}}

[[Категорія:Алгоритми стиснення без втрат|Шеннона — Фано]]
[[Категорія:Клод Шеннон]]