LZMA деректерді сығымдау алгоритмі: жоғары сығымдау қатынасы, жылдам ашу, 4ГБ дейін сөздік көлемі. 7-Zip форматында қолданылады. LZMA2 форматы туралы да біліңіз!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жоқтайтын деректерді қысу алгоритмі
Lossless data compression algorithm
Lempel–Ziv–Markov тізбегі алгоритмі (LZMA) – деректерді жоғалтпай қысу үшін қолданылатын алгоритм. Оны 1996 немесе 1998 жылдан бастап Игорь Павлов әзірлеген және алғаш рет 7-Zip архивтеушісінің 7z форматында пайдаланылған. Бұл алгоритм 1977 жылы Абрахам Лемпель мен Джейкоб Зив жариялаған LZ77 алгоритміне ұқсас сөздік негізіндегі қысу схемасын қолданады және жоғары қысу қатынасына (әдетте bzip2-ден жоғары) және өзгермелі қысу сөздігінің көлеміне (4 ГБ-қа дейін) ие, сонымен бірге басқа көп қолданылатын қысу алгоритмдерімен салыстырылатын қысу жылдамдығын сақтайды. LZMA2 – бұл қарапайым контейнер форматы, ол қысылмаған деректерді де, LZMA деректерін де, тіпті бірнеше түрлі LZMA кодтау параметрлерін де қамтуы мүмкін. LZMA2 кез келген деңгейде масштабталатын көп өрісті қысу және ашуды, сондай-ақ ішінара қысылмайтын деректерді тиімді қысуды қолдайды.
The Lempel–Ziv–Markov chain algorithm (LZMA) is an algorithm used to perform lossless data compression. It has been under development since either 1996 or 1998 by Igor Pavlov and was first used in the 7z format of the 7 Zip archiver. This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 and features a high compression ratio (generally higher than bzip2) and a variable compression dictionary size (up to 4 GB), while still maintaining decompression speed similar to other commonly used compression algorithms. LZMA2 is a simple container format that can include both uncompressed data and LZMA data, possibly with multiple different LZMA encoding parameters. LZMA2 supports arbitrarily scalable multithreaded compression and decompression and efficient compression of data which is partially incompressible.
Декомпрессия алгоритмінің егжей-тегжейі
Қысылған форматтың толыққанды табиғи тілдегі сипаттамасы, осы мәтінде жасалғаннан басқа, көрінеді жоқ. Төмендегі сипаттама Linux ядросының бастапқы кодында қамтылған Лассе Коллиннің ықшам XZ Embedded декодеріне негізделген, одан LZMA және LZMA2 алгоритмдерінің толық мәліметтерін салыстырмалы түрде оңай табуға болады: демек, кодты сілтеме ретінде пайдалану идеалды болмаса да, кез келген бағдарламашы төмендегі мәлімдемелерді бірнеше сағат жұмыс істеу арқылы тексеруге мүмкіндік алады.
No complete natural language specification of the compressed format seems to exist, other than the one attempted in the following text. The description below is based on the compact XZ Embedded decoder by Lasse Collin included in the Linux kernel source from which the LZMA and LZMA2 algorithm details can be relatively easily deduced: thus, while citing source code as reference is not ideal, any programmer should be able to check the claims below with a few hours of work.
Бүкіл сандардың ауқымын кодтау
Диапазондық декодер сонымен қатар біт ағашын, кері біт ағашын және бүтін сандарды декодтау мүмкіндіктерін, сондай-ақ жоғарыда сипатталған бір биттік декодтауды жалпылау үшін пайдаланылатын тұрақты ықтималдықпен бүтін сандарды декодтау құралдарын ұсынады. Лимиттен кіші қолтаңбасыз бүтін сандарды декодтау үшін (лимит - 1) 11 биттік ықтималдық айнымалысынан тұратын массив ұсынылады, олар тұжырымдамалық тұрғыдан лимит жапырақтары бар толық бинарлық ағаштың ішкі түйіндері ретінде орналасқан. Кері емес біт ағашын декодтау, айнымалылар ағашына көрсеткішті сақтап жұмыс істейді, ол түбірден басталады. Көрсеткіш жапыраққа бағытталмағанда, көрсеткіш көрсеткен айнымалыны пайдаланып бит декодталады, содан кейін бит 0 немесе 1 болған жағдайда көрсеткіш солға немесе оңға жылжытылады; көрсеткіш жапыраққа бағытталғанда, жапыраққа сәйкес келетін сан қайтарылады. Осылайша, кері емес біт ағашын декодтау ең маңызды биттен ең аз маңызды битке қарай жүзеге асырылады, тек жарамды диапазон ішінде бір ғана мән болғанда тоқтатылады (бұл концептуалды түрде диапазон өлшемдерінің екінің дәрежесі болмауына мүмкіндік береді, бірақ LZMA мұны пайдаланбайды). Кері біт ағашын декодтау, керісінше, ең аз маңызды биттен ең маңызды битке қарай декодтайды, сондықтан тек екінің дәрежесіндегі диапазонды ғана қолдайды және әрқашан бірдей бит санын декодтайды. Бұл екінің дәрежесі лимитімен кері емес біт ағашын декодтауды орындаумен және нәтиженің соңғы биттерін кері қайтарумен тең. Linux ядросындағы функцияда бүтін сандар шындығында [limit, 2 × limit) диапазонында қайтарылады (концептуалды мәнге лимит қосылады), массивтегі 0 индексіндегі айнымалы пайдаланылмайды, ал 1 индексіндегісі түбір болып табылады, ал сол және оң балалардың индекстері 2i және 2i + 1 ретінде есептеледі. Функцияның өзі [0, limit) диапазонындағы бүтін сандарды шақырушы ұсынған айнымалыға қосады, мұнда лимит оның логарифмі арқылы жасырылған, және тиімділік үшін өзінің тәуелсіз іске асырылуына ие. Тұрақты ықтималдықпен бүтін санды декодтау, ең маңыздыдан ең аз маңыздыға қарай биттерді оқып, тұрақты ықтималдықпен биттік декодтауды қайталап орындайды.
The range decoder also provides the bit tree, reverse bit tree and fixed probability integer decoding facilities, which are used to decode integers, and generalize the single bit decoding described above. To decode unsigned integers less than limit, an array of (limit − 1) 11 bit probability variables is provided, which are conceptually arranged as the internal nodes of a complete binary tree with limit leaves. Non reverse bit tree decoding works by keeping a pointer to the tree of variables, which starts at the root. As long as the pointer does not point to a leaf, a bit is decoded using the variable indicated by the pointer, and the pointer is moved to either the left or right children depending on whether the bit is 0 or 1; when the pointer points to a leaf, the number associated with the leaf is returned. Non reverse bit tree decoding thus happens from most significant to least significant bit, stopping when only one value in the valid range is possible (this conceptually allows to have range sizes that are not powers of two, even though LZMA does not make use of this). Reverse bit tree decoding instead decodes from least significant bit to most significant bits, and thus only supports ranges that are powers of two, and always decodes the same number of bits. It is equivalent to performing non reverse bittree decoding with a power of two limit, and reversing the last bits of the result. In the function in the Linux kernel, integers are actually returned in the [limit, 2 × limit) range (with limit added to the conceptual value), and the variable at index 0 in the array is unused, while the one at index 1 is the root, and the left and right children indices are computed as 2i and 2i + 1. The function instead adds integers in the [0, limit) range to a caller provided variable, where limit is implicitly represented by its logarithm, and has its own independent implementation for efficiency reasons. Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.
Сығу алгоритмінің егжей-тегжейі
Декомпрессиялық форматтарға ұқсас түрде, 7-Zip немесе xz кодилеу техникаларының толыққанды табиғи тілдегі сипаттамасы, төменде келтірілгеннен басқа, көрінетіндей емес. Төмендегі сипаттама Лассе Коллин жасаған Java үшін XZ кодилегішіне негізделген, ол бірдей алгоритмдерді қолдана отырып, түпнұсқа 7-Zip-тің бірнеше қайта жазылуының арасында ең түсінікті болып көрінеді: қайтадан айта кетейік, бастапқы кодты сілтеме ретінде келтіру – идеалды шешім емес, бірақ кез келген бағдарламашы төмендегі мәлімдемелерді бірнеше сағат жұмыс істеу арқылы тексеруге мүмкіндік алады.
Similar to the decompression format situation, no complete natural language specification of the encoding techniques in 7 zip or xz seems to exist, other than the one attempted in the following text. The description below is based on the XZ for Java encoder by Lasse Collin, which appears to be the most readable among several rewrites of the original 7 zip using the same algorithms: again, while citing source code as reference is not ideal, any programmer should be able to check the claims below with a few hours of work.
Сөздіктердегі іздеу деректерінің құрылымдары
Кодтаушы сөздікте сәйкестіктерді жылдам табуға қабілетті болуы керек. LZMA қысуды жақсарту үшін өте үлкен сөздіктерді (потенциалды түрде гигабайттармен өлшенетін) пайдаланатындықтан, егер бүкіл сөздікті қарап шығу керек болса, кодтаушы тым баяу болып, пайдалануға жарамсыз болып қалады. Сондықтан жылдам сәйкестіктерді іздеуге қолдау көрсету үшін күрделі дерек құрылымдары қажет.
The encoder needs to be able to quickly locate matches in the dictionary. Since LZMA uses very large dictionaries (potentially on the order of gigabytes) to improve compression, simply scanning the whole dictionary would result in an encoder too slow to be practically usable, so sophisticated data structures are needed to support fast match searches.
Хаш тізбектері
Ең қарапайым тәсіл, "хаш-тізбектер" деп аталады, және ол 2, 3 немесе 4 болатын N тұрақтысымен параметрленеді, бұл тұрақты әдетте сөздіктің көлемінен үлкен немесе оған тең етіп таңдалады. Ол әр k-ның N-ге тең немесе кіші мәні үшін k байттық тізімдермен индексиленген хаш-кесте құрудан тұрады, мұнда әрбір ұяшықта осы хаш-кесте ұяшығымен байланысты хаш-мәніне хэштелген бірінші k байттың соңғы орны сақталады. Тізбектеу, әрбір сөздік орны үшін соңғы рет көрінген және алғашқы N байты аталған орның алғашқы N байтымен бірдей хэштелген алдыңғы орнды сақтайтын қосымша массив арқылы жүзеге асырылады. N немесе одан жоғары ұзындықтағы сәйкестіктерді табу үшін іздеу N өлшемді хаш-кестесінен басталып, хаш-тізбек массиві арқылы жалғастырылады; іздеу, хаш-тізбек тораптарының алдын ала анықталған санынан өткесімен немесе хаш-тізбектер "айналып келгенде" тоқтатылады, бұл сөздікте қайта жазылған кірістің бөлігіне жеткенін көрсетеді. N-ден кіші өлшемдегі сәйкестіктер тек тиісті хаш-кестені қарау арқылы табылады, ол соңғы сәйкестікті (бар болса) немесе бірдей мәнге хэштелген тізбекті қамтиды; соңғы жағдайда кодер сәйкестікті таба алмайды. Бұл мәселе алыс қысқа сәйкестіктер үшін бірнеше литеральдарды пайдалану аз биттерді қажет етуімен және жақын тізбектерде хаш-қақтығыстардың болу ықтималдығының төмендігімен азайтылады; үлкен хаш-кестелерді немесе тікелей іздеу кестелерін пайдалану жоғары кэштен қашу деңгейі және төмен өнімділік есебінен проблеманы азайтуға болады. Барлық сәйкестіктерді растау қажет, себебі хаш-механизмі тек өткен уақытта хаш-кесте ұяшығы индексіне кейбір таңбалардың хэштелгенін кепілдік береді (кейбір іске асырулар тіпті оны кепілдік бермейді, өйткені олар дерек құрылымдарын инициализацияламайды).
The simplest approach, called "hash chains", is parameterized by a constant N which can be either 2, 3 or 4, which is typically chosen so that is greater than or equal to the dictionary size. It consists of creating, for each k less than or equal to N, a hash table indexed by tuples of k bytes, where each of the buckets contains the last position where the first k bytes hashed to the hash value associated with that hash table bucket. Chaining is achieved by an additional array which stores, for every dictionary position, the last seen previous position whose first N bytes hash to the same value of the first N bytes of the position in question. To find matches of length N or higher, a search is started using the N sized hash table, and continued using the hash chain array; the search stop after a pre defined number of hash chain nodes has been traversed, or when the hash chains "wraps around", indicating that the portion of the input that has been overwritten in the dictionary has been reached. Matches of size less than N are instead found by simply looking at the corresponding hash table, which either contains the latest such match, if any, or a string that hashes to the same value; in the latter case, the encoder will not be able to find the match. This issue is mitigated by the fact that for distant short matches using multiple literals might require less bits, and having hash conflicts in nearby strings is relatively unlikely; using larger hash tables or even direct lookup tables can reduce the problem at the cost of higher cache miss rate and thus lower performance. Note that all matches need to be validated to check that the actual bytes match currently at that specific dictionary position match, since the hashing mechanism only guarantees that at some past time there were characters hashing to the hash table bucket index (some implementations may not even guarantee that, because they do not initialize the data structures).
Екілік ағаштар
Бинарлық ағаш әдісі хештік тізбек әдісін ұстанады, бірақ тізбелеу үшін байланысты тізімнің орнына бинарлық ағашты логикалық түрде пайдаланады. Бинарлық ағаш әрқашан жұрнақтың лексикографиялық ретіне қатысты іздеу ағашы және сөздік позициясы бойынша максималды үйірме болып сақталады (яғни, түбірі әрқашан ең соңғы тізбек болады, ал баласы ата-анасынан кейінірек қосылған болмайды): егер барлық тізбектер лексикографиялық ретпен орналасса, онда бұл шарттар бинарлық ағашты бірегей түрде анықтайды (бұл ағаштың көлемі бойынша индукция арқылы оңай дәлелдеуге болады). Іздеуге және енгізуге арналған тізбек бірдей болғандықтан, сөздік бойынша іздеу және енгізуді (ағашты бұруды талап ететін) бір ағашты аралау арқылы жүзеге асыруға болады.
The binary tree approach follows the hash chain approach, except that it logically uses a binary tree instead of a linked list for chaining. The binary tree is maintained so that it is always both a search tree relative to the suffix lexicographic ordering, and a max heap for the dictionary position (in other words, the root is always the most recent string, and a child cannot have been added more recently than its parent): assuming all strings are lexicographically ordered, these conditions clearly uniquely determine the binary tree (this is trivially provable by induction on the size of the tree). Since the string to search for and the string to insert are the same, it is possible to perform both dictionary search and insertion (which requires to rotate the tree) in a single tree traversal.
LZMA2 кодтаушысы
XZ LZMA2 кодтаушысы кіріс деректерді бөліктерге бөліп өңдейді (созылмаған көлемі 2 МБ-қа дейін немесе 64 КБ-қа дейін, ең кішісін таңдайды), әр бөлікті LZMA кодтаушысына жібереді, содан кейін кодталған деректерді қамтитын LZMA2 LZMA бөлігін шығаруға немесе LZMA2 сығылмаған бөлігін шығаруға шешім қабылдайды, қайсысы қысқа болса, соны таңдайды (LZMA, кез келген басқа сығымдағыш сияқты, кейбір деректерді сығымдаудың орнына кеңейтуі мүмкін). LZMA жай-күйі тек бірінші бөлікте, шақырушы қасиеттерді өзгертуді сұраса және сығылған бөлік шығарылған сайын қалпына келтіріледі. LZMA қасиеттері тек бірінші бөлікте немесе шақырушы қасиеттерді өзгертуді сұраса ғана өзгертіледі. Сөздік тек бірінші бөлікте қалпына келтіріледі.
The XZ LZMA2 encoder processes the input in chunks (of up to 2 MB uncompressed size or 64 KB compressed size, whichever is lower), handing each chunk to the LZMA encoder, and then deciding whether to output an LZMA2 LZMA chunk including the encoded data, or to output an LZMA2 uncompressed chunk, depending on which is shorter (LZMA, like any other compressor, will necessarily expand rather than compress some kinds of data). The LZMA state is reset only in the first block, if the caller requests a change of properties and every time a compressed chunk is output. The LZMA properties are changed only in the first block, or if the caller requests a change of properties. The dictionary is only reset in the first block.
Жоғарғы кодтау қабаттары
LZMA2 кодтаудан бұрын, берілген опцияларға байланысты, xz BCJ сүзгісін қолдана алады, ол орындалатын кодты салыстырмалы офсеттерді көбірек қайталанатын абсолютті мәндермен алмастыру үшін сүзгілейді, немесе дельта сүзгісін қолданады, ол әр байтты одан бұрынғы байттың мәні мен арасындағы айырмамен алмастырады. Параллель кодтау файлды бөліктерге бөліп, оларды жіптерге (thread) таратады, содан кейін әр бөлік жеке кодталады (мысалы, xz блокты кодтау арқылы), нәтижесінде шығыс файлдағы бөліктер арасында сөздік жаңадан басталады.
Before LZMA2 encoding, depending on the options provided, xz can apply the BCJ filter, which filters executable code to replace relative offsets with absolute ones that are more repetitive, or the delta filter, which replaces each byte with the difference between it and the byte bytes before it. Parallel encoding is performed by dividing the file in chunks which are distributed to threads, and ultimately each encoded (using, for instance, xz block encoding) separately, resulting in a dictionary reset between chunks in the output file.
7-Zip эталондық іске асыру
7 Zip-тен алынған LZMA іске асырылуы LZMA SDK ретінде қолжетімді. Бастапқыда GNU LGPL және Common Public License екі лицензиясы бойынша, байланыстырылған бинарлық файлдарға арналған қосымша ерекшелікпен берілген, бірақ 2008 жылдың 2 желтоқсанында Игорь Павлов 4.62 нұсқасымен бірге оны қоғамдық доменге өткізді. Қазіргі таңда .7z форматы үшін стандартты сығылу әдісі болып табылады, 2012 жылдың 26 қазанындағы 9.30 нұсқасынан бастап. Ашық кодты LZMA сығылу кітапханасы бастапқыда C++ тілінде жазылған, бірақ ANSI C, C# және Java тілдеріне аударылды. 7 Zip іске асырылуы сөздік іздеу алгоритмінің негізі ретінде хэш-тізбектердің, бинарлық ағаштардың және Патрисия ағаштарының бірнеше түрлерін пайдаланады. LZMA-дан басқа, SDK және 7 Zip сығылуды жақсартуға арналған бірнеше алдын ала өңдеу сүзгілерін де іске асырады, олар қарапайым дельта кодтаудан (суреттер үшін) бастап, орындалатын код үшін BCJ-ге дейін жетеді. Ол сондай-ақ 7z форматында қолданылатын басқа да сығылу алгоритмдерін ұсынады. LZMA үшін тек сығылмайтын кодты компиляциялау көбінесе 5 КБ шамасында болады, ал сығылу кезінде қажетті RAM мөлшері негізінен сығылу кезінде қолданылатын жылжымалы терезенің мөлшерімен анықталады. Шағын код мөлшері, салыстырмалы түрде аз жадты қажет етуі, әсіресе кішкентай сөздік ұзындығында, және ашық бастапқы код LZMA сығылу алгоритмін кіріктірілген жүйелерге өте қолайлы етеді.
The LZMA implementation extracted from 7 Zip is available as LZMA SDK. It was originally dual licensed under both the GNU LGPL and Common Public License, with an additional special exception for linked binaries, but was placed by Igor Pavlov in the public domain on December 2, 2008, with the release of version 4.62. is now the default compression method for the .7z format, starting with version 9.30 on October 26, 2012. The reference open source LZMA compression library was originally written in C++ but has been ported to ANSI C, C#, and Java. The 7 Zip implementation uses several variants of hash chains, binary trees and Patricia trees as the basis for its dictionary search algorithm. In addition to LZMA, the SDK and 7 Zip also implements multiple preprocessing filters intended to improve compression, ranging from simple delta encoding (for images) and BCJ for executable code. It also provides some other compression algorithms used in 7z. Decompression only code for LZMA generally compiles to around 5 KB, and the amount of RAM required during decompression is principally determined by the size of the sliding window used during compression. Small code size and relatively low memory overhead, particularly with smaller dictionary lengths, and free source code make the LZMA decompression algorithm well suited to embedded applications.
Басқа іске асырулар
7-Zip эталондық нұсқасына қосымша, LZMA форматын келесілер қолдайды. xz: xz файл пішімінде LZMA және LZMA2 қолдайтын, gzip сияқты командалық жол құралы бар ағынды іске асыру. Ол жоғары өнімділігімен (bzip2-мен салыстырғанда) және шағын көлемімен (gzip-бен салыстырғанда) Unix сияқты жүйелердегі көптеген бағдарламалық қамтамасыздарға енді. Fedora қазір өз шығарылымдарын қысу үшін xz-ді пайдаланады. lzip: Unix сияқты жүйелер үшін xz-бен тікелей бәсекелесуге арналған тағы бір LZMA нұсқасы. Ол негізінен қарапайым файл пішімімен және осылайша қателерді оңай қалпына келтіру мүмкіндігімен ерекшеленеді. ZIPX: WinZip 12.1 нұсқасынан бастап құрылған ZIP қысылу форматының кеңейтімі. Ол BZip және PPMd сияқты басқа да қысу әдістерін де қолдана алады.
In addition to the 7 Zip reference implementation, the following support the LZMA format. xz: a streaming implementation that contains a gzip like command line tool, supporting both LZMA and LZMA2 in its xz file format. It made its way into several software of the Unix like world with its high performance (compared to bzip2) and small size (compared to gzip). and Fedora now use xz for compressing their releases. lzip: another LZMA implementation mostly for Unix like systems to be directly competing with xz. It mainly features a simpler file format and therefore easier error recovery. ZIPX: an extension to the ZIP compressions format that was created by WinZip starting with version 12.1. It also can use various other compression methods such as BZip and PPMd.
LZHAM
LZHAM (LZ, Huffman, Arithmetic, Markov) — LZMA сияқты, компрессия жылдамдығын өте жоғары сығылу коэффициенттері мен жоғары декомпрессия жылдамдығы үшін құрбан ететін әдіс. Авторы 2020 жылдың 15 қыркүйегінде оны жалпы қолданысқа қойды.
LZHAM (LZ, Huffman, Arithmetic, Markov), is an LZMA like implementation that trades compression throughput for very high ratios and higher decompression throughput. It was placed by its author in the public domain on 15 September 2020.