Стиснення даних
Система двійкового кодування, що використовується в комп’ютерах, дуже зручна для зберігання, передавання й опрацювання даних з точки зору надійності цих процесів. Однак двійкове кодування збільшує розміри файлів порівняно з іншими системами кодування. Тому виникає потреба у зменшенні розмірів файлів для ефективнішої реалізації інформаційних процесів.
Для зменшення розміру файлів використовують спеціальні способи стиснення даних, які називають алгоритмами (методами) стиснення даних. Стиснення даних використовується при створенні файлів певних типів, наприклад графічних типу JPEG або звукових типу MPEG3, для передачі файлів мережею тощо.
Розрізняють алгоритми стиснення, що забезпечують стиснення без втрати даних, і алгоритми, що передбачають часткову втрату даних.
Алгоритми з частковою втратою даних використовують, коли цілісність даних не є дуже суттєвою. Наприклад, при стисненні графічних, відео, звукових файлів, оскільки органи чуттів людини не здатні помітити незначну різницю у відтінках кольорів на фотографії, незначну різницю у відтворенні звукових або відеоданих тощо.
Розглянемо кілька методів стиснення без втрати даних.
Кодування Лемпеля/Зіва. Даний метод базується на алгоритмі кодування послідовності об’єктів (цифр, літер тощо), в якій є фрагменти, що повторюються. Пояснимо цей алгоритм на такому прикладі. Нехай маємо послідовність цифр: 122222444355555222222. Замінимо її на іншу послідовність, в якій указуватимемо, яка цифра повторюється підряд і скільки разів. У результаті кодування отримуємо таку послідовність: 112543315526. У першій послідовності 21 цифра, у другій значно менше – 12. Тобто відбулося стиснення даних приблизно на 43%. Цей алгоритм дуже дієвий для стиснення графічних зображень з великими ділянками однакового кольору. Однак при відсутності повторювань він призведе до збільшення розміру файлу. Наприклад, послідовність 247435995622 за
даним методом перетвориться у послідовність 21417141315192516122.
Кодування Хаффмана/Шенона. Цей метод часто застосовується при стисненні текстових даних. Він враховує частоту вживання в конкретній мові певних літер. Наприклад, в українській мові найбільш вживаними є літери і, а, о, е, а літери ш, щ, ф, х використовуються набагато рідше. У таких випадках використовують не 8 бітну систему кодування, а систему кодування змінної довжини, в якій найбільш вживані символи кодуються 1-4 бітами, а ті, що зустрічаються рідше, – 7-8 бітами. Одним з прикладів такого кодування є кодування з використанням азбуки Морзе. У ній символи кодуються послідовністю крапок і тире. Наприклад, літера а української
абетки позначається як крапка і тире, літера м – двома тире, літера т – одним тире, а літера и – двома крапками, літера ш – чотирма тире, літера ц – крапкою, тире, крапкою і тире. Якщо замінити крапку на нуль, а тире на одиницю, то слово мати буде закодоване такою послідовністю 11 01 1 00. При існуючому ж кодуванні текстових повідомлень у комп’ютерних системах на кодування кожної літери відводиться мінімум 8 біт і слово із 4 літер буде закодовано послідовністю з 32 нулів і одиниць.