и:
- 00, B - 01, C - 10, D - 11
ми отримаємо повідомлення 000100101000110000 довжиною 18 біт. Тепер побудуємо код Хаффмана, використовуючи дерево Хаффмана. p> Для цього спочатку потрібно переглянути весь вихідний текст і отримати ймовірність (або, що простіше - частоту) кожного вхідного в нього символу. Далі, візьмемо два найрідкісніших коду і об'єднаємо їх в єдиний вузол, частота появи якого дорівнює сумі частот появи входять до нього символів. Розглядаючи цей вузол, як новий символ, який об'єднує два попередні, будемо повторювати операцію злиття символів доти, поки не залишиться жодної букви з вхідного алфавіту. Отримаємо дерево, де листям є символи вхідного алфавіту, а вузлами - з'єднання символів з листів-нащадків даного вузла. Розглядаючи кожну ліву гілку як 0, а праву як 1 і спускаючись по дереву вниз до листя, отримаємо код будь-якого символу:
- 0, B - 110, C - 10, D - 111
Оригінал повідомлення після кодування стане 011001010011100 (15 біт). Ступінь стиснення: 15/18 = 83%. Легко переконатися, що маючи коди Хаффмана, можна однозначно відновити первісний текст
Інший алгоритм побудови оптимальних префіксних кодів, що дає аналогічний результат, був запропонований Шенноном і Фано.
Недоліком такого кодування є той факт, що разом з закодованим повідомленням необхідно передавати також і побудовану таблицю кодів (дерево), що знижує величину стиснення. Однак існує динамічний алгоритм побудови дерева Хаффмана, при якому кодова таблиця оновлюється самим кодувальником і (синхронно і аналогічно) декодувальнику в процесі роботи після отримання кожного чергового символу. Отримувані при цьому коди виявляються Квазіоптимальний, тому текст стискається дещо гірше. Більше того, зростають складність алгоритму і час роботи програми (хоча вона і стає однопрохідної), тому, в даний час динамічний алгоритм майже повністю поступився місцем статичному.
Наступним варіантом розглянутого алгоритму є фіксований алгоритм Хаффмена, що поєднує в собі переваги двох попередніх - високу швидкість роботи, простоту і відсутність додаткового словника, що створює зайву надмірність. Ідея його в тому, щоб користуватися деякими усередненими по багатьом текстам деревом, однаковим для кодувальника і декодувальнику. Таке дерево не треба будувати і передавати разом з текстом, а значить-відпадає необхідність першого проходу. Але, з іншого боку, усереднене фіксоване дерево виявляється ще більш неоптимальним, ніж динамічне. Тому, іноді може бути зручно мати кілька фіксованих дерев для різних видів інформації.
В· Варіантами дерева Хаффмана слід також вважати дерева, отримані для монотонних джерел. Ці джерела мають два важливих для наших цілей характеристики:
В· немає необхідності обчислювати частоти появи символів ...
