Zstd

Zstd

Тип	бібліотека і консольний застосунок^d
Операційна система	GNU/Linux^[d], BSD^[d] і Mac OS
Мова програмування	C
Ліцензія	модифікована ліцензія BSD^d[1][2] і GNU General Public License, version 2.0^[d][1][3]
Репозиторій	github.com/facebook/zstd.git
Вебсайт	facebook.github.io/zstd/

zstd або Zstandard — це алгоритм стиснення без втрат, який розробляється з 2015 року при підтримці Facebook. Автор Ян Коллє (фр. Yann Collet). zstd — це референсна реалізація алгоритму Zstandard написана мовою C.

Реалізація використовує алгоритм стиснення типу LZ77, а також ефективне ентропійне кодування типу ANS.

Особливості

zstd був розроблений для забезпечення швидкості стиснення та декомпресії, зберігаючи при цьому співвідношення стиснення, порівнянне з алгоритмом Deflate (який був розроблений у 1991 році та використовується в оригінальних програмах ZIP та gzip).

zstd пропонує регульовані рівні стиснення від -7 (найшвидший) до 22 (найповільніший за швидкістю стиснення, але з найкращим коефіцієнтом стиснення).

Консольна утиліта zstd має адаптивний режим (--adapt), який регулює рівень стиснення залежно від умов вводу/виводу, зокрема від швидкості запису вихідних даних.

Швидкість декомпресії залишається стабільною на різних рівнях стиснення, коливаючись менше ніж на 20 %.

На максимальному рівні стиснення zstd досягає співвідношення стиснення близького до lzma, lzham та ppmx, і демонструє кращі результати ніж lza або bzip2.

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

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

Дизайн

Zstd поєднує етап зіставлення зі словником (LZ77) з великим вікном пошуку та швидким етапом кодування ентропії. Він використовує як кодування Хаффмана (використовується для записів у розділі літералів), так і ентропію з кінцевим станом (FSE) — швидку табличну версію ANS, tANS, що використовується для записів у розділі послідовностей. Через те, як FSE переносить стан між символами, декомпресія передбачає обробку символів у розділі послідовностей кожного блоку у зворотному порядку (з останнього до першого).

Використання

Алгоритм zstd використовується в ядрі Linux з версії 4.14 для використання в файлових системах btrfs та squashfs.

Також алгоритм тестувався в FreeBSD для інтеграції в файлову систему OpenZFS.

Деякі програми зберігання або обміну даних з вбудованим стисненням, алгоритм якого можна вибрати, використовують zstd опцією компресії:

• tar, TimescaleDB — для зберігання даних.
• rsync, mysql — для передачі даних.

Алгоритм та MIME-тип application/zstd були запропоновані в IETF[4]

Ліцензія

Референсна реалізація ліцензована під ліцензією BSD та розміщена на Github. З версії 1.0 zstd має додаткове «Надання патентних прав».

Примітки

1. License // https://github.com/facebook/zstd/blob/v1.3.3/README.md
2. https://github.com/facebook/zstd/blob/v1.3.3/LICENSE
3. https://github.com/facebook/zstd/blob/v1.3.3/COPYING
4. https://datatracker.ietf.org/doc/html/rfc8878