Стиснення інформації

Навіщо потрібно стискати інформацію і які існують способи це зробити.

А дійсно, навіщо? Порахуємо, приміром, скільки займе пам'яті зображення, за якістю близьке до телевізійного. Нехай його роздільна здатність - 800х6009 пікселів, а число відтінків кольору близько 16 тисяч (High Color), тобто колір кожного пікселя представляється багатобайтових кодом. 800x600 = +480000 елементів. 480000x2 байт = 960000 байт - це трохи менше 1 мегабайта. Здається, не так багато - на лазерному диску поміститься більше 650 таких картинок. Ну, а якщо мова йде про фільмі? Стандартна швидкість кінопроекції - 24 кадрів в секунду. Значить на компакт-диск можна записати фрагмент тривалістю 650:24 = 27 секунд. Куди це годиться?! Але ж це далеко не єдиний випадок, коли інформації "занадто багато". Таким чином, одна з причин використання стиснення даних - бажання помістити більше інформації в пам'ять того ж об'єму. Є й друга причина. Стиснення інформації прискорює її передачу. Але про це - у наступному розділі.

Існує декілька методів стиснення (компрессіі10) даних. Усі їх можна розділити на два групи - стиснення без втрат і з втратами. У першому випадку розпаковані повідомлення точно повторює оригінал. Звісно, так можна обробляти будь-яку інформацію. Стиснення ж з втратами можливо лише в тих випадках, коли допустимі деякі спотворення - які саме, залежить від конкретного типу даних.

Практично всі методи стиснення без втрат засновані на одній з двох досить простих ідей.

Одна з них вперше з'явилася в метод стиснення текстової інформації, запропонованому в 1952 Хафманом. Ви знаєте, що стандартно кожен символ тексту кодується одним байтом. Але справа в тому, що одні букви зустрічаються частіше, а інші рідше. Наприклад, у тексті, написаному російською мовою, в кожній тисячі символів у середньому буде 90 букв "о", 72 - "е" і лише 2 -- "ф". Більше ж за все виявиться пробілів: сто сімдесят і чотири. Якщо для найбільш поширених символів використовувати більш короткі коди (менше 8 біт), а для менш поширених - довгі (більше 8 біт), текст в цілому займе менше пам'яті, ніж при стандартній кодуванні.

Кілька методів стиснення засновані на обліку повторюваних байтів або послідовностей байт. Простий з них - RLE11 - широко використовується при стисненні зображень. У файлі, стислому таким методом, записується, скільки разів повторюються однакові байти. Наприклад, замість "RRRRRGGGBBBBBBRRRBBRRRRRRR" буде зберігатися "5R3G6B3R2B7R" 12. коли зображення містить великі ділянки з однотонним зафарбовування.

Інші методи засновані на тому, що якщо певна послідовність байт зустрічається у файлі багато разів, її можна записати один раз в особливу таблицю, а потім просто вказувати: "взяти стільки-то байт з такого-то місця таблиці "13.

Методи стиснення без втрат зменшують розмір файлів не дуже сильно. Зазвичай коефіцієнт стиснення не перевершує 1/3-1/4. Значно кращих результатів можна домогтися, використовуючи стиснення з втратами. У цьому випадку на основі спеціальних досліджень визначається, якою інформацією можна пожертвувати.

Наприклад, встановлено, що людський зір дуже чутлива до зміни яскравості і набагато менше, до колірного тону. Тому при стисненні фотографічних зображень (і взагалі, зображень, в яких немає різких меж між квітами) можна виключити інформацію про колір частини пікселів. При розпакуванні ж визначати його по сусідніх. На практиці найчастіше застосовується метод, який використовує більше складну обробку, - JPEG14. Він дозволяє стискати зображення в десятки разів. З урахуванням особливостей сприйняття людиною інформації будуються також методи стиснення з втратами відеозображення (найбільш поширені зараз методи MPEG15) і звуку.

Природно, стиснення з втратами може використовуватися тільки програмами, призначеними для обробки конкретних видів даних (наприклад, графічними редакторами). А ось методи стиснення без втрат застосовуються і для будь-яких довільних файлів (широко відомі програми-компресори ARJ, ZIP, RAR, StuffIt та ін).

Зауважимо, що не варто намагатися стиснути файли, які вже були стиснуті: розмір їх або зменшиться зовсім незначно, або навіть збільшиться.

Примітки

На Насправді, в телевізійному зображенні 625 рядків.

Compressus (лат.) - стискання.

Run-Length Encoding (англ.) - кодування довжини послідовності.

На Насправді, звичайно, використовуються коди квітів і коди, що вказують або скільки раз повторюється наступний байт, або скільки наступних байтів -- неповторним.

На цієї ідеї заснований що широко використовується для стиснення різних даних метод LZW, названий так за першими буквами прізвищ його розробників: Lempel, Ziv і Welch.

Joint Photographic Experts Group (англ.) - Об'єднана група експертів з фотографії, що розробила однойменний метод стиснення зображень.

Moving Picture Experts Group (англ.) - Група експертів по рухомих зображень

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://macedu.narod.ru