LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм стиснення даних, розроблюваний від 1996 або 1998 року Ігорем Павловим. Використовується в архіваторі 7-Zip того ж автора для створення стиснутих архівів у форматі 7z.
Алгоритм заснований на схемі , подібній до використаної в LZ77, і забезпечує високий коефіцієнт стиснення (зазвичай перевищує коефіцієнт, що отримується за стиснення з використанням bzip2), а також дозволяє використовувати словники різного розміру (до 4 Гб).
Також lzma — утиліта командного рядка з відкритим кодом для стиснення даних з LZMA SDK, яка працює з файлами, що мають формат і розширення .lzma.
Огляд
Комплект засобів розробки з відкритим початковим кодом LZMA, написаний мовою , використовує покращений алгоритм стиснення LZ77, доповнений алгоритмом інтервального кодування, а також спеціальними процедурами для обробки двійкових файлів.
LZMA підтримує різні варіанти хеш-ланцюжків, двійкових і префіксних дерев як основи алгоритмів пошуку в словнику.
Алгоритми BCJ/BCJ2 для виконуваних файлів
LZMA SDK містить також алгоритм BCJ/BCJ2, реалізований для процесорів архітектури x86, ARM, PowerPC, IA-64 і (ARM Thumb). У ньому точки переходу перед стисненням нормалізуються — тобто, наприклад, для x86 це означає, що інструкції ближніх і умовних переходів і виклики функцій перетворюються з форми з відносним зсувом «перейти на 1665 байт назад» у форму з абсолютною адресою «перейти за адресою 5554».
Алгоритм BCJ2, реалізований у 7-Zip, використовує 32-бітну адресацію. В пакувальника виконуваних файлів адресація залежить від типу архітектури (наприклад, для виконуваних файлів DOS використовується 16-бітна адресація).
Реалізації
Реалізація, яка, починаючи з версії 4.61 beta, переведена з ліцензії CPL у категорію суспільного надбання, має такі властивості:
- Швидкість стиснення: приблизно 1 Мб/с на процесорі x86 з частотою 2 ГГц.
- Швидкість видобування: близько 10-20 Мб/с на процесорі x86 з частотою 2 ГГц.
- Підтримка багатонитковості.
Розмір коду розпакування LZMA становить близько 5 Кб; витрата динамічної пам'яті залежить від розміру словників. Ці можливості дозволяють реалізувати розпаковування на вбудованих системах.
Використання особливостей Microsoft Windows у сирцевому коді ускладнює створення версій програми для Unix. Проте, існує дві працездатні портовані версії: в p7zip більш або менш портовано версії утиліт командного рядка 7z та 7za для POSIX-систем (GNU/Linux, Solaris, OpenBSD, FreeBSD, Cygwin та інших), Mac OS X і BeOS.
Також є офіційна портована реалізація — LZMA Utils, призначена для створення потокових компресорів, подібних до gzip. Від 2008 року вона все частіше використовується в системах управління пакунками — зокрема, dpkg і RPM.
7-Zip використовує досить гнучкий формат архіву, його підтримують і деякі сторонні утиліти (наприклад, читання 7z підтримує WinRAR).
Також існує порт 7-Zip для Mac OS X, який називається Compress[]. Для Mac OS X існують ще збірки p7zip і .
Для роботи з LZMA автор надає свій кросплаформний SDK, що має перераховані вище властивості. Основна частина SDK написана на C++ і спочатку поширювалася на умовах GNU LGPL. Варто відзначити кілька моментів:
- Від версії 4.57 LZMA SDK надає також ANSI C-реалізації як алгоритму розпакування, так і алгоритму стискання, що розширює область застосування SDK і спрощує використання у вбудованих системах та інших обмежених середовищах (наприклад, у ядрах операційних систем).
- Від версії 4.62 LZMA SDK став доступним на умовах Public Domain, тобто допускається його використання для будь-яких цілей, без жодних обмежень.
Деякі мережеві пристрої (на зразок US Robotics 9105 і 9106) як мікропрограму використовують модифікований Linux, що завантажується зі стиснутої файлової системи. Для стиснення файлової системи замість Zlib використовується алгоритм LZMA. Як правило, такою файловою системою є squashfs з LZMA-патчем.
Крім цього, LZMA використовується в реалізаціях UEFI як один з алгоритмів стиснення.
LZMA2
LZMA2 — нова версія алгоритму LZMA. Цей алгоритм має такі переваги перед алгоритмом LZMA:
- вихідний потік може містити одночасно нестиснені і стиснені дані (нестисні дані записуються як є, що економить біти).
- краща підтримка багатонитковості під час стискання і розпакування.
Примітки
- Игорь Павлов несколько раз заявлял на SourceForge, что алгоритм LZMA создан им. (19 лютого 2004). . Архів оригіналу за 9 листопада 2012. Процитовано 16 червня 2013.
- . Архів оригіналу за 3 квітня 2011. Процитовано 20 жовтня 2020.
- LZMA utils [ 27 жовтня 2020 у Wayback Machine.](англ.)
- squashfs на SourceForge.net
- . Архів оригіналу за 29 жовтня 2012. Процитовано 20 жовтня 2020.
Посилання
- Офіційний сайт 7-Zip [ 12 травня 2006 у Wayback Machine.]
- LZMA SDK [ 2 лютого 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
LZMA angl Lempel Ziv Markov chain Algorithm algoritm stisnennya danih rozroblyuvanij vid 1996 abo 1998 roku Igorem Pavlovim Vikoristovuyetsya v arhivatori 7 Zip togo zh avtora dlya stvorennya stisnutih arhiviv u formati 7z Algoritm zasnovanij na shemi podibnij do vikoristanoyi v LZ77 i zabezpechuye visokij koeficiyent stisnennya zazvichaj perevishuye koeficiyent sho otrimuyetsya za stisnennya z vikoristannyam bzip2 a takozh dozvolyaye vikoristovuvati slovniki riznogo rozmiru do 4 Gb Takozh lzma utilita komandnogo ryadka z vidkritim kodom dlya stisnennya danih z LZMA SDK yaka pracyuye z fajlami sho mayut format i rozshirennya lzma OglyadKomplekt zasobiv rozrobki z vidkritim pochatkovim kodom LZMA napisanij movoyu C vikoristovuye pokrashenij algoritm stisnennya LZ77 dopovnenij algoritmom intervalnogo koduvannya a takozh specialnimi procedurami dlya obrobki dvijkovih fajliv LZMA pidtrimuye rizni varianti hesh lancyuzhkiv dvijkovih i prefiksnih derev yak osnovi algoritmiv poshuku v slovniku Algoritmi BCJ BCJ2 dlya vikonuvanih fajlivLZMA SDK mistit takozh algoritm BCJ BCJ2 realizovanij dlya procesoriv arhitekturi x86 ARM PowerPC IA 64 i ARM Thumb U nomu tochki perehodu pered stisnennyam normalizuyutsya tobto napriklad dlya x86 ce oznachaye sho instrukciyi blizhnih i umovnih perehodiv i vikliki funkcij peretvoryuyutsya z formi z vidnosnim zsuvom perejti na 1665 bajt nazad u formu z absolyutnoyu adresoyu perejti za adresoyu 5554 Algoritm BCJ2 realizovanij u 7 Zip vikoristovuye 32 bitnu adresaciyu V pakuvalnika vikonuvanih fajliv adresaciya zalezhit vid tipu arhitekturi napriklad dlya vikonuvanih fajliv DOS vikoristovuyetsya 16 bitna adresaciya RealizaciyiRealizaciya yaka pochinayuchi z versiyi 4 61 beta perevedena z licenziyi CPL u kategoriyu suspilnogo nadbannya maye taki vlastivosti Shvidkist stisnennya priblizno 1 Mb s na procesori x86 z chastotoyu 2 GGc Shvidkist vidobuvannya blizko 10 20 Mb s na procesori x86 z chastotoyu 2 GGc Pidtrimka bagatonitkovosti Rozmir kodu rozpakuvannya LZMA stanovit blizko 5 Kb vitrata dinamichnoyi pam yati zalezhit vid rozmiru slovnikiv Ci mozhlivosti dozvolyayut realizuvati rozpakovuvannya na vbudovanih sistemah Vikoristannya osoblivostej Microsoft Windows u sircevomu kodi uskladnyuye stvorennya versij programi dlya Unix Prote isnuye dvi pracezdatni portovani versiyi v p7zip bilsh abo mensh portovano versiyi utilit komandnogo ryadka 7z ta 7za dlya POSIX sistem GNU Linux Solaris OpenBSD FreeBSD Cygwin ta inshih Mac OS X i BeOS Takozh ye oficijna portovana realizaciya LZMA Utils priznachena dlya stvorennya potokovih kompresoriv podibnih do gzip Vid 2008 roku vona vse chastishe vikoristovuyetsya v sistemah upravlinnya pakunkami zokrema dpkg i RPM 7 Zip vikoristovuye dosit gnuchkij format arhivu jogo pidtrimuyut i deyaki storonni utiliti napriklad chitannya 7z pidtrimuye WinRAR Takozh isnuye port 7 Zip dlya Mac OS X yakij nazivayetsya Compress utochniti Dlya Mac OS X isnuyut she zbirki p7zip i Dlya roboti z LZMA avtor nadaye svij krosplaformnij SDK sho maye pererahovani vishe vlastivosti Osnovna chastina SDK napisana na C i spochatku poshiryuvalasya na umovah GNU LGPL Varto vidznachiti kilka momentiv Vid versiyi 4 57 LZMA SDK nadaye takozh ANSI C realizaciyi yak algoritmu rozpakuvannya tak i algoritmu stiskannya sho rozshiryuye oblast zastosuvannya SDK i sproshuye vikoristannya u vbudovanih sistemah ta inshih obmezhenih seredovishah napriklad u yadrah operacijnih sistem Vid versiyi 4 62 LZMA SDK stav dostupnim na umovah Public Domain tobto dopuskayetsya jogo vikoristannya dlya bud yakih cilej bez zhodnih obmezhen Deyaki merezhevi pristroyi na zrazok US Robotics 9105 i 9106 yak mikroprogramu vikoristovuyut modifikovanij Linux sho zavantazhuyetsya zi stisnutoyi fajlovoyi sistemi Dlya stisnennya fajlovoyi sistemi zamist Zlib vikoristovuyetsya algoritm LZMA Yak pravilo takoyu fajlovoyu sistemoyu ye squashfs z LZMA patchem Krim cogo LZMA vikoristovuyetsya v realizaciyah UEFI yak odin z algoritmiv stisnennya LZMA2LZMA2 nova versiya algoritmu LZMA Cej algoritm maye taki perevagi pered algoritmom LZMA vihidnij potik mozhe mistiti odnochasno nestisneni i stisneni dani nestisni dani zapisuyutsya yak ye sho ekonomit biti krasha pidtrimka bagatonitkovosti pid chas stiskannya i rozpakuvannya PrimitkiIgor Pavlov neskolko raz zayavlyal na SourceForge chto algoritm LZMA sozdan im 19 lyutogo 2004 Arhiv originalu za 9 listopada 2012 Procitovano 16 chervnya 2013 Arhiv originalu za 3 kvitnya 2011 Procitovano 20 zhovtnya 2020 LZMA utils 27 zhovtnya 2020 u Wayback Machine angl squashfs na SourceForge net Arhiv originalu za 29 zhovtnya 2012 Procitovano 20 zhovtnya 2020 PosilannyaOficijnij sajt 7 Zip 12 travnya 2006 u Wayback Machine LZMA SDK 2 lyutogo 2021 u Wayback Machine