Код Шеннона-Фано

Алгоритм коду Шеннона-Фано полягає в наступному: літери вихідного алфавіту повідомлення виписуються в стовпець в порядку зменшення їх ймовірностей; проводиться розбиття на дві групи з рівною по можливості сумарною ймовірністю, всім літерам верхньої групи в якості першого символу кодової комбінації приписується «1», а нижній - «0»; потім виконують такі розбиття до тих пір, поки в кожній підгрупі не залишиться одна літера (при кожному розбитті з'являється новий символ кодової комбінації за правилами, викладеними вище).

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

Розглянемо приклад побудови коду Шеннона-Фано для попереднього прикладу.

A_i p(A_i) Допоміжні стовпці

A₁	0.4	0.4
A₂	0.25	0.6	0.25
A₃	0.15		0.35	0.15
A₄	0.10			0.20	0.10
A₅	0.06				0.10	0.6
A₆	0.04					0.4

Складемо таблицю кодування.

A_ip(A_i) Допоміжні стовпці

A₁	0.4	0.40
A₂	0.25	0.61	0.2510
A₃	0.15		0.3511	0.15110
A₄	0.10			0.20111	0.101110
A₅	0.06				0.101111	0.611110
A₆	0.04					0.411111

Отриманий код:

A₁	A₂	A₃	A₄	A₅	A₆

У нашому випадку результати кодування обома методами збігаються.

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

Читайте також:

I Метод Шеннона-Фано

<== попередня сторінка	\|	наступна сторінка ==>
Код Хаффмена	\|	Перевірка оптимальності коду

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.