Як працює стиснення файлів?

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

Отже, як це працює?

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

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

LZ77, з іншого боку, є відносно простий і є те, про що ми будемо говорити тут. Вона прагне видалити дублікати слів і замінити їх меншим "ключем", що представляє слово.

Візьміть цей короткий фрагмент тексту, наприклад:

Алгоритм LZ77 буде дивитися на цей текст, розуміючи, що він повторює "howtogeek" тричі, і змінює його на це:

Потім, коли він хоче прочитати текст назад, він замінить кожен екземпляр (h) на "howtogeek", повертаючи нас до вихідної фрази.

Ми називаємо стиснення, подібне до цього «без втрат» - дані, які ви вводите, такі ж, як дані, які ви отримуєте. Нічого не втрачено.

Насправді, LZ77 не використовує список ключів, а замість другого і третього випадків замінює посилання:

Так що тепер, коли він добирається до (h), він оглянеться назад до "howtogeek" і прочитає це замість цього.

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

Тепер це ідеалізований приклад. Насправді, більшість тексту стискається за допомогою клавіш усього лише декількох символів. Наприклад, слово "the" буде стисло, навіть якщо воно з'являється словами "там", "їх" і "тоді". При повторному тексті можна отримати деякі божевільні коефіцієнти стиснення. Візьміть цей текстовий файл зі словом "howtogeek", який повторюється 100 разів. Оригінальний текстовий файл розміром три кілобайти. При стисненні він займає лише 158 байт. Це майже 95% стиснення.

Тепер, очевидно, це досить екстремальний приклад, оскільки ми просто повторювали одне й те саме слово. У загальній практиці, ви, ймовірно, отримаєте близько 30-40% стиснення, використовуючи формат стиснення, як ZIP на файлі, який в основному є текстом.

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

Як працює стиснення зображень і відео?

Стиснення відео та звуку працює дуже по-різному. На відміну від тексту, де ви можете мати стиснення без втрат, і дані не втрачаються, з зображеннями ми маємо те, що називається "Lossy Compression", де ви втрачаєте деякі дані. І чим більше ви стискаєте, тим більше даних ви втратите.

Це призводить до тих жахливих JPEG-файлів, які люди завантажували, спільно використовували і знімали кілька разів. Кожен раз, коли зображення стискається, воно втрачає деякі дані.

Ось приклад. Це знімок, який я взяв, який не був стиснутий взагалі.

Потім я взяв цей скріншот і запустив його через Photoshop кілька разів, кожен раз експортуючи його як низьку якість JPEG. Ось результат.

Виглядає досить погано, правильно?

Що ж, це лише найгірший сценарій, що кожен раз експортує на 0% якість JPEG. Для порівняння, тут є якісний JPEG з 50%, який майже не відрізняється від вихідного зображення PNG, якщо ви не підірвите його і не подивитеся ближче..

Розмір PNG для цього зображення становив 200 Кб, але цей формат JPEG розміром 50% складає лише 28 Кб.

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

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

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

Цей образ жахливий. Але незначна кількість стиснення JPEG може мати значний вплив на розмір файлу, і це робить JPEG дуже корисним для стиснення зображень на веб-сайтах. Більшість зображень, які ви бачите в Інтернеті, стискаються, щоб заощадити час завантаження, особливо для мобільних користувачів, які мають слабкі з'єднання даних. Насправді, всі зображення на How-To Geek були стиснуті, щоб зробити завантаження сторінки швидше, і ви, напевно, ніколи не помітили.

Стиснення відео

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

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

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

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

Інша річ, яку слід пам'ятати про відео, - його бітрейт - кількість даних, дозволених кожну секунду. Наприклад, якщо ваш бітрейт становить 200 кб / с, ваше відео буде виглядати досить погано. Якість зростає з підвищенням бітрейта, але після декількох мегабайт в секунду ви отримуєте зменшується прибуток.

Це збільшений кадр, знятий з відео медузи. Ліворуч - 3 Мб / с, а праворуч - 100 Мб / с.

30-кратне збільшення розміру файлу, але не значно підвищує якість. Взагалі, відео YouTube сидить близько 2-10Мб / с залежно від вашого підключення, тому що нічого більше, ймовірно, не буде помічено.

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

Стиснення звуку

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

MP3 також використовує бітрейт, починаючи від нижнього кінця 48 і 96 кбіт / с (низький кінець) до 128 і 240 кбіт / с (досить добре) до 320 кбіт / с (high-end audio), і ви, ймовірно, тільки почуєте різницю з виключно хорошими навушниками і вуха).

Існують також кодеки стиснення без втрат для аудіо, головним з яких є FLAC, який використовує кодування LZ77 для передачі звуку без втрат. Деякі люди клянуться з чудовою якістю звуку FLAC, але з поширенням MP3, здається, більшість людей або не може сказати або не заперечує різницю.