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

Ці методи стиснення нас цікавлять в першу чергу, оскільки саме їх застосовують при передачі текстових документів і програм, при видачі виконаної роботи замовнику або при створенні резервних копій інформації, що зберігається на комп'ютері.

Методи стиснення цього класу не можуть припустити втрату інформації, тому вони засновані тільки на усуненні її надмірності.

Ось простий приклад. В російській мові 33 букви, десять цифр і ще приблизно півтора десятка розділових і інших спеціальних символьних знаків. Для тексту, який записаний тільки прописними російськими буквами (як в телеграмах і радіограмах) цілком вистачило б шістдесяти різних значень. Символ звичайно кодується байтом, який містить 8 бітів і може виражати 256 різних кодів. Ця перша підстава для надмірності. Для нашого телеграфного тексту цілком вистачило б шести бітів на символ.

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

Наявність фрагментів, що повторюються, — третя підстава для надмірності. В текстах це зустрічається рідко, але в таблицях і в графіці повторення кодів — звичайне явище. Так, наприклад, якщо число 0 повторюється двадцять разів підряд, то немає значення повторювати двадцять нульових байтів. Замість них ставлять один нуль та коефіцієнт 20. Такі алгоритми, які засновані на виявленні повторів, називають методами RLЕ (Run Length Encoding)

При створенні резервних копій на жорстких дисках є ще одна можливість отримання виграшу в робочому просторі при стисненні файлів, яка, правда, пов'язала не з надмірністю інформації, а з тим, як організована файлова система комп'ютера. Суть полягає в тому, що будь-який файл, великий або маленький, може займати на диску тільки ціле число кластерів. У файловій системі FАТI6 на жорсткому диску не може бути більше 65536 кластерів (216). А це значить, що для дисків розміром від 1 до 2 Гбайт розмір кластера складає цілих 32 Кбайт. Таким чином, в середньому на кожному файлі ми втрачаємо половину цієї величини, а на малих файлах ще більше.

При ущільненні великої групи файлів в один файл ми економимо мінімум по 16 Кбайт на кожному файлі тільки за рахунок скорочення втрат від нераціональної організації файлової системи. Уявіть, що для файлу, що має розмір 1 Кбайт, ми економимо 31 Кбайт, навіть якщо він абсолютно нестискуваний!

Комп'ютери, що працюють під управлінням WINDOWS, використовують новий формат файлової системи — FАТЗ2 а WINDOWS ХР - NTFS. Тут виграш виявляється менше в зв’язку з меншим розміром кластерів, але і в цьому випадку економія дискового простору є, наприклад, для FАТЗ2 мінімальний розмір кластера складає 4 Кбайт, так що якщо ми маємо справу з великою кількістю малих файлів, то тут теж є що економити.

Дата добавления: 2014-01-06