Після перегляду драми HBO «Silicon Valley» я завжди цікавився алгоритмами стиснення. Річард Хендрікс і його алгоритм стиснення посередині, звісно, фейкові, але після жорсткого пошуку в Google я зрозумів, що в реальному житті існує справжній геній алгоритму стиснення.
Ян Колле винайшов алгоритм стиснення LZ4 у 2011 році. Звісно, алгоритм LZ4 не такий вражаючий, як middle out, але він відомий своєю невразливою швидкістю стиснення та швидшою швидкістю декомпресії, коли гарантована певна швидкість стиснення.
Я не буду тут вдаватися в деталі оцінки швидкості стиснення, якщо вам цікаво, ви можете прочитати цю порівняльну статтю:Вхід за гіперпосиланням видно.
Також додається адреса github LZ4:Вхід за гіперпосиланням видно.
Ця стаття зосереджена на поясненні принципу алгоритму стиснення LZ4. Великий бог раніше написав пояснення алгоритму LZ4:Вхід за гіперпосиланням видно.Але коли я раніше вчився, мені здалося, що ця стаття не дуже дружня до новачків, тому я почав іншу статтю для таких новачків, як я.
Якщо підсумувати в одному реченні, LZ4 — це LZ77, який зберігає словник із хеш-таблицею розміру 16k і спрощує пошук.
LZ4 — це безвтратний алгоритм стиснення, який забезпечує швидкість стиснення > 500 МБ/с на ядро, який можна масштабувати за допомогою багатоядерних процесорів. Він має надзвичайно швидкі декодери зі швидкістю кількох ГБ/с на ядро, часто досягаючи обмежень швидкості оперативної пам'яті на багатоядерних системах.
Швидкість можна динамічно регулювати, обираючи коефіцієнт «прискорення», який замінює ступінь стиснення на вищу швидкість. З іншого боку, також передбачено LZ4_HC високого стиснення для збільшення стиснення за рахунок часу роботи процесора. Усі версії мають однакову швидкість декомпресії.
То що таке LZ77?
Стиснення LZ77 та принцип
LZ77 — це алгоритм, який застосовує словник для стиснення. Простими словами, це дозволяє програмі спостерігати (подивіться словник), чи дублюються поточні дані з попередніми, і якщо так, ми зберігаємо відстань (зсув) і довжину дублікатних полів, щоб замінити дубліковані поля та стиснути дані.
ПосиланняВхід за гіперпосиланням видно.
Для рядка з літер A A B C B при зчитуванні другого A програма зберігає (1,1) (1 цифра від попереднього, довжина 1), і аналогічно, коли читається друге B, програма зберігає (2,1) (відстань 2, довжина 1).
Але якщо рядок довший і програма постійно записує дані у словник, пошук дублікатів полів стає надзвичайно трудомістким, бо в найгіршому випадку програма переглядає весь словник з кожною новою літерою. LZ77 використовує метод ковзного вікна для вирішення цієї проблеми.
Подібно до початкової точки TCP із використанням ковзного вікна, ковзне вікно може зменшити площу кешу, щоб уникнути одночасної обробки надто великої кількості кешованих даних. У LZ77 словник не збільшується постійно, а відкидає перші символи, додані до словника, коли вони перевищують максимальний розмір, визначений словником, щоб зберегти розмір словника на встановленому максимальному розмірі.
Припустимо, довжина словника дорівнює 3
| словник |
| A | A B C B B A B C
Вихід (0,0,A)
| A A | Б В В Б Б А Б В
Результат(1,1)
| А А Б | C B B A B C
Вихід (0,0,B)
A | A B C | Б Б А Б В В
Вихід (0,0,C)
A A | B C B | Б А Б В
Вихід(2,1)
Інша частина ковзного вікна — це кеш для пошуку (буфер для перегляду не має офіційного перекладу). Кеш, який потрібно шукати, — це нестиснута частина довжини, найближча до словника. Алгоритм LZ77 співпадає з найдовшим рядком у цій частині символу, який збігається зі словником. Попередній приклад можна розглядати як буфер огляду вперед 1.
Припустимо, довжина словника — 5, а розмір кешу, який потрібно шукати, — 3
| словник | Буфер Look Ahead |
A | A B C B B | A B C |
Вихід(5,3)
Найдовша низка, що співпадає, — це ABC
Повний процес стиснення:
Припустимо, довжина словника — 5, а розмір кешу, який потрібно шукати, — 3
| словник | Буфер Look Ahead |
| А А Б | C B B A B C
Вихід (0,0,A)
| A | A B C | Б Б А Б В В
Результат(1,1)
| A A | B C B | Б А Б В
Вихід (0,0,B)
| А А Б | C B B | А Б В
Вихід (0,0,C)
| A A B C | B B A | B C
Вихід(2,1)
| A A B C B | B A B | C
Результат(1,1)
A | A B C B B | A B C |
Вихід(5,3)
A A B C | B B A B C | 。。。 |
Немає потреби зберігати словник у вихідному файлі компресора, оскільки програма декомпресії відновлює словник, зіставляючи вихідні одиниці.
Процес декомпресії
Однією з великих переваг алгоритму LZ77 є те, що він дуже швидко розповсюджується.
Якщо перша одиниця співпадіння — (0,0,A), то A — це вихід.
Друга одиниця співпадіння — (1,1), яка копіює попередній біт у вихідному рядку і виводить A, якщо довжина копіювання дорівнює 1.
。。。
Якщо останній підбірний блок — (5,3), то подивись назад на 5 біт у вихідному рядку копіювання, а якщо довжина копії 3, то виведи A, B, C.
Найбільш трудомісткою частиною стиснення алгоритму LZ77 є пошук найдовшого відповідного символу в кеші для пошуку у словнику. Якщо словник і кеш для пошуку занадто короткі, шанси знайти збіг дуже малі. Тому LZ4 змінив алгоритм відповідності для LZ77.
По-перше, словник алгоритму LZ4 — це хеш-таблиця. Ключ у словнику — це 4-байтовий рядок, кожен ключ відповідає лише одному слоту, а значення в слоті — це позиція цього рядка.
Замість пошуку в кеші LZ4 зчитує по чотири байти з вхідного файлу за раз, а потім шукає слот, що відповідає рядку в хеш-таблиці, який далі називається поточним рядком.
Якщо ви дійшли до останніх 12 символів, введіть їх безпосередньо у вихідний файл.
Якщо в слоті не призначено значення, це означає, що чотири байти з'являються вперше, додайте ці чотири байти та позиції до хеш-таблиці і продовжуйте пошук.
Якщо в слоті є призначення, це означає, що ми знайшли відповідне значення.
Якщо значення в слоті плюс розмір вікна повзунка < позицією поточного символу, то позиція співпадіння перевищує розмір блоку, і програма оновлює значення в хеш-слоті до позиції поточного рядка.
LZ4 перевірить, чи був конфлікт хешів. Якщо 4 байти в слоті не збігаються з поточним рядком, має бути конфлікт хешів. Власний xxhash автора також відомий своєю ефективністю, але конфлікти неминучі. У разі конфлікту програма також оновлює значення в хеш-слоті до поточного положення рядка
Нарешті, ми можемо підтвердити, що збіг дійсний, і програма продовжить перевіряти, чи такі ж наступні символи в рядку відповідності. Нарешті, скопіюйте всі символи з кінця попереднього дійсного збігу на початок цього дійсного збігу у стиснений файл і додайте послідовність відповідності цього дійсного збігу.
Колле називає відповідні одиниці, які виводяться послідовностями LZ4, і вони утворюють стиснутий файл LZ4. Деталі такі:
Токен має довжину 1 байт, перші 4 слова — це довжина літера, а останні 4 слова — довжина матчу. Як уже згадувалося, усі символи від кінця попереднього дійсного збігу до початку цього дійсного збігу будуть скопійовані у стиснений файл, ці несжаті файли є літеральними, а їхня довжина — літеральна довжина.
За цим буквально слідує відхилення. Як і в LZ77, відхилення та довжина збігу означають довжину поточного рядка від її збігу, а довжина матчу — довжину довжини поточного рядка з тим самим рядком у словнику. У декомпресії потрібно пройти по ній, щоб знайти рядок для копіювання та довжину для скопіювання. Величина відхилення фіксована.
На рисунку літеральна довжина+ і довжина матчу+ — якщо літерал або довжини match, 4 слова в жетоні недостатньо, вони продовжать збільшуватися на відповідних позиціях. 4 слова можуть представляти від 0 до 15, а якщо їх більше, додайте один байт, тобто 255 до розміру, доки байт не стане меншим за 255. У довжині відповідності 0 означає 4 байти.
Останні 12 байтів закінчуються буквально тому, що їх скопіювали безпосередньо.
Давайте подивимося на код (python більш абстрактний)
Резюме Попри все це, я досі не пояснив, чому LZ4 такий швидкий. Спочатку порівняємо пошук у словнику між LZ77 і LZ4. Рідний LZ77 шукає словники, шукаючи найбільший збіг у кеші та словнику. Це задача знаходження найбільшої ідентичної струни у двох рядках. Якщо ми не використовуємо динамічне програмування, то в найгіршому випадку доведеться розглядати всі підрядки одного рядка і потім зіставляти їх у інший. Якщо ×ми використовуємо динамічне програмування, то використовуємо таблицю для зберігання найдовшого збігу в динаміці, що дозволить завершити збіг лише у випадку O(m*n). І це лише для пари пошукових кешів і словників. У найгіршому випадку, якщо збігів немає, LZ77 доведеться рахувати (довжину всього файлу — довжину кешу, який потрібно шукати) стільки ж таких проблем із відповідністю. LZ4 фактично використовує більший рівень динамічного програмування: він зберігає 4 байти та їхні позиції в хеш-таблиці, а потім кожного разу співставляє нові 4 байти даних, щоб перевірити, чи є значення в хеш-таблиці коректними. Після знаходження дійсного відповідного значення, якщо подивитися на наступні дані двох наборів відповідних значень, можна також знайти найдовше збігання. Оскільки кожен ключ хеш-таблиці LZ4 відповідає лише одному слоту, робота з пошуку, додавання і модифікації хеш-таблиці потребує лише O(1). Якщо після збігу знаходять більше збігів, потрібно більше групових порівнянь, але загалом ці порівняння замінять більше часу на пошук хеш-таблиці, тому загальний час алгоритму LZ4 дорівнює лише O(n). Я маю захоплюватися красою алгоритму Колле! Щоб зробити алгоритм ще швидшим, Collet встановлює стандартний розмір хеш-таблиці 16k, що рекомендується не перевищувати 32k, щоб його можна було помістити у L1-кеш майже всіх процесорів (Intel). Всі знають, що швидкість і співвідношення пам'яті кешу процесора L1 дуже різні, тому не дивно, що LZ4 летить дуже швидко, не кажучи вже про те, що хеш-рівняння, яке використовується в хеш-таблиці LZ4, досі є найшвидшим xxhash. Звісно, такий дизайн має свої недоліки. Чим менша хеш-таблиця, тим менше ключів. Це означає, що виникнуть нові конфлікти хешів, що неминуче. А більше колізій хешів означає менше збігів. Менша хеш-таблиця також означає менше ковзне вікно, а це означає, що більше збігів буде відкинуто, бо вони занадто далеко. Менша кількість збігів означає менший ступінь стиснення, тому LZ4 має менш помітний ступінь стиснення. Дивлячись у майбутнє, LZ4 має широкий спектр сценаріїв застосування. Так само, як middle-out використовувався у VR у Кремнієвій долині, LZ4 може збільшити використання пропускної здатності, додаючи менше IO-введення за рахунок дуже низької затримки завдяки дуже високій швидкості стиснення. Є також невелика гіпотеза: якщо процесор має більший кеш на рівні 1, чи може LZ4 збільшити коефіцієнт стиснення без компромісу для швидкості?
Оригінальний:Вхід за гіперпосиланням видно. |
Опубліковано 03.01.2022 13:54:23
|
|
|
|
