На даний момент розроблено безліч способів стиснення даних, кожен з яких має свої переваги і недоліки. Метод, який називається кодуванням довжини серії (run-length encoding), дає найкращий ефект при стисненні даних, що складаються з довгих послідовностей однакових елементів. Дійсно, при кодуванні довжини серії така послідовність замінюється кодом, що позначає повторюваний елемент, і числом його повторень. Наприклад, для того щоб позначити, що набір бітів складається з 253 одиниць, за якими слідують 118 нулів і 87 одиниць, буде потрібно менше місця, ніж для перерахування всіх 458 бітів.
У деяких випадках інформація складається з блоків даних, які незначно відрізняються один від одного. Наприклад, кадри фільму, наступні один за одним. У таких випадках використовується метод відносного кодування (relative encoding). При такому підході записуються відмінності між блоками, наступними один за одним, а не самі блоки, тобто кожен блок кодується на основі його відносин з попереднім блоком.
Іншим методом скорочення розміру даних є частотно-залежне кодування (frequency-dependent encoding), в якому довжина коду елемента інформації обернено пропорційна частоті використання цього елемента. Ці коди є прикладами кодів змінної довжини (variable-length codes), що означає, що елементи інформації представлені послідовностями різної довжини, на відміну від таких кодів, як Unicode, в якому всі символи представлені 16-бітовими послідовностями. В англійській мові букви е, t, a і i використовуються частіше, ніж літери z, q і х. Тому при кодуванні тексту англійською мовою можна зберегти місце в пам'яті, якщо використовувати короткі набори бітів для перших букв і довші для других. В результаті ми отримаємо код, в якому текст буде мати більш коротке представлення, ніж мав би в коді з фіксованою довжиною, такому як ASCII або Unicode. Давид Хаффман відомий як відкривач алгоритму, який широко використовується для створення частотно-залежних кодів. Тому майже всі частотно-залежні коди, що використовуються сьогодні, - це коди Хаффмана (Huffman codes).
Хоча ми і назвали кодування довжини серії, відносне кодування і частотно-залежне кодування загальними методами кодування даних, кожне з них все-таки має свою область застосування. На відміну від них система стиснення Лемпеля-Зива (Lempel-Ziv encoding), названа на честь її творців Абрахама Лемпеля і Якоба Зива, є більш універсальною системою. Насправді користувачі Мережі (див главу 3), можливо, бачили або використовували обслуговує програмне забезпечення, в якому для створення стислих файлах, що називаються zip-файлами, застосовується метод Лемпеля-Зива. Система кодування Лемпеля-Зива є прикладом кодування з адаптивним словником (adaptive dictionary encoding). Словником в цій системі є набір стандартних блоків, з яких побудовано повідомлення, яке потрібно стиснути. Якби ми хотіли стиснути текст англійською мовою, то такими стандартними блоками були б букви алфавіту. Якби ми хотіли стиснути вже закодовані дані, то стандартними блоками були б цифри 0 і 1. При адаптивному кодування словник може змінюватися в процесі кодування. Наприклад, у випадку з англійським текстом, закодований частина повідомлення, ми можемо вирішити додати в словник ing і the. Тепер кожен раз, коли в тексті зустрінеться ing або the, вони можуть бути закодовані за допомогою звернення до словника один раз, а не три. Метод Лемпеля-Зива дозволяє розумно і ефективно адаптувати словник в процесі кодування (або стиснення) даних.
Як ми вже говорили в розділі 1.4, одна секунда музичного звучання, оцифрована з частотою дискретизації 44 100 відліків в секунду, вимагає більш одного мільйона бітів в пам'яті. Такі вимоги допустимі для музичних записів, які розповсюджуються на компакт-дисках, але спроба поєднати звук і зображення при записі фільмів кидає виклик можливостям технологій. Тому Експертною групою по рухомих зображень (The Motion Picture Experts Group), що входить в організацію ISO, був розроблений метод стиснення даних, який значно скорочує вимоги до пам'яті. Один з цих стандартів називається МРЗ (MPEG-1 Audio Layer-3) і дозволяє досягти коефіцієнта стиснення від 12 до 1. При використанні стандарту МРЗ розмір музичних записів може бути зведений до розміру, який може економно передаватися по Мережі. Ця можливість загрожує докорінно змінити індустрію звукозапису.
Розглянемо як приклад, як ми можемо стиснути повідомлення, використовуючи окремий випадок алгоритму Лемпеля-Зива, який називається LZ77. Почнемо з простого цитування початкової частини повідомлення. Потім представимо решту повідомлення у вигляді послідовності трійок (містять два цілих числа, за яким слідує символ з повідомлення). Кожна така трійка описує, як повинна будуватися наступна частина повідомлення на підставі попередньої. Отже, словник, з якого будується повідомлення, складається з самого повідомлення.
Наприклад, розглянемо стислий повідомлення xyxxyzy (5. 4, х), що складається з початкового сегмента xyxxyzy, за яким слід трійка (5. 4, х). Ланцюжок xyxxyzy є частиною повідомлення, яка вже знаходиться в розгорнутій формі. Для того щоб розгорнути решту повідомлення, ми повинні розшифрувати трійку (5. 4, х), як показано на рис. 1.27. Перше число трійки показує, на скільки символів потрібно повернутися назад в розгорнутій ланцюжку. У нашому випадку ми повертаємося на п'ять символів назад до другого зліва х. Тепер починаємо додавати в кінець розгорнутої ланцюжка символи, що знаходяться в цій позиції. Друге число показує, скільки символів з послідовності потрібно додавати. У нашому випадку це число 4, тому ми дописуємо символи xxyz в кінець розгорнутої ланцюжка і отримуємо xyxxyzyxxyz. Нарешті, додаємо в кінець ланцюжка останній символ трійки. У нашому прикладі цей символ х, приписуємо його в кінець розшифрованої ланцюжка. У підсумку отримуємо розгорнуте повідомлення xyxxyzyxxyzx.
Тепер припустимо, що нам потрібно розгорнути повідомлення xyxxyzy (5. 4, х) (О, 0, w) (8. б. У). Почнемо, як і раніше, з розшифровки першої трійки, отримуємо xyxxyzyxxyzx (0, 0, w) (8. 6, у). Тепер в результаті розгортання другої трійки отримуємо ланцюжок xyxxyzyxxyzxw (8, 6, у). Зверніть увагу, що трійка (0, 0. w) використовувалася тому, що символ w ще не зустрічався в повідомленні. Нарешті, розшифровуємо останню трійку і отримуємо розгорнуте повідомлення xyxxyzyxxyzxwzyxxyzy.
Для того щоб стиснути повідомлення за допомогою алгоритму LZ77, спочатку переписуємо початковий сегмент повідомлення, потім шукаємо в цьому сегменті найдовшу ланцюжок, яка збігається з частиною повідомлення. До цієї ланцюжку буде ставитися перша трійка. Наступні трійки формуються таким же чином.
Нарешті, ви, мабуть, помітили, що всі ці приклади не відображають повною мірою процес стиснення даних, оскільки розглядаються трійки представляють тільки короткі сегменти повідомлення. Однак справедливо вважати, що в довгих довічних кодах трійки представлятимуть довгі сегменти, в результаті чого стиснення даних буде значним.
У розділі 1.4 згадувалося, що в растровій графіці, яка проводиться сучасними цифровими перетворювачами, зображення, як правило, видається в форматі три байта на один піксель, що призводить до великих і важко оброблюваних файлів растрової графіки. Для того щоб зменшити вимоги до пам'яті, було розроблено багато схем стиснення. Одна з них, розроблена компанією CompuServe, називається GIF (скорочено від Graphic Interchange Format - формат графічного обміну). Цей стандарт стиснення вирішує проблему шляхом скорочення кількості квітів, які можуть бути приписані пікселу, до 256. Це означає, що значення кожного пікселя можна уявити за допомогою одного байта, а не трьох. Кожному з 256 значень пікселя за допомогою таблиці, яка називається палітрою, ставиться у відповідність певне поєднання червоного, зеленого і синього кольорів. Змінюючи палітру зображення, ми можемо змінювати кольори зображення.
Одному з кольорів зображення в форматі GIF зазвичай присвоюється значення «прозорий», тобто через будь-яку ділянку зображення, якому присвоєно цей колір, видно фон. Внаслідок цієї можливості і відносну простоту формату GIF, він використовується в комп'ютерних іграх, де численні зображення рухаються по екрану.
Інший стандарт стиснення зображень називається JPEG. Він був розроблений Joint Photographic Experts Group (Об'єднана група експертів в області фотографії), що входить до складу організації ISO. JPEG виявився ефективним для представлення кольорових фотографій. Насправді, саме цей стандарт прийнятий виробниками сучасних цифрових камер, і він обіцяє ще довгий час мати вплив в сфері цифрових зображень.
Насправді стандарт JPEG включає в себе кілька способів представлення зображень, у кожного з яких своя задача. Наприклад, в ситуаціях, коли потрібна гранична точність, формат JPEG надає метод «без втрат», при якому не відбувається втрати інформації під час кодування зображення. Відповідно до цього алгоритмом зберігається відмінність між сусідніми пікселями, а не інтенсивності пікселів. Такий підхід ґрунтується на припущенні, що в більшості випадків відмінність між сусідніми пікселями можна уявити більш коротким двійковим кодом, ніж їх значення (це приклад відносного кодування). Відмінності записуються за допомогою коду змінної довжини.
На жаль, застосування цього методу не дає зображень, розмір яких можна легко змінювати, і тому використовується рідко. Замість нього використовується базисний стандарт JPEG, який скорочує розмір коду зображення, використовуючи для визначення стану пікселів два параметри: яскравість і колір.
Причина такого поділу полягає в тому, що людське око більш чутливий до змін яскравості, ніж до змін кольору. Розглянемо, наприклад, два синіх фону, що розрізняються лише тим, що один з них містить невелику яскраву крапку, а другий невелику зелену точку, яскравість якої така ж, як і яскравість фону. Людське око швидше виявить яскраву крапку, ніж зелену. Базисний формат використовує це властивість людського ока і кодує кожну компоненту яскравості, але при цьому зображення розділяється на блоки розміром чотири пікселя, і записується тільки середній колір кожного блоку. Отже, в остаточному поданні зберігаються всі швидкі зміни яскравості, але при цьому стираються швидкі зміни кольору. Перевага ж цього методу полягає в тому, що кожен блок з чотирьох пікселів задається тільки шістьма значеннями (4 для яскравості і 2 для кольору), а не дванадцятьма, як якщо один піксель задається трьома значеннями.
Більше простору економиться час запису змін яскравості і кольору, а не їх фактичних значень. Причина цього, як і в методі «без втрат», полягає в тому, що під час сканування зображення ступінь відмінності сусідніх пікселів можна уявити більш коротким двійковим кодом, ніж той, який був потрібен для запису фактичних значень кольору. Насправді, ці відмінності записуються за допомогою математичного методу, який називається дискретного косинусного перетворення. Ми не будемо розглядати його в цій книзі. Остаточний двійкового коду потім стискається за допомогою методу з кодом змінної довжини.
Коротше кажучи, за допомогою базисного стандарту JPEG можна кодувати високоякісні кольорові зображення, використовуючи двійковий код, який займає приблизно в двадцять разів менше пам'яті, ніж код формату «три байта на піксель», який використовується у багатьох сканерах. Тому стандарт JPEG завойовує все більшу популярність. Однак в деяких прикладних системах використовуються інші формати. Наприклад, формат GIF більше, ніж JPEG, підходить для зображень, що складаються з блоків одного кольору з чіткою межею, таких як кольорові мультфільми.