пристрої повинні розташовуватися як з боку передавача, так і з боку приймача. Як правило, вони дають гарні коефіцієнти стиснення і прийнятні затримки, але вони застосовні лише при з'єднаннях точка-точка. Такі пристрої можуть бути зовнішніми або вбудованими, з'явилися й спеціальні інтегральні схеми, які вирішують завдання стиснення/декомпресії. На практиці це може вирішуватися як апаратно, так і програмно, можливі й комбіновані рішення.
Якщо при роботі з пакетами заголовки залишати незміненими, а стискати тільки інформаційні поля, обмеження на використання стандартних маршрутизаторів може бути знято. Пакети будуть доставлятися кінцевому адресату, і тільки там буде виконуватися процедура декомпресії. Така схема стиснення даних прийнятна для мереж X.25, SMDS, Frame Relay і ATM. Маршрутизатор корпорації CISCO підтримують практично всі режими стиснення/декомпресії інформації, перераховані вище.
Цій проблемі присвячено багато книг, наприклад, David Salomon, Giovanni Motta, Handbook of Data Compression raquo ;, Springer, або Khalid Sayood, Introduction to data compression raquo ;. Обидві книги можна, принаймні частково, переглянути через Інтернет. За останні 15 років ці технології досить мало змінилися.
Статичний алгоритм Хафмана
Статичний алгоритм Хафмана можна вважати класичним.
Нехай повідомлення m (1), ..., m (n) мають ймовірності P (m (1)), ... P (m (n)) і нехай для визначеності вони впорядковані так, що P ( m (1)) і P (m (2)) і ... і P (m (N)). Нехай x1, ..., xn - сукупність двійкових кодів і нехай l1, l2, ..., lN довжини цих кодів. Завданням алгоритму є встановлення відповідності між m (i) і xj. Можна показати, що для будь-якого ансамблю повідомлень з повним числом більше 2 існує двійковий код, в якому два найменш вірогідних коду xN і xN - 1 мають одну і ту ж довжину і відрізняються лише останнім символом: xN має останній біт 1, а xN - 1- 0. Редукований ансамбль матиме свої два найменш вірогідні повідомлення, згрупованими разом. Після цього можна отримати новий редукований ансамбль і так далі. Процедура може бути продовжена доти, поки в черговому ансамблі не залишиться тільки два повідомлення. Процедура реалізації алгоритму зводиться до наступного (див. Рис. 2.). Спочатку групуються дві найменш вірогідні повідомлення, передостаннього повідомленням ставиться у відповідність код з молодшим бітом, рівним нулю, а останньому - код з одиничним молодшим бітом (на малюнку m (4) і m (5)). Вірогідність цих двох повідомлень складаються, після чого шукаються дві найменш вірогідні повідомлення у знову отриманому ансамблі (m (3) і m` (4); p (m` (4))=p (m (4)) + P (m ( 5))).
Рис. 2. Приклад реалізації алгоритму Хафмана
На наступному кроці найменш вірогідними повідомленнями виявляться m (1) і m (2). Кодові слова на отриманому дереві зчитуються справа наліво. Алгоритм видає оптимальний код (мінімальна надмірність).
Але при використанні кодів різної довжини можуть виникнути проблема поділ кодових слів при послідовній пересиланні. Наприклад, нехай lt; (a, 1); (b, 01); (c, 101); (d, 011) gt ;, тоді бітова послідовність +1011 може бути інтерпретована як aba, ca або ada. Щоб уникнути цієї невизначеності можна посилати код довжини перед кожним символом, що пов'язано з пересилкою додаткових даних. Більш ефективним рішенням є конструювання кодів, в яких ми можемо завжди однозначно перетворити бітову послідовність у кодове слово. Кодом такого типу є префіксний код, в якому ніяка бітова рядок не є префіксом іншого коду. Наприклад, lt; (a, 1); (b.01); (c, 000); (d, 001) gt ;. Префіксние коди мають ту перевагу перед іншими кодами, що ми можемо дешифрувати будь-яке повідомлення без необхідності виявлення початку наступного. Префіксний код може бути представлений у вигляді двійкового дерева:
· Кожне повідомлення є листом дерева.
· Код кожного повідомлення визначається рухом від кореня до листа, причому до коду додається 0 для відгалуження вліво і 1 - для відгалуження вправо.
Таке дерево називається деревом префіксних кодів. Це дерево може використовуватися і при декодуванні префіксних кодів. При надходженні бітів декодер може слідувати уздовж дерева, поки не досягне листа, формуючи таким способом повідомлення. Після цього при вступі чергового біта здійснюється повернення до кореня дерева і процедура повторюється. При декодуванні можуть використовуватися кілька префіксних дерев.
При використанні кодування за схемою Хафмана треба разом з закодованим текстом передати відповідний алфавіт. При передачі великих фрагментів надмірність, сполучена з цим не може бути значною. Для одного і того ж масиву біт можуть бути сформовані різні алфавіти, але вони будуть о...
