Алгоритми стиснення - Кодування інформації
Стиснення даних здійснюється або на прикладному рівні за допомогою програм стиснення, таких як ARJ, або за допомогою пристроїв захисту від помилок (ПЗВ) безпосередньо у складі модемів за протоколами типу V.42bis.
Очевидний спосіб стиснення числової інформації, представленої в коді ASCII, полягає у використанні скороченого коду з чотирма бітами на символ замість восьми, оскільки передається набір, що включає лише 10 цифр, символи "точка", "кома" і "пробіл".
Серед простих алгоритмів стиснення найбільш відоміалгоритми RLE (Run Length Encoding). У них замість передачі ланцюжка з однакових символів передаються символ і значення довжини ланцюжка. Метод ефективний під час передачі растрових зображень, але малокорисний під час передачі тексту.
До методів стиснення відносять такожметоди різницевого кодування, оскільки різниці амплітуд відліків видаються меншим числом розрядів, ніж самі амплітуди. Різнинне кодування реалізовано в методах дельта-модуляції та її різновидах.
Пророчі (предиктивні) методизасновані на екстраполяції значень амплітуд відліків, і якщо виконано умову
то відлік має бути переданий, інакше він є надлишковим; тут Ar і Ap – амплітуди реального та передбаченого відліків, d – допуск (допустима похибка подання амплітуд). Ілюстрація передбачуваного методу з лінійною екстраполяцією представлена на рис. 3.3. Тут точками показані передбачувані значення сигналу. Якщо точка виходить за межі коридору (допуску d), показаного пунктирними лініями, то відбувається передача відліку. На малюнку передані відліки відзначені темними кружками моменти часу t1, t2, t4, t7. Якщо передачі відліку немає, то наприймальному кінці приймається екстраполіроване значення.
Мал. 3.3. Передиктивне кодування
Методи MPEG (Moving Pictures Experts Group) використовують передбачуване кодування зображень(для стиснення даних про об'єкти, що рухаються разом зі звуком).Так, якщо передавати тільки змінилися в часі пікселі зображення, то досягається стиснення в кілька десятків разів. Цей алгоритм стиснення використовується у стандарті Н.261 ITU. Методи MPEG стають світовими стандартами цифрового телебачення.
Для стиснення даних про зображення можна використовувати також методи типу JPEG (Joint Photographic Expert Group), що ґрунтуються на втраті малоістотної інформації (не помітні для ока відтінки кодуються однаково, коди можуть стати коротшими). У цих методах послідовність пікселів, що передається, ділиться на блоки, в кожному блоці проводиться перетворення Фур'є, усуваються високі частоти, передаються коефіцієнти розкладання для частот, що залишилися, по них у приймачі зображення відновлюється.
Інший принцип втілений у фрактальному кодуванні, у якому зображення, представлене сукупністю ліній, описується рівняннями цих линий.
Більш універсальним є широко відомий метод Хаффмена, що відноситься до статистичних методів стиснення. Ідея методу - символи, що часто повторюються, потрібно кодувати більш короткими ланцюжками бітів, ніж ланцюжки рідкісних символів. Будується двійкове дерево, листя відповідають символам, що кодуються, код символу представляється послідовністю значень ребер (ці значення в двійковому дереві суть 1 і 0), що ведуть від кореня до листа. Листя символів з високою ймовірністю появи знаходиться ближче до кореня ніж листя малоймовірних символів.
Розпізнавання коду, стисненого методом Хаффмена,виконується за алгоритмом, аналогічним алгоритмам висхідного граматичного аналізу. Наприклад, нехай набір із восьми символів (A, B, C, D, E, F, G, H) має такі правила кодування:
A ::= 10; B ::= 01; C ::= 111; D ::= 110;
E ::= 0001; F ::= 0000; G ::= 0011; H ::= 0010.
Тоді при розпізнаванні вхідного потоку 101100000110 у стек розпізнавача заноситься 1, але 1 не збігається з правою частиною жодного з правил. Тому в стек додається наступний символ 0. Отримана комбінація 10 розпізнається і замінюється А. У стек надходить наступний символ 1, потім 1, потім 0. Поєднання 110 збігається з правою частиною правила для D. Тепер в стеку AD, заносяться наступні символи 0000 і і т.д.
Недолік методу полягає у необхідності знати ймовірність символів. Якщо заздалегідь вони не відомі, то потрібні два проходи: на одному в передавачі підраховуються ймовірності, на іншому ці ймовірності та стислий потік символів передаються до приймача. Однак двопрохідність не завжди можлива.
Цей недолік усувається в однопрохідних алгоритмах адаптивного стиснення, в яких схема кодування є схема пристосування до поточних особливостей потоку символів. Оскільки схема кодування відома як кодеру, і декодеру, стиснене повідомлення буде відновлено на приймальному кінці.
Узагальненням цього є алгоритм, заснований насловнику стиснення даних. У ньому відбувається виділення і запам'ятовування в словнику ланцюжків символів, що повторюються, які кодуються ланцюжками меншої довжини.
Цікавийалгоритм "стіпка книг", у якому код символу дорівнює його порядковому номеру у списку. Поява символу в потоці, що кодується, викликає його переміщення на початок списку. Очевидно, що символи, що часто зустрічаються, будутьтяжіти до малих номерів, а вони кодуються коротшими ланцюжками 1 і 0.
Крім згаданих алгоритмів стиснення існує низка інших алгоритмів, наприклад LZ-алгоритми (алгоритми Лемпеля-Зіва). Зокрема, один із них (LZW) застосований у протоколі V.42bis.
Якщо Ви не знайшли, що шукали, то рекомендую скористатися пошуком по сайту: