Setelah menonton drama HBO "Silicon Valley", saya selalu tertarik dengan algoritma kompresi. Richard Hendricks dan algoritma kompresi tengahnya di dalamnya tentu saja palsu, tetapi setelah Google keras, saya menemukan bahwa ada algoritma kompresi yang jenius dalam kehidupan nyata.
Yann Collet menemukan algoritma kompresi LZ4 pada tahun 2011. Tentu saja, algoritma LZ4 tidak sehebat mid out, tetapi dikenal dengan kecepatan kompresinya yang tak terkalahkan dan kecepatan dekompresi yang lebih cepat ketika tingkat kompresi tertentu dapat dijamin.
Saya tidak akan membahas secara rinci di sini tentang evaluasi kecepatan kompresinya, jika Anda tertarik, Anda dapat membaca artikel perbandingan ini:Login hyperlink terlihat.
Juga dilampirkan adalah alamat github LZ4:Login hyperlink terlihat.
Artikel ini berfokus pada penjelasan prinsip algoritma kompresi LZ4. Seorang dewa agung menulis penjelasan tentang algoritma LZ4 sebelumnya:Login hyperlink terlihat.Tetapi ketika saya belajar sebelumnya, saya merasa bahwa artikel ini tidak terlalu ramah bagi pemula, jadi saya memulai artikel lain untuk pemula seperti saya.
Jika Anda menyimpulkannya dalam satu kalimat, LZ4 adalah LZ77 yang menyimpan kamus dengan tabel hash ukuran 16k dan menyederhanakan pengambilan.
LZ4 adalah algoritme kompresi lossless yang menawarkan kecepatan kompresi > 500 MB/s per core, yang dapat diskalakan dengan CPU multi-core. Ini memiliki dekoder yang sangat cepat dengan kecepatan beberapa GB/s per inti, seringkali mencapai batas kecepatan RAM pada sistem multi-core.
Kecepatan dapat disesuaikan secara dinamis, memilih faktor "akselerasi" yang memperdagangkan rasio kompresi untuk kecepatan yang lebih cepat. Di sisi lain, LZ4_HC turunan kompresi tinggi juga disediakan untuk meningkatkan kompresi dengan mengorbankan waktu CPU. Semua versi memiliki kecepatan dekompresi yang sama.
Jadi apa itu LZ77?
Kompresi dan prinsip LZ77
LZ77 adalah algoritma yang menerapkan kamus untuk kompresi. Dalam istilah awam, ini adalah membiarkan program mengamati (lihat kamus) apakah data yang saat ini terlihat diduplikasi dengan yang sebelumnya, dan jika demikian, kami menyimpan jarak (offset) dan panjang bidang duplikat untuk menggantikan bidang duplikat dan mengompres data.
referensiLogin hyperlink terlihat.
Untuk serangkaian huruf A A B C B B A B C, ketika A kedua dibaca, program menyimpan (1,1) (1 digit dari yang sebelumnya, panjang 1), dan demikian pula, ketika B kedua dibaca, program menyimpan (2,1) (jarak 2, panjang 1).
Tetapi jika string lebih panjang dan program mencatat data ke dalam kamus sepanjang waktu, pencarian bidang duplikat menjadi sangat memakan waktu, karena dalam kasus terburuk program melewati seluruh kamus dengan setiap huruf baru yang dibaca. LZ77 menggunakan metode jendela geser untuk mengatasi masalah ini.
Mirip dengan titik awal TCP menggunakan jendela geser, jendela geser dapat mengecilkan area cache untuk menghindari pemrosesan terlalu banyak data yang di-cache pada saat yang bersamaan. Di LZ77, kamus tidak bertambah sepanjang waktu, tetapi membuang karakter pertama yang ditambahkan ke kamus ketika melebihi ukuran maksimum yang ditentukan oleh kamus, untuk memastikan bahwa ukuran kamus selalu dipertahankan pada ukuran maksimum yang ditentukan.
Misalkan panjang kamus adalah 3
| Kamus |
| Sebuah | A B C B B A B C
Keluaran (0,0,A)
| A A | B C B B A B C
Keluaran(1,1)
| A B | C B B A B C
Keluaran (0,0,B)
Sebuah | A B C | B B A B C
Keluaran (0,0,C)
A A | B C B | B A B C
Keluaran(2,1)
Bagian lain dari jendela geser adalah cache yang akan dicari (lihat ke depan buffer tidak memiliki terjemahan resmi). Cache yang akan dicari adalah bagian yang tidak terkompresi dari panjang yang paling dekat dengan kamus. Algoritma LZ77 akan cocok dengan string terpanjang di bagian karakter ini yang sama dengan kamus. Contoh sebelumnya dapat dianggap sebagai buffer look ahead dari 1.
Misalkan panjang kamus adalah 5 dan ukuran cache yang akan dicari adalah 3
| Kamus | Lihat ke depan buffer |
Sebuah | A B C B B | A B C |
Keluaran(5,3)
String terpanjang yang cocok adalah ABC
Proses kompresi lengkap:
Misalkan panjang kamus adalah 5 dan ukuran cache yang akan dicari adalah 3
| Kamus | Lihat ke depan buffer |
| A B | C B B A B C
Keluaran (0,0,A)
| Sebuah | A B C | B B A B C
Keluaran(1,1)
| A A | B C B | B A B C
Keluaran (0,0,B)
| A B | C B B | A B C
Keluaran (0,0,C)
| A A B C | B B A | B C
Keluaran(2,1)
| A A B C B | B A B | C
Keluaran(1,1)
Sebuah | A B C B B | A B C |
Keluaran(5,3)
A A B C | B B A B C | 。。。 |
Tidak perlu menyimpan kamus dalam file output kompresor, karena program dekompresi mengembalikan kamus dengan mencocokkan unit output.
Proses dekompresi
Salah satu keuntungan besar dari algoritma LZ77 adalah sangat cepat untuk didekompresi.
Jika satuan pencocokan pertama adalah (0,0,A), maka A adalah output.
Unit pencocokan kedua adalah (1,1), yang menyalin bit sebelumnya dalam string output, dan mengeluarkan A jika panjang salinan adalah 1.
。。。
Jika unit pencocokan terakhir adalah (5,3), maka lihat kembali 5 bit dalam string output salinan, dan jika panjang salinan adalah 3, maka keluaran A, B, C.
Bagian yang paling memakan waktu dari kompresi algoritma LZ77 adalah menemukan karakter pencocokan terpanjang dalam cache untuk dicari di kamus. Jika kamus dan cache yang akan dicari terlalu pendek, peluang untuk menemukan kecocokan tipis. Oleh karena itu, LZ4 telah mengubah algoritma pencocokan untuk LZ77.
Pertama, kamus algoritma LZ4 adalah tabel hash. Kunci dalam kamus adalah string 4 byte, setiap kunci hanya sesuai dengan satu slot, dan nilai dalam slot adalah posisi string ini.
Alih-alih mencari cache, LZ4 membaca empat byte sekaligus dari file input, dan kemudian mencari slot yang sesuai dengan string dalam tabel hash, yang selanjutnya disebut sebagai string saat ini.
Jika Anda telah mencapai 12 karakter terakhir, masukkan langsung ke dalam file output.
Jika tidak ada nilai yang ditetapkan di slot, itu berarti empat byte muncul untuk pertama kalinya, tambahkan empat byte dan posisi ini ke tabel hash, dan lanjutkan pencarian.
Jika ada tugas di slot, itu berarti kita telah menemukan nilai yang cocok.
Jika nilai dalam slot ditambah ukuran jendela penggeser < posisi karakter saat ini, maka posisi pencocokan melebihi ukuran blok, dan program memperbarui nilai dalam slot hash ke posisi string saat ini.
LZ4 akan memeriksa apakah ada konflik hash. Jika 4 byte di slot tidak sama dengan string saat ini, pasti ada konflik hash. xxhash penulis sendiri juga dikenal karena efisiensinya, tetapi konflik tidak dapat dihindari. Jika terjadi konflik, program juga memperbarui nilai di slot hash ke posisi string saat ini
Terakhir, kami dapat mengonfirmasi bahwa kecocokan valid, dan program akan terus melihat apakah karakter berikutnya dalam string yang cocok adalah sama. Terakhir, salin semua karakter dari akhir kecocokan valid sebelumnya ke awal kecocokan valid ini ke file terkompresi, dan tambahkan urutan pencocokan yang valid ini.
Collet memanggil unit pencocokan yang dikeluarkan oleh urutan LZ4, dan mereka membentuk file terkompresi LZ4. Rinciannya adalah sebagai berikut:
Token ini panjangnya 1 byte, dengan 4 kata pertama menjadi panjang harfiah dan 4 kata terakhir menjadi panjang kecocokan. Seperti disebutkan sebelumnya, semua karakter dari akhir kecocokan valid sebelumnya hingga awal kecocokan valid ini akan disalin ke file terkompresi, file yang tidak terkompresi ini bersifat harfiah, dan panjangnya adalah panjang harfiah.
Secara harfiah diikuti oleh penyimpangan. Seperti dalam LZ77, penyimpangan dan panjang pencocokan mengacu pada panjang string saat ini dari kecocokannya, dan panjang pencocokan mengacu pada panjang panjang pencocokan string saat ini dengan string yang sama dalam kamus. Dalam dekompresi adalah melewatinya untuk menemukan string yang akan disalin dan panjang yang akan disalin. Besarnya penyimpangan diperbaiki.
Pada gambar, panjang literal+ dan panjang pencocokan+ adalah jika panjang literal atau panjang pertandingan 4 kata dalam token tidak cukup, mereka akan terus meningkat di posisi yang sesuai. 4 kata dapat mewakili 0-15, dan jika ada lagi, tambahkan satu byte, yaitu tambahkan 255 ke ukuran sampai byte kurang dari 255. Dalam panjang yang cocok, 0 mewakili 4 byte.
12 byte terakhir berakhir secara harfiah karena disalin secara langsung.
Mari kita lihat kodenya (python lebih abstrak)
Ringkasan Setelah mengatakan semua ini, saya masih belum merangkum mengapa LZ4 begitu cepat. Pertama-tama mari kita bandingkan pencarian kamus antara LZ77 dan LZ4. LZ77 asli mencari kamus dengan mencari kecocokan terbesar dalam cache yang akan dicari dan di kamus. Ini adalah masalah menemukan string identik terbesar dalam dua string. Jika kita tidak menggunakan pemrograman dinamis, maka paling buruk kita harus mempertimbangkan semua substring dari satu string dan kemudian mencocokkannya dalam string lain. Jika ×kita menggunakan pemrograman dinamis, kita akan menggunakan tabel untuk menahan pertandingan terpanjang dalam dinamika, yang hanya akan memungkinkan kita untuk menyelesaikan pertandingan dalam kasus O(m*n). Dan, itu hanya untuk sepasang cache pencarian dan kamus. Dalam kasus terburuk, jika tidak ada kecocokan, maka LZ77 harus menghitung (panjang seluruh file - panjang cache yang akan dicari) sebanyak masalah pencocokan tersebut. LZ4 sebenarnya menggunakan tingkat pemrograman dinamis yang lebih besar: ia menyimpan 4 byte dan posisinya dalam tabel hash, dan kemudian mencocokkan 4 byte data baru setiap kali hanya untuk melihat apakah nilai dalam tabel hash valid. Setelah menemukan nilai pencocokan yang valid, jika Anda melihat data tindak lanjut dari dua set nilai yang cocok, Anda juga dapat menemukan kecocokan terpanjangnya. Karena setiap kunci tabel hash LZ4 hanya sesuai dengan 1 slot, pekerjaan menemukan dan menambahkan dan memodifikasi tabel hash hanya membutuhkan O(1). Jika lebih banyak kecocokan ditemukan setelah pencocokan, lebih banyak perbandingan grup diperlukan, tetapi dalam total waktu, perbandingan ini akan menggantikan lebih banyak waktu untuk mencari tabel hash, sehingga total waktu algoritma LZ4 hanya O(n). Saya harus mengagumi keindahan algoritma Collet! Untuk membuat algoritme lebih cepat, Collet mengatur ukuran tabel hash default menjadi 16k, yang disarankan untuk tidak melebihi 32k, sehingga dapat dimasukkan ke dalam cache L1 dari hampir semua CPU (Intel). Semua orang tahu bahwa kecepatan dan rasio memori cache CPU L1 sangat berbeda, jadi tidak mengherankan jika LZ4 terbang cepat, belum lagi persamaan hash yang digunakan dalam tabel hash LZ4 masih xxhash tercepat. Tentu saja, desain seperti itu memiliki kekurangan. Semakin kecil tabel hash, semakin sedikit kunci yang dimilikinya. Ini berarti bahwa lebih banyak konflik hash akan terjadi, yang tidak dapat dihindari. Dan lebih banyak tabrakan hash berarti lebih sedikit kecocokan. Dan tabel hash yang lebih kecil juga berarti jendela geser yang lebih kecil, yang berarti lebih banyak kecocokan akan dibuang karena terlalu jauh. Lebih sedikit kecocokan mewakili rasio kompresi yang lebih kecil, itulah sebabnya LZ4 memiliki rasio kompresi yang kurang menonjol. Melihat ke Depan LZ4 memiliki berbagai skenario aplikasi. Sama seperti middle out yang digunakan dalam VR di Silicon Valley, LZ4 dapat meningkatkan pemanfaatan bandwidth dengan menghadirkan lebih sedikit IO dengan biaya latensi yang sangat rendah karena kecepatan kompresinya yang sangat cepat. Ada juga sedikit dugaan, jika ada CPU dengan cache yang lebih besar di level 1, dapatkah LZ4 meningkatkan rasio kompresi tanpa mengorbankan kecepatan?
Asli:Login hyperlink terlihat. |
Diposting pada 03/01/2022 13.54.23
|
|
|
|
