Кодування Хаффмана

Статистичне кодування Хаффмана спів ставляє вхідним символом, представленим ланцюжком бітів однакової довжини, ланцюжки бітів змінної множини. Довжина коду для символу пропорційна двійковому логарифму його частоти взятому із протилежним знаком. Це кодування є префіксним, що дозволяє легко його декодувати однопрохідним алгоритмом. Префікс ний код зручно відображати у вигляді двійкового «дерева», в якому символи знаходяться в листях, а гілки відмічені 0 або 1. тоді код символу можна задавати як шлях від кореня дерева до листка. Ущільнення інформації відбувається за 2 проходи:

1. під час 1-го проходу оцінюються частоти появи символів в початковому файлі.

2. під час 2-го проходу виконується представлення цих символів префікс ними кодами цієї довжини.

Н-д

Побудова двійкового дерева:

Символ	U	A	M	H	N	F
частота	4 3	19	7	23	27	61

26

49

70 100

Корінь

1-гілка вправо

0- гілка вліво

U	Л-Л	00
A	П-Л-Л-Л	1000
M	П-Л-Л-П	1001
H	П-Л-П	101
N	Л-П	01
F	П-П	11

Символи, які мають найбільшу частоту повторюваності мають найменшу комбінацію бітів

Оцінка ступеня ущільнення файлу

символ	частота	Кількість біт на символ	Загальна кількість
U A M H N F	43 19 7 23 27 61	2 4 4 3 2 2	86 76 28 69 54 122
всього	180		435

Об’єм вхідного (початкового) файлу – 180 байт = 1440 біт

На останньому етапі програма, що реалізує даний метод оброблює файл і замінює кожний символ на його код. Також вона записує кодове дерево у файл. Оскільки, за допомогою лише цього дерева можна знову декодувати файл. Ступінь ущільнення погіршується через те, що і кодове дерево потребує додаткової пам’яті. Таким чином алгоритм статистичного кодування способом Хаффмана буде складатись з таких етапів:

• визначення кількості повторювання кожного символу

• побудова двійкового дерева

• побудова кодової послідовності для кожного символу

• заміна символів заданого файлу відповідними кодовими послідовностями, запис результату

недоліком кодування Хаффмана є залежність ступеня стискання від близькості ймовірності символів до від’ємних степенів двійки, а також складна апаратна реалізація.

При використанні адаптивного кодування Хаффмана необхідне постійне коректування дерева у відповідності зі зміною статистики вхідного потоку. При реалізації це звичайно потребує значних витрат на пере балансування кодового дерева у відповідності з новими частотами символів на кожному кроці

АЛГОРИТМИ УЩІЛЬНЕННЯ ЗОБРАЖЕННЯ З ВТРАТАМИ