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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

А дійсно, навіщо? Порахуємо, наприклад, скільки займе пам'яті зображення, за якістю близьке до телевізійного. Нехай його роздільна здатність - 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 рядків.

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

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

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

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

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

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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Доповідь
9.9кб. | скачати


Схожі роботи:
Алгоритм стиснення історичної інформації
Ентропія складних повідомлень надмірність джерела Мета стиснення даних і типи систем стиснення
Синдром тривалого стиснення
Алгоритми стиснення даних
Алгоритми стиснення даних 2
Система стиснення і ущільнення каналів
Стиснення даних при передачі зображень
Система стиснення і ущільнення каналів Розробка системи
Властивості інформації Одиниці виміру кількості інформації
© Усі права захищені
написати до нас