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

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

Стиснення є приватним випадком кодування, основною характеристикою якого є те, що результуючий код менше вихідного. Процес заснований на пошуку повторень в інформаційних рядках і подальшому збереженні тільки одного поряд з кількістю повторень. Таким чином, наприклад, якщо послідовність з 'являється у файлі, як "AAAAA", займаючи 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)

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

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


01110010

11010101

11111011

00010010

11010101


11110111

10111001

10000000

0x72

0xd5


0xFB

0x12

0xd5

0xF7

0xB9


0x80

Всього вісім байтів, а вихідний текст був 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;
  • com/css-minifier;
  • com/css-minify;
  • io;
  • org;
  • css-minifier.com.

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

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

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

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

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

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

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

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

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

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

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

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

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