Новини
Користувач
Пароль
Реєстрація
Зворотній зв’язок
Інструкція
Для учнів
Для вчителів
.
Як ви використовуєте Інтернет у навчанні?
шукаю потрібну інформацію
користуюсь перекладачем
спілкуюсь на форумах
проходжу онлайн-тестування
Способи стиснення
Стиснення буває без втрат (lossless compression) і з втратами (lossy compression). Не важко здогадатися, що в першому випадку відновлення файлу з архіву відбувається без зміни якості початкового файлу, у другому - з невеликими втратами якості. Стиснення без втрат або «повністю минаюче стиск» базується на методі розділення вихідного файлу на невеликі частини і відновлення цих частин у вихідний файл при розпакуванні архіву. У випадку «lossy compression» відбувається втрата частини інформації, а та частина інформації, яку потрібно зберегти, виділяється з допомогою певного алгоритму.
Найбільш простим видом стиснення без втрат є метод під назвою «running» - підраховується кількість послідовних, «що йдуть один за одним» повторів. Але цей метод є недостатнім у випадку наявності повторів, що зустрічаються в різних місцях тексту.
Процес роботи архіваторів не варто плутати з поняттям архівації даних, що стосується спеціальних кодеків стиснення зображення, музики та відео. Ми будемо розглядати тільки програми для створення архівів. Для стискування музичних файлів та зображень метод, на якому заснована робота програм-архіваторів, не підходить. Для стиснення, наприклад, зображення використовується зовсім інший алгоритм: у стислому фото відбувається вирівнювання кольору, задається один тон для різних відтінків окремих пікселів.
Параметри стиснення
Процес стиснення даних характеризується рядом важливих параметрів: наприклад, ступенем стиснення файлу і коефіцієнтом стиснення - два важливих показники, від яких у першу чергу залежить якість архівного файлу. Ступінь стиснення файлу залежить від наступних параметрів: застосовуваного методу стиснення, самої програми-архіватора і типу стискування файлу. Найкраще «стискуються» текстові файли та графічні файли у форматі bmp, png. Файли з розширенням. exe, dll, а також архівні файли практично не стискуються.
Також для роботи архіватора чимале значення має параметр швидкості стиснення та розпаковування файлу. Коротко механізм стиснення можна описати наступним чином: певна кількість цифрової інформації або мовою фахівців «блок» стискується, в результаті виходить «стиснений блок», який містить меншу кількість бітів, але по якому можна відновити всі біти початкового файлу.
Методи стиснення.
Методи стиснення файлів бувають «відкритими» і «комерційними». У першому випадку алгоритм можна вільно досліджувати та використовувати, так як він сам по собі є цінністю. У другому випадку використання методу є закритим: алгоритм засекречується, тому, що він застосовується тільки в окремих програмних продуктах, і несанкціоноване використання може викликати подальші розгляди з приводу авторських прав, що власне неодноразово відбувалося в історії розвитку архіваторів.
Розроблено велику кількість методів стиснення, найбільш відомі: методи Зеева - Лемпела або «LZ-методи» (LZ77, LZ78, LZH, LZW), метод Хаффмана або «HUFF» ( «Huffman Coding»), перетворення Барроуза-Уіллера ( «BWT» ), метод перетворення Фур'є «FT» ( «Fourier Transform») та інші. Стиснення, наприклад, по «LZ-методу» засноване на створенні своєрідного словника, де кожне слово отримує свій порядковий номер, і в результаті стиснений файл містить послідовність чисел, що істотно скорочує його розмір.
Кодування за методом Хаффман описується трохи складніше: воно відбувається завдяки створенню певної таблиці даних і додавання до неї нових комірок, в результаті чого виходить систематизація даних у вигляді дерева ( «двійкове дерево»). За допомогою цього дерева відбувається обчислення коду і власне саме кодування.
При стисненні за методом Барроуза і Уіллера упаковка відбувається в два етапи: на початку здійснюється певний перетворення даних, а потім - сам процес стиснення. На першому етапі відбувається сортування даних, яка отримала назву «перетворення Барроуза-Уіллера»: у блоці даних різні символи міняються місцями таким чином, щоб забезпечити більш дієве стиск на другому етапі.
Необхідно особливо виділити метод PPM ( «Prediction by Partial Match»), за яким працює програма WinRAR і багато архіватори російських розробників: архіватори PPMD і PPMonstr (автор Дмитро Шкарін), PPMN (автор Максим Смирнов), PPMY (архіватор Євгена Шелвіна). Також варто відзначити метод арифметичного кодування ARC, що став попередником формату архіватора WinZip. Арифметичне кодування є створенням з стискає файлу нумерації окремих його блоків: в послідовності бітів файлу виділяються біти з однаковими частотами для подальшої нумерації. Арифметичне кодування стало основою багатьох методів стиснення, включаючи метод Хаффман.
Що стосується передісторії програми WinZIP, спочатку були розроблені алгоритми стиснення за так званим методам редукування ( «reducing») і скорочення ( «shrinking»), які сьогодні вже практично не підтримуються. Пізніше в програму WinZIP було впроваджено метод, що поєднує LZ-метод (LZ77) і метод Хаффман, і в результаті цього вдалого поєднання був розроблений новий формат стиснення, що став широко поширеним.
Повернутись