Алгоритми стиснення даних без втрат. Принципи стиснення інформації Типи стиснення графіки, відео та аудіо

У мережі сьогодні популярні десятки архіваторів, причому, в опис у кожної програми можна зустріти що її алгоритм най-най… Вирішив взяти кілька популярних у мережі архіваторів, а саме: WinRar, WinUha, WinZip, KGB archiver, 7Z і перевірити їх у «бойових» » умов.

Невелика передмова…Порівняння, можливо, буде не надто об'єктивне. Порівняння ахіваторів проводилося на звичайному домашньому комп'ютері, середньому за показниками на сьогоднішній день. До того ж не бралися різні типи даних: порівняння стиснення проводилося на звичайному «вордівському» документі, яких у багатьох хто навчається або працює з ними - зможе накопичитися безліч. Ну і логічно, що інформацію, яку рідко використовуєш, - доцільно запакувати в архів і іноді витягувати. Та й передавати такий файл набагато легше: і на флешку швидше скопіюється, ніж купа дрібних файлів, та й по інтернету швидше скачається.

Таблиця порівняння стиснення

Для невеликого експерименту було взято порівняно великий файл RTF - близько 3,5 мегабайт і стиснутий різними архіваторами. Час роботи поки не беремо, про особливості роботи програм буде розказано далі, зараз тільки подивимося ступінь стиснення.

Програма	Формат	Ступінь стиснення	Розмір, к.байт	Скільки разів зменшився розмір файлу ?
KGB Archiver 2	.kgb	максимум	141411	22,99
WinRar	.rar	максимум	190546	17,07
WinUha	.uha	максимум	214294	15,17
7Z	.7z	максимум	218511	14,88
WinZip	.zip	максимум	299108	10,87
Вихідний файл	.rtf	Без стиску	3252107	1

Як видно з невеликої таблички, що найвищий ступінь стиснення досягається у програми KGB Archiver 2 - у 23 рази зменшився вихідний розмір файлу! Тобто. якщо у вас на жорсткому диску кілька гігабайт різної документації, якою ви не користуєтеся і хочете видалити (але не залишає почуття, а раптом знадобиться) - чи не простіше стиснути такою програмою і записати на диск.

Але про всі «підводні камені» по порядку…

KGB Archiver 2

Загалом щось хороший архіватор, за заявами розробників їх алгоритм стиснення один із «найсильніших». Важко не погодитися.

Тільки ось швидкість стиснення залишає бажати кращого. Наприклад, файл у прикладі (близько 3 мб) програма стискала близько 3 хв! Неважко прикинути, що один CD диск вона стискатиме пів дня, якщо не більше.

Але особливе здивування викликає не це. Розпакування файлу триває за часом стільки ж, скільки компресія! Тобто. якщо ви витратили пів дня на те, щоб стиснути частину своїх документів, то стільки часу ви витратите, щоб дістати їх з архіву.

Підсумок:програму можна використовувати для невеликих обсягів інформації, особливо коли важливий мінімальний розмір вихідного файлу (наприклад, файл потрібно розмістити на дискеті, або на невеликий за місткістю флешці). Але знову ж таки, заздалегідь вгадати розмір стисненого файлу не можна, і можливо, час на стиск ви витратите марно…

WinRar

Знаменита програма на пострадянському просторі встановлена ​​на більшості комп'ютерів. Напевно, якби вона не показувала таких добрих результатів, вона б і не мала стільки шанувальників. Нижче скріншот на якому показано налаштування стиснення, нічого особливого, хіба що ступінь стиснення була поставлена ​​на максимум.

На подив WinRar стиснув файл за кілька секунд, причому розмір файлу зменшився у 17 разів. дуже гідний результат, якщо ще врахувати, що час витрачений на обробку мізерно мало. А час на розпакування файлу – ще менше!

Підсумок:чудова програма, що показує одні з найкращих результатів. У процесі налаштувань стиснення можна вказати максимальний розмір архіву і програма його розіб'є на кілька частин. Це дуже зручно, щоб перенести файл з одного комп'ютера на інший на флешці або CD/DVD диску, коли весь файл не запишеш…

WinUha

Порівняно молодий архіватор. Назвати його надпопулярним не можна, але інтерес у багатьох користувачів до нього хтось часто працює з архівами - є. І не випадково, адже за заявами розробників архіватора, його алгоритм стиснення сильніший, ніж у RAR та 7Z.

У нашому невеликому експерименті я би не сказав, що це так. Можливо, що на деяких інших даних він і покаже найкращі результати.

До речі, при установці вибирайте англійську мову, російською – програма видає «крякозабри».

Підсумок:непогана програма з цікавим алгоритмом стискування. Час на обробку та створення архіву, звичайно, більший ніж у WinRar, але на деяких типах даних можна отримати трохи більший ступінь стиснення. Хоча, особисто я не став би робити на цьому великий акцент…

7Z

Дуже популярний безкоштовний архіватор. Багато хто стверджує, що ступінь стиснення в 7z реалізований навіть краще ніж у WinRar. Цілком можливо, але при стисканні з рівнем "Ультра" на більшості файлів він програє WinRar'у.

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

WinZip

Легендарний, один із найпопулярніших колись архіваторів. У мережі, напевно, найчастіше зустрічаються архіви - це «ZIP». І не випадково – адже незважаючи на не найвищий ступінь стиснення, швидкість роботи – просто вражає. Наприклад, Windows відкриває такі архіви, як звичайні папки!

До того ж не слід забувати, що цей архіватор і формат стиснення набагато старший за новомодних конкурентів. Та й далеко не всі зараз мають потужні комп'ютери, які дозволять швидко працювати з новими форматами. А формат Zip підтримують усі сучасні архіватори!

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

Що мається на увазі під ступенем стиснення файлу?

Почнемо із теоретичних питань. Що таке ступінь стиснення файлу? З найпростіших трактувань цього терміна, під ним мається на увазі співвідношення розміру кінцевого (стисненого) об'єкта до початкового обсягу. Однак таке пояснення більшою мірою може стосуватися виключно архівних даних, оскільки зовсім не торкається деяких питань, пов'язаних зі зміною формату мультимедіа, де стиснення також дуже поширене. Загалом, говорити про те, що ступінь стиснення файлу залежить тільки від якоїсь однієї ознаки, не можна. У разі роль грає і тип об'єкта, і використовувані для стиснення даних програми, і швидкість проведення процесу стискування. Далі стисло зупинимося на деяких важливих аспектах, які можуть вплинути на кінцевий результат зменшення розміру вихідних даних.

Ступінь стиснення файлу залежить тільки від типу файлу: чи це так насправді?

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

При спробі упаковки таких даних до архіву істотного зменшення розміру досягти практично неможливо. Те саме стосується формату WAV. Однак, якщо зробити не стиснення, а перекодування з WAV в MP3, розмір можна зменшити разів на десять і більше. Багато користувачів тут же відштовхуються від того, що ступінь стиснення файлу залежить саме від початкового і кінцевого формату. Це не зовсім так, оскільки важливу роль відіграє і алгоритм перекодування, що застосовується, про що буде сказано окремо. А поки що зупинимося на використанні архіваторів.

Від чого залежить ступінь стиснення файлу під час упаковки в архів?

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

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

Якщо ж стосовно архіваторів розглядати файлові формати, з найстисніших можна виділити текстові документи будь-яких форматів.

Відносно непогано стискаються деякі файли EXE-формату, що виконуються (при стандартному методі стиснення можна домогтися зменшення розміру більше, ніж наполовину). Найбільш, як говорилося, несжимаемыми є об'єкти мультимедіа. І, якщо картинки зменшити за розміром хоч якось можна, з аудіо та відео без зміни початкового формату такі дії не відбуваються, і архіватори тут зовсім ні до чого.

Типи стиснення графіки, відео та аудіо

Стосовно мультимедіа розрізняють два основних типи стиснення: із втратою якості (lossy) і без втрат (lossless). І в даному випадку ступінь стиснення файлу залежить саме від технології компресії, що використовується.

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

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

Найпоширеніші програми на всі випадки життя

Від чого залежить ступінь стиснення файлу, дещо розібралися. Тепер слід сказати кілька слів про застосовані програмні продукти. Серед архіваторів найпоширенішими можна назвати WinRAR, WinZIP та 7-Zip.

Що ж до стиснення мультимедіа, у найпростішому випадку можна використовувати спеціальні програми-конвертери, які працюють за принципом перекодування вихідного матеріалу в інший формат з метою зменшення розміру файлу.

Короткі підсумки

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

АРХІВАТОРИ

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

Архівний файл– це спеціально створений файл, що містить у собі один або кілька файлів у стислому вигляді.

Ступінь стиснення: K c =V c /V o *100%

K c- Коефіцієнт стиснення, V c- Обсяг стисненого файлу, V o- Вихідний обсяг файлу.

Ступінь стиснення залежить від:

1) використовуваної програми – архіватора,

2) методу стиснення,

3) тип вихідного файлу: текстового, графічного, відео, звукового і т.д.

Програми, які здійснюють упаковку та розпакування файлів називаються архіваторами. Найбільш поширеними є: ARJ, ZIP, RAR. Розширення архівних файлів збігається з назвою використаного для створення архіватора.

Архіватори дозволяють створювати архівні файли, що саморозпаковуються, тобто. їх розпакування не потрібно запуску програми-архіватора, т.к. вони самі містять програму розпакування. Ці архіви називаються SFX-архіви
(SelF-eXtracting). Розширення файлів *.EXE.

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

У будь-якому тексті зустрічаються символи, що повторюються. Можна вказати один символ та кількість повторень. Ще вища ефективність цього алгоритму стосовно графічних файлів. Якщо поглянути на монітор, то можна бачити дуже багато точок одного кольору, що повторюються. У цьому принципі стискування інформації заснований формат графічних файлів PCX. Сучасні архіватори виділяють, як повторювані символи, а й ланцюжка символів, окремі слова.

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

3. У наступному принципі використовується закономірність, що в тексті літери зустрічаються з різною частотою. Наприклад, у цьому тексті пробіл найпоширеніший символ, дуже часто зустрічаються символи «а», «і». Ці символи, що часто зустрічаються, можна представляти короткою комбінацією бітів, інші символи можна кодувати більш довгою послідовністю. Наприклад:

4. Фізично ПК виділяє місце розміщення файлів на диску по кластерам - блоками по 4 кБ. Менше виділити неможливо. Наприклад, якщо файл має розмір 8193 байти (8 кБ і 1 байт), фізично він займатиме 16 кБ або 16384 байти. Об'єднання групи файлів на один дозволяє заощадити на цих залишках. При пакуванні маленьких файлів це дає велику економію.

Разом, при окремому розміщенні файлів не використовуються 6 кБ, що становить 100% вмісту файлів. У другому випадку невикористовуваними залишається 2 кБ, 33%.

Архіватор zip

Запаковка файлів pkzip [ключи]<имя архива>[шляхи файлів]

Ключі: -rpархівація з підкаталогами із збереженням структури

S PWDзахист архіву паролем (PWD)

A додати файли до архіву

M перемістити файли до архіву

V перегляд вмісту архіву

Якщо проводиться архівація всіх файлів каталогу, обов'язково вказувати маску *.*

Розпакування файлів pkunzip [ключи]<имя архива>[імена файлів]

Ключі: -d розпакування з підкаталогами із збереженням структури

SPWD пароль архіву (PWD)

Архіватор arj

arj<команда>[ключи]<имя архива>[імена файлів]

Для архіватора arj один файл виконує операції та розпакування та запакування.

Команди: aархівація

e розпакування без збереження структури каталогів

xрозпакування із збереженням структури

l перегляд вмісту архіву

m перемістити файли до архіву

d видалити файли з архіву

Ключі: -r упаковка з підкаталогами із збереженням структури

V розбивка архіву на томи з обсягом vol(якщо вказано)

розмір для стандартних дискет (360, 720, 1200, 1440) вказується в кілобайтах, розмір нестандартних дискет вказується в байтах

V вказується при розпакуванні багатотомного архіву

G PWDпароль архіву ( PWD)

Запаковка файлів

Розпакування файлів

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

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

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

Стискатися можуть як одні, так і кілька файлів, які в стислому вигляді поміщаються в так званий архівний файл, чи архів.

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

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

Під ступенем стисненнярозуміють відношення розмірів стисненого файлу та вихідного, виражене у відсотках.

Ступінь стисненнязалежить від програми стиснення, методу стиснення і типу вихідного файлу. Найкраще стискаються файли графічних образів, текстові файли, файли даних, ступінь стиснення яких може досягати 5 - 40%, менше стискаються файли програм і завантажувальних модулів - 60 - 90%. Майже не стискаються архівні файли. Програми для архівації відрізняються використовуваними методами стиснення, що впливає на ступінь стиснення.

Архівація (упаковка) — розміщення (завантаження) вихідних файлів у архівний файл у стислому чи несжатому вигляді.

Розархівація - процес відновлення файлів з архіву точно в такому вигляді, який вони мали до завантаження в архів. Під час розпакування файли виймаються з архіву і поміщаються на диск або оперативну пам'ять.

Програми, що здійснюють упаковку та розпакування файлів, називаються програмами-архіваторами.

Великі за обсягом архівні файли можуть бути розміщені на кількох дисках (томах). Такі архіви називаються багатотомними. Том – це складова частина багатотомного архіву. Створюючи архів із кількох частин, можна записати його частини на кілька носіїв.

Основні види програм-архіваторів

В даний час застосовується кілька десятків програм-архіваторів, які відрізняються переліком функцій і параметрами роботи, проте найкращі мають приблизно однакові характеристики. З-поміж найбільш популярних програм можна виділити: Zip (і його модифікація WinZip), WinRAR, Arj (і його різновиди), G-Zip, 7-Zip.

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

Саморозпаковується архівотримав назву SFX-архів(SelF-eXtracting). Архіви такого типу зазвичай створюються у форматі ЕХЕ-файлу.

Багато програм-архіваторів роблять розпакування файлів, вивантажуючи їх на диск, але є й такі, які призначені для створення упакованого виконуваного модуля (програми). В результаті такої упаковки створюється програмний файл з тим самим ім'ям і розширенням, який при завантаженні в оперативну пам'ять саморозпаковується і відразу запускається. Разом з тим, можливе і зворотне перетворення програмного файлу в розпакований формат. До таких архіваторів належать програми Upx, PKLITE, LZEXE.

Програма EXPAND, що входить до складу утиліт операційної системи Windows, застосовується для розпакування файлів програмних продуктів, які постачаються фірмою Microsoft.

Способи керування програмою-архіватором

Управління програмою-архіватором здійснюється одним із наступних способів:

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

Частина перша – історична.

Вступ

Існуючі алгоритми стиснення даних можна поділити на два великі класи – з втратами і без. Алгоритми із втратами зазвичай застосовуються для стиснення зображень та аудіо. Ці алгоритми дозволяють досягти великих ступенів стиснення завдяки вибірковій втраті якості. Однак, за визначенням, відновити початкові дані із стисненого результату неможливо.
Алгоритми стиснення без втрат застосовуються для зменшення розміру даних, і працюють таким чином, що можливо відновити дані точно такими, якими вони були до стиснення. Вони застосовуються в комунікаціях, архіваторах та деяких алгоритмах стиснення аудіо та графічної інформації. Далі ми розглянемо лише алгоритми стискування без втрат.
Основний принцип алгоритмів стиснення полягає в тому, що у будь-якому файлі, що містить невипадкові дані, інформація частково повторюється. Використовуючи статистичні математичні моделі, можна визначити ймовірність повторення певної комбінації символів. Після цього можна створити коди, що позначають вибрані фрази, і призначити фразам, що найчастіше повторюються, найкоротші коди. Для цього використовуються різні техніки, наприклад: ентропійне кодування, кодування повторів та стиснення за допомогою словника. З їх допомогою 8-бітний символ, або цілий рядок, можуть бути замінені лише кількома бітами, усуваючи таким чином зайву інформацію.

Історія

Ієрархія алгоритмів:

Хоча стиснення даних набуло широкого поширення разом з інтернетом і після винаходу алгоритмів Лемпелем і Зівом (алгоритми LZ), можна навести кілька ранніх прикладів стиснення. Морзе, винаходячи свій код у 1838 році, розумно призначив найчастіше використовуваним буквам в англійській мові, "e" і "t", найкоротші послідовності (точка і тире соотв.). Незабаром після появи мейнфреймів у 1949 році був придуманий алгоритм Шеннона - Фано, який призначав символам у блоці даних коди, ґрунтуючись на ймовірності їх появи у блоці. Імовірність появи символу в блоці була обернено пропорційна довжині коду, що дозволяло стиснути подання даних.
Девід Хаффман був студентом у класі у Роберта Фано і як навчальну роботу вибрав пошук покращеного методу бінарного кодування даних. В результаті йому вдалося покращити алгоритм Шеннона-Фано.
Ранні версії алгоритмів Шеннона-Фано та Хаффмана використовували заздалегідь визначені коди. Пізніше для цього почали використовувати коди, створені динамічно на основі даних, призначених для стиснення. У 1977 році Лемпель і Зів опублікували свій алгоритм LZ77, заснований на використанні словника, що динамічно створюється (його ще називають «ковзним вікном»). У 78 році вони опублікували алгоритм LZ78, який спочатку парсить дані та створює словник, замість того, щоб створювати його динамічно.

Проблеми з правами

Алгоритми LZ77 та LZ78 здобули велику популярність і викликали хвилю покращувачів, з яких до наших днів дожили DEFLATE, LZMA та LZX. Більшість популярних алгоритмів засновані на LZ77, тому що похідний від LZ78 алгоритм LZW був запатентований компанією Unisys у 1984 році, після чого вони почали тролити всіх і кожного, включаючи навіть випадки використання зображень у форматі GIF. У цей час на UNIX використовували варіацію алгоритму LZW під назвою LZC, і через проблеми з правами їх використання довелося згортати. Перевагу віддали алгоритму DEFLATE (gzip) та перетворення Барроуза - Уїлера, BWT (bzip2). Що було і на краще, тому що ці алгоритми майже завжди перевершують зі стиснення LZW.
До 2003 року термін патенту минув, але поїзд уже пішов і алгоритм LZW зберігся, мабуть, лише у файлах GIF. Домінуючими є алгоритми на основі LZ77.
У 1993 році була ще одна битва патентів - коли компанія Stac Electronics виявила, що розроблений нею алгоритм LZS використовується компанією Microsoft у програмі для стиснення дисків, що поставлялася з MS-DOS 6.0. Stac Electronics подала до суду і їм удалося виграти справу, внаслідок чого вони отримали понад $100 мільйонів.

Зростання популярності Deflate

Великі корпорації використовували алгоритми стиснення для зберігання масивів даних, що все збільшувалися, але справжнє поширення алгоритмів сталося з народженням інтернету в кінці 80-х. Пропускна спроможність каналів була надзвичайно вузькою. Для стиснення даних, що передаються мережею, були придумані формати ZIP, GIF і PNG.
Том Хендерсон вигадав і випустив перший комерційно успішний архіватор ARC у 1985 році (компанія System Enhancement Associates). ARC була популярна серед користувачів BBS, т.к. вона одна з перших могла стискати кілька файлів в архів, причому вихідники її були відкриті. ARC використала модифікований алгоритм LZW.
Філ Катц, натхненний популярністю ARC, випустив програму PKARC у форматі shareware, у якій покращив алгоритми стиснення, переписавши їх на Асемблері. Проте був засуджений Хендерсоном і був визнаний винним. PKARC настільки відкрито копіювала ARC, що іноді навіть повторювалися помилки в коментарях до вихідного коду.
Але Філ Катц не розгубився, і в 1989 сильно змінив архіватор і випустив PKZIP. Після того, як його атакували вже у зв'язку з патентом на алгоритм LZW, він змінив і базовий алгоритм на новий під назвою IMPLODE. Знову формат було замінено у 1993 році з виходом PKZIP 2.0, і заміною став DEFLATE. Серед нових можливостей була функція розбиття архіву на томи. Ця версія досі повсюдно використовується, незважаючи на поважний вік.
Формат зображень GIF (Graphics Interchange Format) був створений компанією CompuServe в 1987 році. Як відомо, формат підтримує стиснення зображення без втрат, і обмежений палітрою в 256 кольорів. Попри всі потуги Unisys, їй вдалося зупинити поширення цього формату. Він досі популярний, особливо через підтримку анімації.
Злегка схвильована патентними проблемами компанія CompuServe в 1994 році випустила формат Portable Network Graphics (PNG). Як і ZIP, вона використала новий модний алгоритм DEFLATE. Хоча DEFLATE був запатентований Катцем, він став пред'являти жодних претензій.
Нині це найпопулярніший алгоритм стиснення. Крім PNG та ZIP він використовується в gzip, HTTP, SSL та інших технологіях передачі даних.

На жаль, Філ Катц не дожив до тріумфу DEFLATE, він помер від алкоголізму в 2000 році у віці 37 років. Громадяни – надмірне вживання алкоголю є небезпечним для вашого здоров'я! Ви можете не дожити свого тріумфу!

Сучасні архіватори

ZIP царював неподільно до середини 90-х, однак у 1993 році простий російський геній Євген Рошал придумав свій формат та алгоритм RAR. Останні його версії ґрунтуються на алгоритмах PPM та LZSS. Зараз ZIP, мабуть, найпоширеніший із форматів, RAR – донедавна був стандартом для поширення різного малолегального контенту через інтернет (завдяки збільшенню пропускної спроможності все частіше файли розповсюджуються без архівації), а 7zip використовується як формат із найкращим стиском при прийнятному часі роботи. У світі UNIX використовується зв'язка tar + gzip (gzip - архіватор, а tar поєднує кілька файлів в один, тому що gzip цього не вміє).

Прим. перев.Особисто я, крім перелічених, стикався ще з архіватором ARJ (Archived by Robert Jung), який був популярним у 90-х за доби BBS. Він підтримував багатотомні архіви, і так само, як після нього RAR, використовувався для поширення ігор та іншого варезу. Ще був архіватор HA від Harri Hirvola, який використовував стиснення HSC (не знайшов виразних пояснень - лише «модель обмеженого контексту та арифметичне кодування»), який добре справлявся зі стиском довгих текстових файлів.

У 1996 році з'явився варіант алгоритму BWT з відкритими вихідниками bzip2, і швидко набув популярності. 1999 року з'явилася програма 7-zip з форматом 7z. За стиснення вона змагається з RAR, її перевагою є відкритість, а також можливість вибору між алгоритмами bzip2, LZMA, LZMA2 та PPMd.
2002 року з'явився ще один архіватор, PAQ. Автор Метт Махоуні використав покращену версію алгоритму PPM з використанням техніки під назвою «контекстне змішування». Вона дозволяє використовувати більше однієї статистичної моделі, щоб покращити прогноз за частотою появи символів.

Майбутнє алгоритмів стиснення

Звичайно, бог його знає, але зважаючи на все, алгоритм PAQ набирає популярності завдяки дуже гарному ступеню стиснення (хоча і працює він дуже повільно). Але завдяки збільшенню швидкодії комп'ютерів швидкість роботи стає менш критичною.
З іншого боку, алгоритм Лемпеля-Зіва-Маркова LZMA є компромісом між швидкістю і ступенем стиснення і може породити багато цікавих відгалужень.
Ще одна цікава технологія substring enumeration або CSE, яка поки мало використовується в програмах.

У наступній частині ми розглянемо технічну сторону згаданих алгоритмів та принципи їхньої роботи.