Алгоритми стиснення: опис, основні прийоми, характеристики

Стиснення є окремим випадком кодування, основною характеристикою якого є те, що результуючий код менше вихідного. Процес заснований на пошуку повторень в інформаційних рядах і подальшому збереженні тільки одного поруч з кількістю повторень. Таким чином, наприклад, якщо послідовність з`являється у файлі, як» AAAAAA", займаючи 6 байт, він буде збережений, як «6a», який займає тільки 2 байти, в алгоритмі стиснення RLE.

Історія виникнення процесу

Азбука Морзе, винайдена в 1838 році-перший відомий випадок стиснення даних. Пізніше, коли в 1949 році мейнфрейм-комп`ютери почали завойовувати популярність, Клод Шеннон і Роберт Фано винайшли кодування, названого на честь авторів-Шеннона-Фано. Це шифрування присвоює коди символам у масиві даних за теорією ймовірності.

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

У 1977 році, Авраам Лемпель і Джейкоб зів видали свій інноваційний метод LZ77, що використовує більш модернізований словник. У 1978 році, та ж команда авторів, видала вдосконалений алгоритм стиснення LZ78. Який використовує новий словник, який аналізує вхідні дані і генерує статичний словник, а не динамічний, як у 77 версії.

Форми виконання компресії

Компресія виконується програмою, яка використовує формулу або алгоритм, що визначають, як зменшити розмір даних. Наприклад, представити рядок бітів з меншим рядком 0 і 1, використовуючи словник для перетворень або формулу.

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

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

Перевага алгоритмів стиснення:

1. Значно зменшує обсяг пам`яті. При ступені стиснення 2: 1 файл в 20 мегабайт (МБ) займе 10 МБ простору. В результаті адміністратори мережі витрачають менше грошей і часу на зберігання баз даних.
2. Оптимізує продуктивність резервного копіювання.
3. Важливий метод скорочення даних.
4. Практично будь-який файл може бути стиснутий, але важливо вибрати потрібну технологію під конкретний тип файлу. Інакше файли можуть бути "зменшений", але при цьому загальний розмір не зміниться.

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

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

Алгоритм стиснення Хаффмана

Цей процес, який можна використовувати для "зменшення" або шифрування.

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

Порядок створення алгоритми стиснення даних:

1. Прораховують, скільки разів кожен символ повторюється в файлі для "зменшення".
2. Створюють пов`язаний список з інформацією про символи і частотах.
3. Виконують сортування списку від найменшого до найбільшого в залежності від частоти.
4. Перетворюють кожен елемент у списку на дерево.
5. Об`єднують дерева в одне, при цьому перші два утворюють нове.
6. Додають частоти кожної гілки в новий елемент дерева.
7. Вставляють нове в потрібне місце в списку, відповідно до суми отриманих частот.
8. Призначають новий двійковий код кожного символу. Якщо береться нульова гілка, до коду додається нуль, а якщо перша гілка, додається одиниця.
9. Файл перекодується відповідно до нових кодів.
10. Наприклад характеристики алгоритмів стиснення для короткого тексту:"ata la jaca a la estaca"
11. Підраховують, скільки разів з`являється кожен символ і складають пов`язаний список:" (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
12. Замовляють по частоті від нижчої до вищої: e (1), j (1), s (1), c (2), l (2), t (2), " (5), a (9)

Як видно, кореневої вузол дерева створений, далі призначаються коди.

І залишилося тільки упакувати біти в групи по вісім, тобто в байти:

Всього вісім байтів, а оригінальний текст був 23.

Демонстрація бібліотеки LZ77

Алгоритм LZ77 розглянемо на прикладі тексту«howtogeek». Якщо повторити його три рази, то він змінить його наступним чином.

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

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

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

Дискретне косинусне перетворення зображень

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

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

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

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

Стиснення аудіо працює дуже схоже на стиснення тексту та зображень. Якщо JPEG видаляє деталі з зображення, яке не видно людським оком, стиснення звуку робить, те ж саме для звуків. MP3 використовує бітрейт, починаючи від нижнього рівня 48 і 96 Кбіт/сек (нижня межа) до 128 і 240 Кбіт/сек (досить хороший) до 320 кбіт/сек (високоякісний звук), і різницю можна почути лише з надзвичайно хорошими навушниками. Існують кодеки стиснення без втрат для звуку, основним з яких є FLAC і використовує кодування LZ77 для передачі звуку без втрат.

Формат "зменшення" текст

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

Прогони значень кодуються, як символ, за яким слід довжина прогону. Можна правильно відновити оригінальний потік. Якщо довжина серії<= 2 Символи, має сенс просто залишити їх незмінними, наприклад, як у кінці потоку з «bb».

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

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

Схеми HTTP: DEFLATE та GZIP

Сьогодні в Інтернеті використовують два широко використовуваних алгоритмів стиснення тексту HTTP: DEFLATE і GZIP.

DEFLATE-зазвичай об`єднує дані, із застосуванням LZ77, кодування Хаффмана. Gzip-файлу використовує DEFLATE всередині, поряд з деякими цікавими блокуваннями, евристикою фільтрації, заголовком і контрольною сумою. Загалом, додаткове блокування та евристика, що використовують GZIP, дають якісні коефіцієнти стиснення, ніж просто один DEFLATE.

Протоколи даних наступного покоління-SPDY та HTTP2.0, підтримують стиснення заголовків за допомогою GZIP, тому більша частина веб-стека буде використовувати його і в майбутньому.

Більшість розробників просто завантажують нестиснений вміст і покладаються на веб-сервер для "зменшення" даних на льоту. Це дає відмінні результати і простий у використанні алгоритм стиснення графічних зображень. За замовчуванням на багатьох серверах встановлений gzip з рівнем 6, найбільший рівень якого дорівнює 9. Це робиться навмисно, що дозволяє серверам швидше стискати дані за рахунок більшого вихідного файлу.

Формати BZIP2 і LZMA, що створюють більш компактні форми ніж GZIP, які при цьому розпаковуються швидше.

LZMA можна вважати далеким родичем GZIP. Обидва вони починаються з популярного словника LZ, за яким слідує система статистичного кодування. Однак поліпшена LZMA-можливість компресувати файли малого розміру полягає в його " просунутих алгоритмах зіставлення і вікон LZ.

Попередня обробка документа

Для якісного стиснення виконують двоетапний процес:

• етап мінімізації;
• етап без втрат.

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

Є багато програм, які виконують основні алгоритми стиснення, серед них:

1. Winzip-це формат зберігання без втрат, який широко використовується для документів, зображень або програм. Це досить проста програма, яка стискає кожен з файлів окремо, що дозволяє відновлювати кожен без необхідності читати інші. Тим самим підвищуючи продуктивність процесу.
2. 7zip-безкоштовний менеджер для дуже потужного і найпростішого алгоритму стиснення інформації. Завдяки формату файлів 7z, який покращує Стандарт ZIP на 50%. Він підтримує інші найбільш поширені формати, такі як RAR, ZIP, CAB, GZIP і ARJ, тому не створює проблем для використання з будь-яким стисненим файлом і інтегрується з контекстним меню в Windows.
3. GZIP-це один з найвідоміших компресорів, призначених для Linux. Враховуючи успіх на цій платформі, його допрацювали для Windows. Однією з головних переваг gzip є те, що він використовує алгоритм DEFLATE (комбінація кодування LZ77 та Хаффмана).
4. WinRAR-Компресорна програма і багатофункціональний декомпресор даних. Це незамінний інструмент для економії місця на диску і часу передачі при відправці і отриманні файлів через Інтернет або при резервному копіюванні. Він служить для стиснення всіх типів документів або програм, щоб вони займали менше місця на диску і могли швидше зберігатися або передаватися по мережі. Це перший компресор, який реалізує 64-бітове управління файлами, що дозволяє обробляти великі обсяги, обмежені тільки операційна система.

Минификаторы CSS

Існує багато МІНІФІКАТОРІВ CSS. Деякі з доступних варіантів включають:

• онлайн CSS Minifier;
• freeformatter.com/css-minifier;
• cleancss.com/css-minify;
• cnvyr.io;
• minifier.org;
• css-minifier.com.

Основна відмінність між цими інструментами залежить від того, наскільки глибокі їх процеси мініфікації. Так, спрощена оптимізація фільтрує текст, щоб прибрати непотрібні прогалини і масиви. Розвинена оптимізація передбачає заміну "AntiqueWhite" на "# FAEBD7", оскільки шістнадцяткова форма в файлі коротше, і примусове використання символу нижнього gzip-регістра.

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

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

Плюси і мінуси стиснення

Основними перевагами стиснення є скорочення апаратних засобів зберігання, часу передачі даних і пропускної здатності зв`язку.

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

Основним недоліком компресії є вплив на продуктивність в результаті використання ресурсів ЦП і пам`яті для процесу і, подальшої розпакування.

Багато виробників розробили системи, щоб спробувати мінімізувати вплив ресурсномістких обчислень, пов`язаних зі стисненням. Якщо воно виконується до того як дані будуть записані на диск, система може розвантажити процес, щоб зберегти системні ресурси. Наприклад, IBM використовує окрему карту апаратного прискорення для обробки стиснення в деяких корпоративних системах зберігання даних.

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

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

З експоненціальним збільшенням апаратної швидкості відповідно до закону Мура, процеси змішування контексту, ймовірно, будуть процвітати. Так як витрати на швидкість долаються за рахунок швидкого обладнання через високий ступінь стиснення. Алгоритм, який PAQ прагнув покращити, називається "Прогнозування шляхів часткового зіставлення". Або PPM.

Нарешті, ланцюговий алгоритм Лемпеля-зіва-Маркова (LZMA) постійно демонструє чудовий компроміс між швидкістю та високим ступенем стиснення і, ймовірно, створить більше нових варіантів у майбутньому. Він буде лідирувати, оскільки вже прийнятий у багатьох конкуруючих форматах стиснення, наприклад, у програмі 7-Zip.

Іншим потенційним розвитком є використання компресії за допомогою перерахування підрядків (CSE), яка представляє собою перспективну технологію і поки не має багато програмних реалізацій.