Визначення 1: Нехай A = 1, a2,. , An> - алфавіт з n різних символів, W = 1, w2,. , Wn> - відповідний йому набір позитивних цілих ваг. Тоді набір бінарних кодів C = 1, c2,. , Cn>, такий що:
(1) ci не є префіксом для cj. при i ≠ j
(2) мінімальна (| ci | довжина коду ci)
Називається мінімально-надлишковим префіксним кодом або інакше кодом Хаффмана.
1. Властивість (1) називається властивістю префіксних. Воно дозволяє однозначно декодувати коди змінної довжини.
2. Суму в властивості (2) можна трактувати як розмір закодованих даних в бітах. На практиці це дуже зручно, тому що дозволяє оцінити ступінь стиснення не вдаючись безпосередньо до кодування.
3. Надалі, щоб уникнути непорозумінь, під кодом будемо розуміти бітову рядок певної довжини, а під мінімально-надлишковим кодом або кодом Хаффмана - безліч кодів (бітових рядків), які відповідають певним символам і володіють певними властивостями.
Відомо, що будь-якому бінарним префіксних коду відповідає певний бінарне дерево.
Визначення 2: Бінарне дерево, що відповідає коду Хаффмана, будемо називати деревом Хаффмана.
Завдання побудови коду Хаффмана рівносильна задачі побудови відповідного йому дерева. Наведемо загальну схему побудови дерева Хаффмана:
літери розташовують в порядку убування їх ймовірностей. Складають ймовірності двох останніх букв, і ряд переписують знову з урахуванням нової ймовірності (суми). Далі повторюють операцію, поки не вийде 1. Нижню букву завжди кодують нулем, а верхню - одиницею.
Для складання кодових комбінацій будується кодове дерево. Рухаючись по кодовому дереву зверху вниз, можна записати для кожної літери відповідну їй кодову комбінацію.
Код Хаффмана, також як і Шеннона-Фано є префіксним, тобто в такому коді жодна комбінація не збігається з початком довшою комбінації, а це дозволяє забезпечити однозначне декодування без введення розділових знаків.
Середнє у розрядів:
Як ми бачимо, величина середнього кількості розрядів вийшла досить близькою до ентропії, отже, код можна вважати ефективним. При цьому для порівняння можна обчислити величину K для рівномірного коду:
Нехай є випадкова величина X (x1, x2, x3, x4, x5, x6, x7, x8), що має вісім станів з розподілом ймовірностей
Всі букви записуються в порядку убування їх ймовірностей, потім діляться на рівноімовірні групи, які позначаються 0 і 1, потім знову діляться на рівноімовірні групи і т.д.
побудувати дерево Хаффмана для повідомлення S = "A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H".
Нехай є наступна таблиця префіксних кодів:
Розкодування повідомлення: +00100010000111010101110000110
ВКАЗІВКА. Декодування проводиться циклічним повторенням наступних дій:
1. відрізати від поточного повідомлення крайній лівий символ, приєднати до робочого кодовим словом;
2. порівняти робоче кодове слово з кодовою таблицею; якщо збігу немає, перейти до (1);
3. декодувати робоче кодове слово, очистити його;
4. перевірити, чи є ще знаки в повідомленні; якщо «так», перейти до (1).
Нехай є первинний алфавіт A. складається з шести знаків a1 ... a6 з ймовірності появи в повідомленні, відповідно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05.
Побудувати код Хаффмана
Закодуйте двійковим кодом Шеннона-Фано ансамбль повідомлень Х = х1, х2. х8, якщо все кодуються повідомлення різновірогідні. Показати оптимальний характер отриманого коду.
Визначте кількість елементів в кодовому слові, якщо відомо загальна кількість комбінацій N = 512, а підстава коду 2.
Скільки двійкових чисел може бути представлено 7-розрядних кодом?
Дана сукупність символів х1, х2, х3, х4 з наступною статистикою відповідно: 0,28; 0,14; 0,48; 0,10. Закодуйте символи за методом Шеннона-Фано і визначте ефективність коду.