lzma – Lempel–Ziv–Markov chain algorithm

ompression disebut juga irreversible compression karena data asli mustahil untuk dikembalikan seperti semula. Kelebihan teknik ini adalah rasio kompresi yang tinggi dibanding metode lossless. Keuntungan dari metode lossy atas lossless adalah dalam beberapa kasus metode lossy menghasilkan file kompresi yang lebih kecil dibandingkan dengan metode lossless. Metode lossy sering digunakan untuk mengkompresi suara, gambar dan video karena data tersebut dimaksudkan kepada human interpretation dimana pikiran dapat dengan mudah “mengisi bagian-bagian yang kosong” atau melihat kesalahan yang sangat kecil atau inkonsistensi. Sedangkan lossless digunakan untuk mengkompresi data untuk diterima ditujuan dalam kondisi asli seperti dokumen teks. Lossy akan mengalami generation loss pada data sedangkan pada lossless tidak terjadi karena data yang hasil dekompresi sama dengan data asli.

Gambaran
LZMA menggunakan algoritme kompresi kamus (varian LZ77 dengan ukuran kamus besar dan dukungan khusus untuk jarak pencocokan yang digunakan berulang kali), yang keluarannya kemudian dikodekan dengan enkoder rentang, menggunakan model kompleks untuk membuat prediksi probabilitas setiap bit. Kompresor kamus menemukan kecocokan menggunakan struktur data kamus yang canggih, dan menghasilkan aliran simbol literal dan referensi frase, yang dikodekan sedikit demi sedikit oleh range encoder: banyak pengkodean dimungkinkan, dan algoritma pemrograman dinamis digunakan untuk memilih sebuah yang optimal dengan perkiraan tertentu.[7]

Sebelum LZMA, sebagian besar model pembuat enkode murni berbasis byte (yaitu mereka mengkodekan setiap bit hanya menggunakan kaskade konteks untuk mewakili ketergantungan pada bit sebelumnya dari byte yang sama). Inovasi utama LZMA adalah bahwa alih-alih model berbasis byte generik, model LZMA menggunakan konteks khusus untuk bitfield di setiap representasi literal atau frase: ini hampir sesederhana model berbasis byte generik, tetapi memberikan jauh lebih baik kompresi karena menghindari pencampuran bit yang tidak terkait bersama dalam konteks yang sama. Selain itu, dibandingkan dengan kompresi kamus klasik (seperti yang digunakan dalam format zip dan gzip), ukuran kamus bisa dan biasanya jauh lebih besar, dengan memanfaatkan banyaknya memori yang tersedia di sistem modern.

Ikhtisar format terkompresi
Dalam kompresi LZMA, aliran terkompresi adalah aliran bit, yang dikodekan menggunakan pengkode rentang biner adaptif. Aliran dibagi menjadi paket-paket, setiap paket menggambarkan satu byte, atau urutan LZ77 dengan panjang dan jaraknya yang dikodekan secara implisit atau eksplisit. Setiap bagian dari setiap paket dimodelkan dengan konteks independen, sehingga prediksi probabilitas untuk setiap bit berkorelasi dengan nilai bit tersebut (dan bit terkait dari bidang yang sama) di paket sebelumnya dengan tipe yang sama. Dokumentasi lzip[8] dan LZMA SDK menjelaskan format streaming ini.[7]

Ada 7 jenis paket:[8]

LONGREP[*] merujuk ke paket LONGREP[0-3], *REP merujuk ke LONGREP dan SHORTREP, dan *MATCH merujuk ke MATCH dan *REP.

Paket LONGREP[n] menghapus jarak yang digunakan dari daftar jarak terbaru dan memasukkannya kembali di depan, untuk menghindari entri berulang yang tidak berguna, sedangkan MATCH hanya menambahkan jarak ke depan meskipun sudah ada dalam daftar dan SHORTREP dan LONGREP [0] jangan mengubah daftar.

Panjangnya dikodekan sebagai berikut:

Seperti pada LZ77, panjangnya tidak dibatasi oleh jarak, karena penyalinan dari kamus didefinisikan seolah-olah penyalinan dilakukan byte demi byte, menjaga jarak konstan.

Jarak secara logis 32-bit dan jarak 0 menunjuk ke byte yang terakhir ditambahkan dalam kamus.

Pengkodean jarak dimulai dengan “slot jarak” 6-bit, yang menentukan berapa banyak bit tambahan yang diperlukan. Jarak didekodekan sebagai rangkaian biner, dari yang paling signifikan hingga yang paling tidak signifikan, dua bit tergantung pada slot jarak, beberapa bit dikodekan dengan probabilitas tetap 0,5, dan beberapa bit dikodekan konteks, menurut tabel berikut (slot jarak 0−3 langsung dikodekan jarak 0−3).

Detail algoritma dekompresi

Tampaknya tidak ada spesifikasi bahasa alami lengkap dari format terkompresi, selain yang dicoba dalam teks berikut.

Uraian di bawah ini didasarkan pada dekoder XZ Embedded yang ringkas oleh Lasse Collin yang disertakan dalam sumber kernel Linux[9] yang darinya detail algoritme LZMA dan LZMA2 dapat disimpulkan dengan relatif mudah: jadi, meskipun mengutip kode sumber sebagai referensi tidak ideal, ada programmer harus dapat memeriksa klaim di bawah ini dengan beberapa jam kerja.

Rentang pengkodean bit
Data LZMA berada pada level terendah yang didekodekan satu per satu oleh dekoder rentang, sesuai arah dekoder LZMA.

Penguraian kode rentang berbasis konteks dipanggil oleh algoritme LZMA yang meneruskannya sebagai referensi ke “konteks”, yang terdiri dari prob variabel 11-bit yang tidak ditandatangani (biasanya diimplementasikan menggunakan tipe data 16-bit) yang mewakili probabilitas prediksi dari bit tersebut. 0, yang dibaca dan diperbarui oleh dekoder rentang (dan harus diinisialisasi ke {\displaystyle 2^{10}}{\displaystyle 2^{10}}, mewakili probabilitas 0,5).

Penguraian rentang probabilitas tetap alih-alih mengasumsikan probabilitas 0,5, tetapi beroperasi sedikit berbeda dari pengodean rentang berbasis konteks.

Status dekoder rentang terdiri dari dua variabel 32-bit yang tidak ditandatangani, rentang (mewakili ukuran rentang), dan kode (mewakili titik yang disandikan dalam rentang).

Inisialisasi range decoder terdiri dari pengaturan range ke 232 − 1, dan kode ke nilai 32-bit mulai dari byte kedua dalam aliran yang diinterpretasikan sebagai big-endian; byte pertama dalam aliran benar-benar diabaikan.

Normalisasi berlangsung dengan cara ini:

1. Geser rentang dan kode ke kiri 8 bit
2. Baca satu byte dari aliran terkompresi
3. Setel kode 8 bit paling tidak signifikan ke nilai byte yang dibaca

Decoding rentang berbasis konteks dari bit menggunakan variabel probabilitas prob berlangsung dengan cara ini:

• Jika rentang kurang dari {\displaystyle 2^{24}}{\displaystyle 2^{24}}, lakukan normalisasi
• Set terikat ke {\displaystyle \lfloor range/2^{11}\rfloor *prob}{\displaystyle \lfloor range/2^{11}\rfloor *prob}
• Jika kode kurang dari terikat:
  1 Tetapkan rentang ke terikat
  2 Setel prob ke prob + {\displaystyle \lfloor 2^{11}-prob\rfloor /2^{5}}{\displaystyle \lfloor 2^{11}-prob\rfloor /2^{5}}
  3 Kembalikan sedikit 0
• Jika tidak (jika kode lebih besar dari atau sama dengan batas):
  1 Atur rentang ke rentang − terikat
  2 Tetapkan kode ke kode – terikat
  3 Tetapkan prob ke {\displaystyle prob-\lfloor prob/2^{5}\rfloor }{\displaystyle prob-\lfloor prob/2^{5}\rfloor }
  4 Kembalikan sedikit 1

Decoding rentang probabilitas tetap dari suatu bit berlangsung dengan cara ini:

1. Jika rentang kurang dari {\displaystyle 2^{24}}{\displaystyle 2^{24}}, lakukan normalisasi
2. Tetapkan rentang ke {\displaystyle \lfloor range/2\rfloor }{\displaystyle \lfloor range/2\rfloor }
3. Jika kode kurang dari rentang:
   1 Kembalikan sedikit 0
4. Jika tidak (jika kode lebih besar atau sama dengan rentang):
   1 Tetapkan kode ke rentang kode
   2 Kembalikan sedikit 1

Implementasi kernel Linux dari decoding probabilitas-tetap di rc_direct(), karena alasan kinerja, tidak menyertakan cabang bersyarat, melainkan mengurangi rentang dari kode tanpa syarat. Bit tanda yang dihasilkan digunakan untuk memutuskan bit untuk dikembalikan dan untuk menghasilkan topeng yang digabungkan dengan kode dan ditambahkan ke rentang.

• Perhatikan bahwa:

1. Pembagian dengan {\displaystyle 2^{11}}{\displaystyle 2^{11}} saat komputasi terikat dan operasi dasar dilakukan sebelum perkalian, bukan setelahnya (tampaknya untuk menghindari kebutuhan dukungan perangkat keras yang cepat untuk perkalian 32-bit dengan hasil 64-bit)
2. Dekoding probabilitas tetap tidak sepenuhnya setara dengan decoding rentang berbasis konteks dengan nilai prob apa pun, karena fakta bahwa dekode rentang berbasis konteks membuang rentang 11 bit yang lebih rendah sebelum dikalikan dengan prob seperti yang baru saja dijelaskan, sementara decoding probabilitas tetap hanya membuang bit terakhir

Rentang pengkodean bilangan bulat
Dekoder rentang juga menyediakan fasilitas dekode bit-tree, reverse bit-tree, dan probabilitas tetap bilangan bulat, yang digunakan untuk mendekode bilangan bulat, dan menggeneralisasi dekode bit tunggal yang dijelaskan di atas. Untuk mendekode bilangan bulat tak bertanda yang kurang dari batas, disediakan array (batas − 1) variabel probabilitas 11-bit, yang secara konseptual disusun sebagai simpul internal dari pohon biner lengkap dengan daun batas.

Dekode bit-tree non-terbalik berfungsi dengan mempertahankan pointer ke pohon variabel, yang dimulai dari root. Selama penunjuk tidak menunjuk ke daun, bit didekodekan menggunakan variabel yang ditunjukkan oleh penunjuk, dan penunjuk dipindahkan ke anak kiri atau kanan tergantung pada apakah bitnya 0 atau 1; ketika penunjuk menunjuk ke daun, nomor yang terkait dengan daun dikembalikan.

Dekode bit-tree non-terbalik dengan demikian terjadi dari bit yang paling signifikan hingga yang paling tidak signifikan, berhenti ketika hanya satu nilai dalam rentang yang valid dimungkinkan (ini secara konseptual memungkinkan untuk memiliki ukuran rentang yang bukan pangkat dua, meskipun LZMA tidak menggunakan ini).

Alih-alih mendekodekan bit-tree terbalik, mendekodekan dari bit paling signifikan ke bit paling signifikan, dan dengan demikian hanya mendukung rentang yang merupakan kekuatan dua, dan selalu mendekodekan jumlah bit yang sama. Ini setara dengan melakukan decoding bittree non-terbalik dengan kekuatan dua batas, dan membalikkan bit log2(batas) terakhir dari hasil.

Dalam fungsi rc_bittree di kernel Linux, bilangan bulat sebenarnya dikembalikan dalam rentang [batas, 2 * batas) (dengan batas ditambahkan ke nilai konseptual), dan variabel pada indeks 0 dalam larik tidak digunakan, sedangkan variabel pada indeks 1 adalah root, dan indeks anak kiri dan kanan dihitung sebagai 2i dan 2i + 1. Fungsi rc_bittree_reverse sebagai gantinya menambahkan bilangan bulat dalam rentang [0, limit) ke variabel yang disediakan pemanggil, di mana limit secara implisit diwakili oleh logaritmanya , dan memiliki implementasi independennya sendiri untuk alasan efisiensi.

Dekode bilangan bulat probabilitas tetap hanya melakukan decoding bit probabilitas tetap berulang kali, membaca bit dari yang paling signifikan hingga yang paling tidak signifikan.

konfigurasi LZMA
Dekoder LZMA dikonfigurasi oleh byte “properti” lclppb dan ukuran kamus. Nilai byte lclppb adalah lc + lp * 9 + pb * 9 * 5, di mana:

1. lc adalah jumlah bit tinggi dari byte sebelumnya untuk digunakan sebagai konteks pengkodean literal (nilai default yang digunakan oleh LZMA SDK adalah 3)
2. lp adalah jumlah bit rendah dari posisi kamus untuk disertakan dalam literal_pos_state (nilai default yang digunakan oleh LZMA SDK adalah 0)
3. pb adalah jumlah bit rendah dari posisi kamus untuk disertakan dalam pos_state (nilai default yang digunakan oleh LZMA SDK adalah 2)

Dalam aliran non-LZMA2, lc tidak boleh lebih besar dari 8, dan lp dan pb tidak boleh lebih besar dari 4. Dalam aliran LZMA2, (lc + lp) dan pb tidak boleh lebih besar dari 4.

Dalam format file LZMA 7-zip, konfigurasi dilakukan oleh header yang berisi byte “properti” diikuti oleh ukuran kamus little-endian 32-bit dalam byte. Di LZMA2, byte properti dapat diubah secara opsional pada awal paket LZMA2 LZMA, sedangkan ukuran kamus ditentukan di header LZMA2 seperti yang dijelaskan nanti.

Konteks pengkodean LZMA
Format paket LZMA telah dijelaskan, dan bagian ini menentukan bagaimana LZMA secara statistik memodelkan stream yang dikodekan LZ, atau dengan kata lain variabel probabilitas mana yang diteruskan ke dekoder rentang untuk mendekode setiap bit.

Variabel probabilitas tersebut diimplementasikan sebagai array multi-dimensi; sebelum memperkenalkannya, beberapa nilai yang digunakan sebagai indeks dalam larik multidimensi ini ditentukan.

Nilai status secara konseptual didasarkan pada pola mana dalam tabel berikut yang cocok dengan 2-4 jenis paket terbaru yang terlihat, dan diimplementasikan sebagai status mesin negara yang diperbarui menurut tabel transisi yang tercantum dalam tabel setiap kali paket dikeluarkan.

Keadaan awal adalah 0, dan dengan demikian paket sebelum permulaan diasumsikan sebagai paket LIT.

Nilai pos_state dan literal_pos_state masing-masing terdiri dari pb dan lp (hingga 4, dari header LZMA atau paket properti LZMA2) bit paling tidak signifikan dari posisi kamus (jumlah byte yang dikodekan sejak modul reset kamus terakhir ukuran kamus). Perhatikan bahwa ukuran kamus biasanya merupakan kelipatan dari pangkat 2 yang besar, jadi nilai ini secara ekuivalen digambarkan sebagai bit signifikan terkecil dari jumlah byte yang tidak terkompresi yang terlihat sejak pengaturan ulang kamus terakhir.

Nilai prev_byte_lc_msbs diatur ke lc (sampai 4, dari header LZMA atau paket properti LZMA2) bit paling signifikan dari byte yang tidak terkompresi sebelumnya.

Nilai is_REP menunjukkan apakah paket yang menyertakan panjang adalah LONGREP daripada MATCH.

Nilai match_byte adalah byte yang akan didekodekan jika paket SHORTREP telah digunakan (dengan kata lain, byte ditemukan di kamus pada jarak terakhir yang digunakan); ini hanya digunakan setelah paket *MATCH.

literal_bit_mode adalah array dari 8 nilai dalam rentang 0-2, satu untuk setiap posisi bit dalam satu byte, yaitu 1 atau 2 jika paket sebelumnya adalah *MATCH dan itu adalah posisi bit paling signifikan atau lebih signifikan bit dalam literal untuk menyandikan/mendekode sama dengan bit pada posisi yang sesuai dalam match_byte, sedangkan jika tidak, itu adalah 0; pilihan antara nilai 1 atau 2 tergantung pada nilai bit pada posisi yang sama di match_byte.

Kumpulan variabel literal/Literal dapat dilihat sebagai “pseudo-bit-tree” mirip dengan bit-tree tetapi dengan 3 variabel, bukan 1 di setiap node, dipilih tergantung pada nilai literal_bit_mode pada posisi bit dari bit berikutnya untuk mendekode setelah konteks bit-tree yang dilambangkan dengan node.

Klaim, yang ditemukan di beberapa sumber, bahwa literal setelah *MATCH dikodekan sebagai XOR dari nilai byte dengan match_byte salah; mereka malah dikodekan hanya sebagai nilai byte mereka, tetapi menggunakan pseudo-bit-tree yang baru saja dijelaskan dan konteks tambahan yang tercantum dalam tabel di bawah ini.

Kelompok variabel probabilitas yang digunakan dalam LZMA adalah:

format LZMA2
Wadah LZMA2 mendukung beberapa proses data LZMA terkompresi dan data tidak terkompresi. Setiap operasi terkompresi LZMA dapat memiliki konfigurasi dan kamus LZMA yang berbeda. Ini meningkatkan kompresi sebagian atau seluruhnya file yang tidak dapat dimampatkan dan memungkinkan kompresi multithreaded dan dekompresi multithreaded dengan memecah file menjadi proses yang dapat dikompresi atau didekompresi secara independen secara paralel. Kritik terhadap perubahan LZMA2 terhadap LZMA termasuk kolom header yang tidak dicakup oleh CRC, dan dekompresi paralel tidak mungkin dilakukan dalam praktiknya.

Header LZMA2 terdiri dari sebuah byte yang menunjukkan ukuran kamus:

• 40 menunjukkan ukuran kamus 4 GB − 1
• Bahkan nilai kurang dari 40 menunjukkan ukuran kamus 2v/2 + 12 byte
• Nilai ganjil kurang dari 40 menunjukkan ukuran kamus 3×2(v − 1)/2 + 11 byte
• Nilai yang lebih tinggi dari 40 tidak valid

Data LZMA2 terdiri dari paket yang dimulai dengan byte kontrol, dengan nilai sebagai berikut:

• 0 menunjukkan akhir dari file
• 1 menunjukkan reset kamus diikuti oleh potongan yang tidak terkompresi
• 2 menunjukkan potongan yang tidak terkompresi tanpa pengaturan ulang kamus
• 3-0x7f adalah nilai yang tidak valid
• 0x80-0xff menunjukkan potongan LZMA, di mana 5 bit terendah digunakan sebagai bit 16-20 dari ukuran yang tidak
• dikompres dikurangi satu, dan bit 5-6 menunjukkan apa yang harus diatur ulang

Bit 5-6 untuk potongan LZMA dapat berupa:

• 0: tidak ada yang disetel ulang
• 1: status diatur ulang
• 2: setel ulang status, setel ulang properti menggunakan byte properti
• 3: setel ulang status, setel ulang properti menggunakan byte properti, setel ulang kamus

Penyetelan ulang status LZMA menyebabkan penyetelan ulang semua status LZMA kecuali kamus, dan khususnya:

Pengkode jangkauan

• Nilai negara
• Jarak terakhir untuk pertandingan berulang
• Semua probabilitas LZMA
• Potongan yang tidak terkompresi terdiri dari:

Nilai big-endian 16-bit yang menyandikan ukuran data minus satu

• Data yang akan disalin kata demi kata ke dalam kamus dan hasilnya
• Potongan LZMA terdiri dari:

Nilai big-endian 16-bit yang menyandikan 16-bit rendah dari ukuran tidak terkompresi minus satu

• Nilai big-endian 16-bit yang menyandikan ukuran terkompresi minus satu
• Sebuah byte properti/lclppb jika bit 6 dalam byte kontrol diatur
• Data terkompresi LZMA, dimulai dengan 5 byte (yang pertama diabaikan) digunakan untuk menginisialisasi range coder
• (yang termasuk dalam ukuran terkompresi)

format xz dan 7z
Format .xz, yang dapat berisi data LZMA2, didokumentasikan di tukaani.org,[10] sedangkan format file .7z, yang dapat berisi data LZMA atau LZMA2, didokumentasikan dalam file 7zformat.txt yang terdapat di LZMA SDK [11]

Detail algoritma kompresi
Mirip dengan situasi format dekompresi, tampaknya tidak ada spesifikasi bahasa alami lengkap dari teknik pengkodean dalam 7-zip atau xz, selain yang dicoba dalam teks berikut.

Deskripsi di bawah ini didasarkan pada XZ untuk pembuat enkode Java oleh Lasse Collin,[12] yang tampaknya paling mudah dibaca di antara beberapa penulisan ulang 7-zip asli menggunakan algoritme yang sama: sekali lagi, mengutip kode sumber sebagai referensi tidaklah ideal , programmer mana pun harus dapat memeriksa klaim di bawah ini dengan beberapa jam kerja.

Encoder rentang
Range encoder tidak dapat membuat pilihan yang menarik, dan dapat dengan mudah dibangun berdasarkan deskripsi decoder.

Inisialisasi dan terminasi tidak sepenuhnya ditentukan; encoder xz menghasilkan 0 sebagai byte pertama yang diabaikan oleh dekompresor, dan mengkodekan batas bawah rentang (yang penting untuk byte terakhir).

Encoder xz menggunakan variabel 33-bit unsigned yang disebut low (biasanya diimplementasikan sebagai integer 64-bit, diinisialisasi ke 0), variabel 32-bit unsigned disebut range (diinisialisasi ke 232 − 1), variabel 8-bit unsigned disebut cache (diinisialisasi ke 0), dan variabel unsigned disebut cache_size yang harus cukup besar untuk menyimpan ukuran yang tidak terkompresi (diinisialisasi ke 1, biasanya diimplementasikan sebagai integer 64-bit).

Variabel cache/cache_size digunakan untuk menangani carry dengan benar, dan mewakili angka yang ditentukan oleh urutan big-endian yang dimulai dengan nilai cache, dan diikuti oleh byte cache_size 0xff, yang telah dipindahkan dari register rendah, tetapi belum ditulis belum, karena bisa bertambah satu karena membawa.

Perhatikan bahwa keluaran byte pertama akan selalu 0 karena fakta bahwa cache dan rendah diinisialisasi ke 0, dan implementasi encoder; dekoder xz mengabaikan byte ini.

Normalisasi berlangsung dengan cara ini:

1. Jika rendah kurang dari ({\displaystyle 2^{32}-2^{24}}{\displaystyle 2^{32}-2^{24}}):
   Keluarkan byte yang disimpan dalam cache ke aliran terkompresi
   Output cache_size − 1 byte dengan nilai 0xff
   Setel cache ke bit 24-31 rendah
   Setel cache_size ke 0
2. Jika rendah lebih besar atau sama dengan {\displaystyle 2^{32}}{\displaystyle 2^{32}}:
   Keluarkan byte yang disimpan dalam cache ditambah satu ke aliran terkompresi
   Output cache_size − 1 byte dengan nilai 0
   Setel cache ke bit 24-31 rendah
   Setel cache_size ke 0
3. Tingkatkan cache_size
4. Atur rendah ke 24 bit terendah dari rendah digeser ke kiri 8 bit
5. Atur rentang ke rentang yang digeser ke kiri sebesar 8 bit

Pengkodean rentang berbasis konteks dari bit menggunakan variabel probabilitas prob menghasilkan dengan cara ini:

1. Jika rentang kurang dari {\displaystyle 2^{24}}{\displaystyle 2^{24}}, lakukan normalisasi
2. Set terikat ke {\displaystyle \lfloor range/2^{11}\rfloor *prob}{\displaystyle \lfloor range/2^{11}\rfloor *prob}
3. Jika menyandikan 0 bit:
   Tetapkan rentang ke terikat
   Tetapkan prob ke {\displaystyle prob+\lfloor 2^{11}-prob\rfloor /2^{5}}{\displaystyle prob+\lfloor 2^{11}-prob\rfloor /2^{5}}
4. Jika tidak (jika menyandikan 1 bit):
   Atur rentang ke rentang − terikat
   Setel rendah ke rendah + terikat
   Tetapkan prob ke {\displaystyle prob-\lfloor prob/2^{5}\rfloor }{\displaystyle prob-\lfloor prob/2^{5}\rfloor }

Pengkodean rentang probabilitas tetap dari bit menghasilkan dengan cara ini:

1. Jika rentang kurang dari {\displaystyle 2^{24}}{\displaystyle 2^{24}}, lakukan normalisasi
2. Tetapkan rentang ke {\displaystyle \lfloor range/2\rfloor }{\displaystyle \lfloor range/2\rfloor }
3. Jika mengkodekan 1 bit:
   Setel kisaran rendah ke rendah +

Pemutusan berlangsung dengan cara ini:

1. Lakukan normalisasi sebanyak 5 kali

Pengkodean bit-tree dilakukan seperti decoding, kecuali bahwa nilai bit diambil dari integer input yang akan dikodekan bukan dari hasil fungsi bit decoding.

Untuk algoritme yang mencoba menghitung pengkodean dengan ukuran pengkodean pasca-rentang terpendek, pembuat enkode juga perlu memberikan perkiraannya.

Struktur data pencarian kamus
Encoder harus dapat dengan cepat menemukan kecocokan dalam kamus. Karena LZMA menggunakan kamus yang sangat besar (berpotensi dalam urutan gigabyte) untuk meningkatkan kompresi, hanya dengan memindai seluruh kamus akan menghasilkan pembuat enkode yang terlalu lambat untuk dapat digunakan secara praktis, sehingga diperlukan struktur data yang canggih untuk mendukung pencarian pencocokan cepat.

Rantai hash
Pendekatan paling sederhana, yang disebut “rantai hash”, diparameterisasi oleh konstanta N yang dapat berupa 2, 3 atau 4, yang biasanya dipilih sehingga 28×N lebih besar atau sama dengan ukuran kamus.

Ini terdiri dari pembuatan, untuk setiap k kurang dari atau sama dengan N, sebuah tabel hash yang diindeks oleh tupel k byte, di mana masing-masing ember berisi posisi terakhir di mana k byte pertama di-hash ke nilai hash yang terkait dengan ember tabel hash itu .

Chaining dicapai dengan array tambahan yang menyimpan, untuk setiap posisi kamus, posisi terakhir yang terlihat sebelumnya yang N byte pertamanya di-hash ke nilai yang sama dari N byte pertama dari posisi yang dimaksud.

Untuk menemukan kecocokan dengan panjang N atau lebih tinggi, pencarian dimulai menggunakan tabel hash berukuran N, dan dilanjutkan menggunakan larik rantai hash; pencarian berhenti setelah sejumlah node rantai hash yang telah ditentukan telah dilalui, atau ketika rantai hash “berputar”, menunjukkan bahwa bagian input yang telah ditimpa dalam kamus telah tercapai.

Kecocokan dengan ukuran kurang dari N malah ditemukan dengan hanya melihat tabel hash yang sesuai, yang berisi kecocokan terbaru, jika ada, atau string yang memiliki nilai hash yang sama; dalam kasus terakhir, pembuat enkode tidak akan dapat menemukan kecocokan. Masalah ini dimitigasi oleh fakta bahwa untuk pencocokan pendek jarak jauh yang menggunakan banyak literal mungkin memerlukan lebih sedikit bit, dan memiliki konflik hash di string terdekat relatif tidak mungkin terjadi; menggunakan tabel hash yang lebih besar atau bahkan tabel pencarian langsung dapat mengurangi masalah dengan biaya tingkat kesalahan cache yang lebih tinggi dan dengan demikian menurunkan kinerja.

Perhatikan bahwa semua kecocokan perlu divalidasi untuk memeriksa bahwa byte sebenarnya cocok saat ini pada kecocokan posisi kamus tertentu, karena mekanisme hashing hanya menjamin bahwa di masa lalu ada karakter hashing ke indeks ember tabel hash (beberapa implementasi bahkan mungkin tidak menjamin itu, karena mereka tidak menginisialisasi struktur data).

LZMA menggunakan rantai Markov, seperti yang tersirat dari “M” pada namanya.

Pohon biner
Pendekatan pohon biner mengikuti pendekatan rantai hash, kecuali bahwa secara logis menggunakan pohon biner, bukan daftar tertaut untuk rantai.

Pohon biner dipertahankan sehingga selalu merupakan pohon pencarian relatif terhadap urutan leksikografi sufiks, dan tumpukan maksimum untuk posisi kamus[13] (dengan kata lain, akar selalu merupakan string terbaru, dan anak tidak dapat ditambahkan baru-baru ini daripada induknya): dengan asumsi semua string diurutkan secara leksikografis, kondisi ini dengan jelas menentukan pohon biner (ini dapat dibuktikan dengan induksi pada ukuran pohon).

Karena string yang akan dicari dan string yang akan disisipkan adalah sama, dimungkinkan untuk melakukan pencarian kamus dan penyisipan (yang memerlukan rotasi pohon) dalam traversal pohon tunggal.

Patricia mencoba
Beberapa pembuat enkode LZMA lama juga mendukung struktur data berdasarkan percobaan Patricia, tetapi dukungan semacam itu telah dibatalkan karena dianggap lebih rendah daripada opsi lainnya.

pembuat enkode LZMA
Pembuat enkode LZMA dapat dengan bebas memutuskan kecocokan mana yang akan dihasilkan, atau apakah akan tetap mengabaikan keberadaan kecocokan dan output literal.

Kemampuan untuk mengingat 4 jarak yang terakhir digunakan berarti bahwa, pada prinsipnya, menggunakan kecocokan dengan jarak yang akan dibutuhkan lagi nanti mungkin optimal secara global meskipun tidak optimal secara lokal, dan sebagai hasilnya, kompresi LZMA optimal mungkin memerlukan pengetahuan tentang seluruh masukan dan mungkin memerlukan algoritme yang terlalu lambat untuk dapat digunakan dalam praktik.

Karena itu, implementasi praktis cenderung menggunakan heuristik non-global.

Encoder xz menggunakan nilai yang disebut nice_len (standarnya adalah 64): ketika ada kecocokan dengan panjang setidaknya nice_len ditemukan, encoder menghentikan pencarian dan mengeluarkannya, dengan panjang pencocokan maksimum.

Encoder cepat
Encoder cepat XZ[14] (berasal dari enkoder cepat 7-zip) adalah enkoder LZMA terpendek di pohon sumber xz.

Cara kerjanya seperti ini:

1. Lakukan pencarian dan penyisipan gabungan dalam struktur data kamus
2. Jika ada jarak berulang yang cocok dengan panjang setidaknya nice_len:
   Keluarkan jarak yang paling sering digunakan dengan paket REP
3. Jika kecocokan ditemukan dengan panjang setidaknya nice_len:
   Keluarkan dengan paket MATCH
4. Atur pertandingan utama menjadi pertandingan terpanjang
5. Lihatlah kecocokan terdekat dari setiap panjang dalam urutan panjang yang menurun, dan hingga tidak ada penggantian yang dapat dilakukan:
   Ganti pertandingan utama dengan pertandingan yang satu karakter lebih pendek, tetapi jaraknya kurang dari 1/128 jarak pertandingan utama saat ini
6. Setel panjang pertandingan utama ke 1 jika pertandingan utama saat ini memiliki panjang 2 dan jarak minimal 128
7. Jika kecocokan berulang ditemukan, dan kecocokan tersebut lebih pendek dengan maksimal 1 karakter dari kecocokan utama:
   Keluarkan kecocokan berulang dengan paket REP
8. Jika kecocokan berulang ditemukan, dan lebih pendek dengan paling banyak 2 karakter dari kecocokan utama, dan jarak kecocokan utama setidaknya 512:
   Keluarkan kecocokan berulang dengan paket REP
9. Jika kecocokan berulang ditemukan, dan lebih pendek dengan paling banyak 3 karakter dari kecocokan utama, dan jarak kecocokan utama setidaknya 32768:
   Keluarkan kecocokan berulang dengan paket REP
10. Jika ukuran kecocokan utama kurang dari 2 (atau tidak ada kecocokan):
    Keluarkan paket LIT
11. Lakukan pencarian kamus untuk byte berikutnya
12. Jika byte berikutnya lebih pendek paling banyak 1 karakter daripada pencocokan utama, dengan jarak kurang dari 1/128 kali jarak pencocokan utama, dan jika panjang pencocokan utama setidaknya 3:
    Keluarkan paket LIT
13. Jika byte berikutnya memiliki kecocokan setidaknya sepanjang kecocokan utama, dan dengan jarak kurang dari kecocokan utama:
    Keluarkan paket LIT
14. Jika byte berikutnya memiliki kecocokan setidaknya satu karakter lebih panjang dari kecocokan utama, dan sedemikian rupa sehingga 1/128 jaraknya kurang atau sama dengan jarak kecocokan utama:
    Keluarkan paket LIT
15. Jika byte berikutnya memiliki kecocokan lebih dari satu karakter lebih lama dari kecocokan utama:
    Keluarkan paket LIT
16. Jika ada pencocokan berulang yang lebih pendek dengan paling banyak 1 karakter daripada pencocokan utama:
    Keluarkan jarak yang paling sering digunakan dengan paket REP
17. Keluarkan kecocokan utama dengan paket MATCH

Encoder biasa
Encoder normal XZ [15] (berasal dari encoder normal 7-zip) adalah encoder LZMA lainnya di pohon sumber xz, yang mengadopsi pendekatan yang lebih canggih yang mencoba meminimalkan ukuran post-range-encoding dari paket yang dihasilkan.

Secara khusus, ini mengkodekan bagian dari input menggunakan hasil dari algoritma pemrograman dinamis, di mana submasalah menemukan pengkodean yang kira-kira optimal (yang memiliki ukuran pengkodean pasca-rentang minimal) dari substring dengan panjang L mulai dari byte yang sedang dikompresi .

Ukuran porsi input yang diproses dalam algoritme pemrograman dinamis ditentukan sebagai maksimum antara pencocokan kamus terpanjang dan pencocokan berulang terpanjang yang ditemukan pada posisi awal (yang dibatasi oleh panjang pencocokan LZMA maksimum, 273); lebih jauh lagi, jika kecocokan yang lebih panjang dari nice_len ditemukan pada titik mana pun dalam rentang yang baru saja ditentukan, algoritme pemrograman dinamis berhenti, solusi untuk submasalah hingga saat itu adalah keluaran, kecocokan berukuran nice_len adalah keluaran, dan pemrograman dinamis baru instance masalah dimulai pada byte setelah kecocokan dihasilkan.

Solusi kandidat subproblem diperbarui secara bertahap dengan pengkodean kandidat, dibangun mengambil solusi untuk substring yang lebih pendek dengan panjang L ‘, diperpanjang dengan semua “ekor” yang mungkin, atau set 1-3 paket dengan batasan tertentu yang menyandikan input pada posisi L’ . Setelah solusi akhir dari submasalah ditemukan, status LZMA dan jarak yang paling jarang digunakan untuknya dihitung, dan kemudian digunakan untuk menghitung ukuran pengkodean pasca-rentang yang sesuai dari ekstensinya.

Pada akhir pengoptimalan pemrograman dinamis, seluruh pengkodean optimal dari substring terpanjang yang dipertimbangkan adalah keluaran, dan pengkodean berlanjut pada byte terkompresi pertama yang belum dikodekan, setelah memperbarui status LZMA dan jarak yang paling jarang digunakan.

Setiap subproblem diperluas dengan urutan paket yang kita sebut “ekor”, yang harus cocok dengan salah satu pola berikut:

Alasan untuk tidak hanya memperluas dengan paket tunggal adalah bahwa submasalah hanya memiliki panjang substring sebagai parameter untuk alasan kinerja dan kompleksitas algoritmik, sementara pendekatan pemrograman dinamis yang optimal juga memerlukan jarak yang terakhir digunakan dan status LZMA sebagai parameter; dengan demikian, memperluas dengan beberapa paket memungkinkan untuk mendekati solusi optimal dengan lebih baik, dan khususnya untuk memanfaatkan paket LONGREP[0] dengan lebih baik.

Data berikut disimpan untuk setiap subproblem (tentu saja, nilai yang disimpan adalah untuk kandidat solusi dengan harga minimum), di mana dengan “ekor” kita mengacu pada paket yang memperluas solusi dari subproblem yang lebih kecil, yang dijelaskan secara langsung berikut ini struktur:

Perhatikan bahwa dalam implementasi XZ untuk Java, anggota optPrev dan backPrev digunakan kembali untuk menyimpan daftar paket tertaut tunggal maju sebagai bagian dari keluaran solusi akhir.

pembuat enkode LZMA2
Encoder XZ LZMA2 memproses input dalam potongan (hingga 2 MB ukuran tidak terkompresi atau ukuran terkompresi 64 KB, mana yang lebih rendah), menyerahkan setiap potongan ke pembuat enkode LZMA, dan kemudian memutuskan apakah akan mengeluarkan potongan LZMA2 LZMA termasuk data yang disandikan , atau untuk mengeluarkan potongan LZMA2 yang tidak terkompresi, tergantung mana yang lebih pendek (LZMA, seperti kompresor lainnya, akan memperluas daripada mengompres beberapa jenis data).

Status LZMA direset hanya di blok pertama, jika pemanggil meminta perubahan properti dan setiap kali potongan terkompresi dikeluarkan. Properti LZMA hanya diubah di blok pertama, atau jika pemanggil meminta perubahan properti. Kamus hanya disetel ulang di blok pertama.

Lapisan penyandian atas
Sebelum pengkodean LZMA2, tergantung pada opsi yang disediakan, xz dapat menerapkan filter BCJ, yang memfilter kode yang dapat dieksekusi untuk mengganti offset relatif dengan yang absolut yang lebih berulang, atau filter delta, yang menggantikan setiap byte dengan perbedaan antara byte dan byte N byte sebelumnya.

Pengkodean paralel dilakukan dengan membagi file dalam potongan-potongan yang didistribusikan ke utas, dan akhirnya masing-masing dikodekan (menggunakan, misalnya, pengkodean blok xz) secara terpisah, menghasilkan pengaturan ulang kamus di antara potongan-potongan dalam file keluaran.

Implementasi referensi 7-Zip
Implementasi LZMA yang diekstrak dari 7-Zip tersedia sebagai LZMA SDK. Itu awalnya berlisensi ganda di bawah GNU LGPL dan Lisensi Publik Umum, dengan pengecualian khusus tambahan untuk binari tertaut, tetapi ditempatkan oleh Igor Pavlov di domain publik pada 2 Desember 2008, dengan rilis versi 4.62

Kompresi LZMA2, yang merupakan versi perbaikan dari LZMA, sekarang menjadi metode kompresi default untuk format .7z, dimulai dengan versi 9.30 pada 26 Oktober 2012.

Pustaka kompresi LZMA sumber terbuka referensi awalnya ditulis dalam C++ tetapi telah dipindahkan ke ANSI C, C#, dan Java.Ada juga binding Python pihak ketiga untuk pustaka C++, serta port LZMA ke Pascal, Go, dan Ada

Implementasi 7-Zip menggunakan beberapa varian rantai hash, pohon biner dan pohon Patricia sebagai dasar algoritma pencarian kamusnya.

Selain LZMA, SDK dan 7-Zip juga mengimplementasikan beberapa filter preprocessing yang dimaksudkan untuk meningkatkan kompresi, mulai dari enkode delta sederhana (untuk gambar) dan BCJ untuk kode yang dapat dieksekusi. Ini juga menyediakan beberapa algoritma kompresi lain yang digunakan dalam 7z.

Kode khusus dekompresi untuk LZMA umumnya dikompilasi menjadi sekitar 5 KB, dan jumlah RAM yang diperlukan selama dekompresi pada prinsipnya ditentukan oleh ukuran jendela geser yang digunakan selama kompresi. Ukuran kode yang kecil dan overhead memori yang relatif rendah, terutama dengan panjang kamus yang lebih kecil, dan kode sumber bebas membuat algoritme dekompresi LZMA sangat cocok untuk aplikasi yang disematkan.

Implementasi lainnya
Selain implementasi referensi 7-Zip, berikut ini mendukung format LZMA.

• xz: implementasi streaming yang berisi alat baris perintah mirip gzip, mendukung LZMA dan LZMA2 dalam format file xz. Itu masuk ke beberapa perangkat lunak dunia mirip Unix dengan kinerja tinggi (dibandingkan dengan bzip2) dan ukuran kecil (dibandingkan dengan gzip). Kernel Linux, sistem dpkg dan RPM berisi kode xz, dan banyak distributor perangkat lunak seperti kernel.org, Debian dan Fedora sekarang menggunakan xz untuk mengompresi rilis mereka.
• lzip: implementasi LZMA lainnya terutama untuk sistem mirip Unix agar bersaing langsung dengan xz. Ini terutama menampilkan format file yang lebih sederhana dan karenanya pemulihan kesalahan lebih mudah.
• ZIPX: ekstensi ke format kompresi ZIP yang dibuat oleh WinZip dimulai dengan versi 12.1. Ia juga dapat menggunakan berbagai metode kompresi lain seperti BZip dan PPMd

LZHAM
LZHAM (LZ, Huffman, Arithmetic, Markov), adalah implementasi mirip LZMA yang memperdagangkan throughput kompresi untuk rasio yang sangat tinggi dan throughput dekompresi yang lebih tinggi. Itu ditempatkan oleh penulisnya di domain publik pada 15 September 2020