1.2.5.3. Класичний метод Хаффмена
Метод Хаффмана – це статистичний метод, що будує коди змінної довжини з мінімальною середньою довжиною. Базуючись на ймовірності появи символів алфавіту в тексті. Базується на створенні так званого дерева Хаффмана, що будується за наступним алгоритмом [6]:
1) Будується список вільних вузлів (листів), утворених символами алфавіту в порядку зменшення їх ймовірностей появи в тексті. Кожен лист має вагу, що дорівнює його ймовірності.
2) Вибираються два “листки” дерева з найменшою вагою та створюється їх предок з вагою, рівною їх сумарній вазі.
3) Предок додається до списку вільних вузлів, а двоє його нащадків видаляються з цього списку.
4) Одній дузі (гілці), що виходить з предка, приписується значення 1, а іншій – 0.
5) Кроки 2-4 повторюються до тих пір, доки не залишиться єдиний вільний вузол – корінь дерева.
6) Побудова коду символа здійснюється спуском по дереву від кореня до відповідного листа.
Зауважимо!!! Дані з рівноможливими символами не стискаються методом Хаффмана.
Краще за все проілюструвати даний алгоритм на простому прикладі, наведеному у наступному пункті.
Проілюструємо принцип роботи методу прикладом. Маємо п'ять символів з ймовірностями, заданими на рис. 1.7.
Рис. 1.7. Дерево Хаффмена
Символи об'єднуються в пари згідно алгоритму, наведеному раніше, в наступній послідовності:
1) а4 об'єднується з а5 й обидва замінюються комбінованим символом а45 з ймовірністю 0.2;
2) залишились символ а1 з ймовірністю 0.4 та три символи а2, а3, а45 з ймовірностями 0.2. Довільно вибираємо а3 та а45, об'єднуємо їх та замінюємо комбінованим символом а345 з ймовірністю 0.4;
3) маємо три символи а1, а2, а345 з ймовірностями 0.4 ,0.2 та 0.4, відповідно. Вибираємо та об'єднуємо символи а2 та а345 в комбінований символ а2345 з ймовірністю 0.6;
4) нарешті, об'єднуємо символи а1 та а2345 й замінюємо їх на а12345 з ймовірністю 1.
Дерево Хаффмана побудовано. Для призначення кодів приписуємо біт 1 гілці, яка виходить з вузла з більшою ймовірністю, іншій приписуємо біт 0.
Зчитуючи коди від кореня дерева Хаффмана до відповідних вузлів, отримаємо значеня, наведені в табл. 1.2.
Таблиця 1.2. Коди хаффмена
аі |
Код |
а1 |
0 |
а2 |
10 |
а3 |
111 |
а4 |
1101 |
а5 |
1100 |
Зауважимо, що кожен з кодів не являється префіксом іншого (правило префікса), й символи з вищою ймовірністю представлені коротшими кодами.
При декомпресії в стиснутий файл записуються ймовірності символів. Коли декомпресор відновлює вихідні дані, він будує дерево Хаффмана, спираючись на отриману інформацію про ймовірності.
Декомпресор починає з кореня й зчитує перший біт, в залежності від того, 0 це чи 1, він пересувається по відповідній гілці, відміченій цим бітом.
Далі зчитується другий біт й відбувається просування по наступній гілці у напрямку до листя.
Коли декомпресор дістається листа, він визначає перший нестиснутий символ. Процедура повторюється для наступного біту, починаючи знов від кореня дерева.
1.2.5.4. JBIG|
Алгоритм розроблений групою експертів ISO| (Joint| Bi-level| Experts| Group|) спеціально для стиснення однобітових| чорно-білих зображень [7]. Наприклад, факсів або відсканованих документів. В принципі, може застосовуватися і до 2-х, і до 4-х бітових зображень. При цьому алгоритм розбиває їх на окрему бітову площину. JBIG| дозволяє управляти такими параметрами, як порядок|лад| розбиття зображення на бітову площину, ширина смуг в зображенні, рівні масштабування. Остання можливість|спроможність| дозволяє легко орієнтуватися в базі великих по розмірах зображень, проглядаючи спочатку їх зменшені копії. Настроюючи|набудовувати| ці параметри, можна використовувати описаний вище ефект “огрубленого зображення” при отриманні|здобутті| зображення мережею або по будь-якому іншому каналу, пропускна спроможність якого мала в порівнянні з можливостями|спроможностями| процесора. Розпаковуватися зображення на екрані буде поступове, як би поволі|повільно| “виявляючись”. При цьому людина починає|розпочинає| аналізувати картинку задовго до кінця процесу розархівування.
Алгоритм побудований|спорудити| на базі Q-кодера|, патентом на який володіє IBM|. Q-кодер|, так само як і алгоритм Хаффмана, використовує для частіше за символи, що з'являються|появляються|, короткі ланцюжки, а для що рідше з'являються|появляються| — довгі. Проте|однак|, на відміну від нього, в алгоритмі використовуються і послідовності символів.
1.2.5.5. Lossless| JPEG|
Цей алгоритм розроблений групою експертів в області фотографії (Joint| Photographic| Expert| Group|) [8]. На відміну від JBIG|, Lossless| JPEG| орієнтований на повнокольорові 24-бітові або 8-бітові в градаціях сірого зображення без палітри. Він є спеціальною реалізацією JPEG| без втрат. Коефіцієнти стиснення: 20, 2, 1. Lossless| JPEG| рекомендується застосовувати в тих програмах, де необхідна побітова відповідність початкового|вихідного| і декомпресованого зображень.