3.5 Кодування Хафмана в jpeg.
В комп’ютерній техніці набори символів маже завжди представляють методами кодування з фіксованою довжиною коду (fixed-length encoding method)(напр. ASCII чи EBCDIC), які не враховують частоту їх використання в роботі. Це дуже ефективно для досягнення найбільшої швидкості обчислень. Але при стисненні зображень де розмір даних відіграє велику роль, доцільно використовувати коди змінної довжини. За таким методом кодується, наприклад, азбука морзе. (* = «Є»;- = «Т»).
Найвідомішим шрифтом генерування кодів змінної довжини, на основі частоти їх використання є метод кодування Хафмана (запропонований в 1952р.)
Процедура формування кодів Хафмана вимагає створення двійкового дерева, що вміщує символи. Символ, що зустрічаються рідко знаходяться далі від кореня. Створюється так-званий пул (pool), який може вміщувати значення та вузли дерева. Початково цей пул має всі значення і не вміщує вузлів.
Алгоритм (процедура) кодування Хафмана.
1.Знайти два значення чи вузли дерева з найменшою частотою появи і видалити їх з пулу.
2. Створити новий вузол дерева і зробити елементи із попереднього кроку його гілками.
3. Присвоїти новому вузлу дерева частоту, що дорівнює сумі частот гілок, що відходять від
нього.
4.Добавити створений вузол в пул.
Ця процедура повторюється до тих пір, поки пул не буде складатись з одного вузла дерева і в ньому не буде жодного вузла дерева і в ньому не буде жодного вузла символу. Після цього кожному вузлу дерева призначається значення 0 одній його гілці, та значення 1 другій. Код Хафмана визначається проходом по шляху від кореня дерева до даного значення і додаванням у загальний код, коду кожної гілки.
Множина кодових значень утворює так-звану таблицю Хафмана.
Приклад кодування Хафмана.
Закодуємо поліндром(рядок, що читається однаково за обома напрямками):
A MAN A PLAN A CANAL PANAMA .
Початковій пул:
A C L M N P <SPACE> .
10 1 2 2 4 2 6 1
1. Два значення з найменшою появою у тексті (=1)-символи «С» та «.». Використовуємо ці символи для створення вузла дерева. Призначаємо цьому вузлу значення частоти, що дорівнює частоті гілок, що відходять від вузла. Маємо пул з вузлом дерева:
A L M N P <SPACE>
1
0
2 2 4 2 6
2
С .
1 1
2. Чотири елементи, що відображені в пулі, мають нижчу частоту, що = 2. Беремо «P» і вузол дерева, з’єднуємо їх між собою, щоб створити новий вузол дерева із сумарною частотою, що = 4.
A L M N <SPACE>
10 2 2 4 6
4
Р 2
2
С .
1 1
3.Тепер із залишених символів найменша частота зустрічається у букв L та M. Оскільки всім доступним гілкам дерева призначені більші частоти, необхідно створити новий вузол, не з’єднаний з деревом:
A N <SPACE>
10 4 4 6 4
2
L M Р
2 2 2 С .
1 1
4. Тепер є два вузли дерева та буква «N», що зв’язані з найменшою частотою, що = 4. Ми обираємо букву «N» і приєднуємо її до дерева:
8
A <SPACE>
10 4 6 N 4
4 2
L M Р
2 2 2 С .
1 1
5. Із залишених елементів:
A
10 10 8
<SPACE> 4 N 4
6 4 2
L M Р
2 2 2 С .
1 1
6. Тепер залишились 2 вузла дерева та буква «А». Ми довільно вирішуємо з’єднати два вузли дерева, а не букву з одним із цих вузлів:
A 18
10 10 8
<SPACE> 4 N 4
6 4 2
L M Р
2 2 2 С .
1 1