Mengapa metode kompresi (lossless) dari banyak gambar png serupa ini tidak efektif?

Saya baru saja menemukan hal berikut: Saya meletakkan beberapa salinan identik gambar png ke dalam folder dan kemudian mencoba untuk mengompresi folder itu dengan metode berikut:

• tar czf folder.tar.gz folder/
• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (yang ini bekerja dengan baik untuk gambar yang identik, namun untuk gambar yang sama, keuntungannya nol)
• zip -r folder.zip folder/

Ketika saya memeriksa ukuran .tar.gz, .tar.xz, .zipsaya menyadari bahwa itu adalah hampir sama dengan salah satu folder/.
Saya mengerti bahwa gambar png itu sendiri mungkin memiliki tingkat kompresi yang tinggi dan karena itu tidak dapat dikompresi lebih lanjut. Namun ketika menggabungkan banyak gambar png yang serupa (dalam hal ini bahkan identik) ke arsip dan kemudian mengompresi arsip saya akan mengharapkan ukuran yang diperlukan berkurang secara nyata. Dalam hal gambar identik, saya harapkan ukuran kira-kira ukuran gambar tunggal.

Lihat bagaimana cara kerja algoritma kompresi. Setidaknya mereka dalam keluarga Lempel-Ziv ( gzip menggunakan LZ77 , ziptampaknya sebagian besar juga , dan xz menggunakan LZMA ) mengompres secara lokal : Persamaan yang terletak jauh satu sama lain tidak dapat diidentifikasi.

Rinciannya berbeda antara metode, tetapi intinya adalah bahwa pada saat algoritma mencapai gambar kedua, sudah "lupa" awal yang pertama. Dan seterusnya.

Anda dapat mencoba dan secara manual mengubah parameter dari metode kompresi; jika ukuran jendela (LZ77) resp. ukuran blok / bongkahan (metode yang lebih baru) setidaknya sebesar dua gambar, Anda mungkin akan melihat kompresi lebih lanjut.

Perhatikan bahwa hal di atas hanya benar-benar berlaku jika Anda memiliki gambar identik atau hampir tidak terkompresi gambar identik . Jika ada perbedaan, gambar yang dikompresi mungkin tidak terlihat sama dalam memori. Saya tidak tahu bagaimana kompresi PNG bekerja; Anda mungkin ingin memeriksa representasi hex dari gambar yang Anda miliki untuk substring bersama secara manual.

Juga perhatikan bahwa bahkan dengan parameter yang diubah dan redundansi untuk dieksploitasi, Anda tidak akan turun ke ukuran satu gambar. Kamus yang lebih besar berarti ukuran kata-kata yang lebih besar, dan bahkan jika dua gambar persis sama, Anda mungkin harus menyandikan yang kedua menggunakan beberapa kata-kata (yang menunjuk ke yang pertama).

Kenapa ini terjadi? Sebenarnya ada dua efek berbeda yang terjadi di sini:

• Setiap file dikompresi secara independen. Beberapa program arsip - termasuk zip - kompres setiap file secara independen, tanpa memori dari satu file ke file lain. Dengan kata lain, setiap file dikompresi secara terpisah, maka file yang dikompresi tersebut disatukan menjadi arsip.

• Ingatan jangka pendek. Beberapa program arsip dapat menggunakan informasi tentang satu file untuk membantu mengompres file berikutnya dengan lebih baik. Mereka secara efektif menyatukan file, lalu mengompres hasilnya. Ini merupakan peningkatan.

  Lihat juga jawaban Nayuki untuk diskusi lebih lanjut tentang ini.

  Namun, ada masalah kedua. Beberapa skema kompresi - termasuk zip, gzip, dan bzip2 - memiliki memori terbatas. Mereka memampatkan data saat itu juga, dan mengingat data 32KB yang lalu, tetapi mereka tidak mengingat apa pun tentang data yang terjadi jauh lebih awal dalam file. Dengan kata lain, mereka tidak dapat menemukan data duplikat jika duplikat terjadi lebih jauh dari 32KB terpisah. Akibatnya, jika file yang identik pendek (lebih pendek dari sekitar 32KB), algoritma kompresi dapat menghapus data yang digandakan, tetapi jika file yang sama panjang, algoritma kompresi disemprot dan menjadi tidak berharga: tidak dapat mendeteksi semua duplikat dalam data Anda. (Bzip mengingat data 900KB yang lalu, bukan 32KB.)

  Semua algoritma kompresi standar memiliki beberapa ukuran memori maksimum, di luar itu mereka gagal mendeteksi pola ... tetapi untuk beberapa, jumlah ini jauh lebih besar daripada yang lain. Untuk Bzip, kira-kira seperti 900KB. Untuk xz, kira-kira 8MB (dengan pengaturan default). Untuk 7z, kira-kira 2GB. 2GB lebih dari cukup besar untuk mengenali duplikat file PNG (yang biasanya jauh lebih kecil dari 2GB). Selain itu, 7z juga mencoba untuk pandai menempatkan file yang cenderung mirip satu sama lain di dalam arsip, untuk membantu kompresor bekerja lebih baik; tar tidak tahu apa-apa tentang itu.

  Lihat juga jawaban Raphael dan jawaban Nayuki untuk penjelasan lebih lanjut tentang efek ini.

Bagaimana ini berlaku untuk pengaturan Anda. Untuk contoh spesifik Anda, Anda bekerja dengan gambar PNG. Gambar PNG sendiri dikompresi, sehingga Anda dapat menganggap setiap file PNG pada dasarnya adalah urutan byte yang tampak acak, tanpa pola atau duplikasi di dalam file tersebut. Tidak ada yang bisa dieksploitasi kompresor, jika terlihat pada gambar PNG tunggal. Jadi, jika Anda mencoba untuk mengompres file PNG tunggal (atau membuat arsip zip / tar / ... yang hanya berisi file PNG tunggal), Anda tidak akan mendapatkan kompresi apa pun.

Sekarang mari kita lihat apa yang terjadi jika Anda mencoba menyimpan banyak salinan dari file PNG yang sama:

• File kecil.Jika file PNG sangat kecil, maka semuanya kecuali zip akan bekerja dengan baik. Zip akan gagal secara spektakuler: ia mengkompres setiap file secara independen, sehingga tidak memiliki peluang untuk mendeteksi redundansi / duplikasi di antara file-file tersebut. Selain itu, ketika mencoba untuk mengompresi setiap file PNG, itu tidak mencapai kompresi; ukuran arsip zip akan sangat besar. Sebaliknya, ukuran arsip tar (apakah dikompresi dengan gzip, bzip2, atau xz) dan arsip 7z akan kecil, karena pada dasarnya menyimpan satu salinan file dan kemudian memperhatikan bahwa yang lainnya semuanya identik - mereka mendapat manfaat dari mempertahankan memori dari satu file ke file lainnya.

• File besar. Jika file PNG besar, maka hanya 7z yang berfungsi dengan baik. Secara khusus, zip terus gagal secara spektakuler. Juga, tar.zip dan tar.bzip2 gagal dengan buruk, karena ukuran file lebih besar dari jendela memori kompresor: karena kompresor melihat salinan file pertama, itu tidak dapat menyusutkan (karena sudah dikompresi) ); pada saat mulai melihat awal dari salinan kedua file, ia sudah lupa urutan byte yang terlihat di awal file pertama dan tidak dapat membuat koneksi bahwa data ini sebenarnya merupakan duplikat.

  Sebaliknya, tar.xz dan 7z terus melakukan yang terbaik dengan banyak salinan file PNG besar. Mereka tidak memiliki batasan "ukuran memori kecil" dan dapat melihat bahwa salinan kedua file identik dengan salinan pertama, jadi tidak perlu menyimpannya untuk yang kedua kalinya.

Apa yang dapat Anda lakukan tentang ini? Gunakan 7z. Ini memiliki banyak heuristik yang akan membantu mendeteksi file yang identik atau serupa dan kompres dengan sangat baik dalam kasus itu. Anda juga dapat melihat lrzip dengan kompresi lzop.

Bagaimana aku tahu? Saya dapat memverifikasi ini dengan mencoba beberapa percobaan dengan 100 salinan file yang berisi byte acak. Saya mencoba 100 salinan file 4KB, 100 salinan file 1MB, dan 100 salinan file 16MB. Inilah yang saya temukan:

Size of file      Size of compressed archive (with 100 copies)
                  zip  tar.gz  tar.bz2  tar.xz    7z
         4KB    414KB     8KB     10KB     5KB    5KB
         1MB    101MB   101MB    101MB     1MB    2MB
        16MB    1.6G    1.6GB    1.6GB   1.6GB  401MB

Seperti yang Anda lihat, zip itu mengerikan, sekecil apa pun file Anda. 7z dan xz keduanya baik jika gambar Anda tidak terlalu besar (tetapi xz akan rapuh dan bergantung pada urutan penempatan gambar dalam arsip, jika Anda memiliki beberapa duplikat dan beberapa non-duplikat yang digabungkan menjadi satu). 7z sangat bagus, bahkan untuk file besar.

Referensi. Ini juga dijelaskan dengan baik dalam banyak posting di Super User. Lihatlah:

• Mengapa kompresi Gzip tidak menghilangkan duplikat data?
• Mengapa Zip dapat mengkompres satu file lebih kecil dari banyak file dengan konten yang sama?
• Mengompresi banyak file besar yang serupa
• Kompres File Mirip Secara Efisien
• Apakah ada program kompresi atau pengarsipan untuk Windows yang juga melakukan deduplikasi?
• Program kompresi file yang lebih efisien untuk banyak file yang identik?

Pertama, perhatikan bahwa format gambar PNG pada dasarnya adalah piksel RGB mentah (dengan beberapa penyaringan cahaya) didorong melalui format kompresi DEFLATE. Secara umum, file terkompresi (PNG, JPEG, MP3, dll.) Tidak akan mendapat manfaat dari dikompres lagi. Jadi untuk maksud praktis, kami dapat memperlakukan file PNG Anda sebagai data acak yang tidak dapat dimampatkan untuk sisa percobaan.

Kedua, perhatikan bahwa format ZIP dan gzip juga menggunakan codec DEFLATE. (Ini akan menjelaskan mengapa zipping versus gzipping satu file pada dasarnya akan menghasilkan ukuran output yang sama.)

Sekarang izinkan saya untuk mengomentari setiap kasus uji secara individual:

• tar czf folder.tar.gz folder/

  Ini membuat file TAR (tidak terkompresi) yang menggabungkan semua file PNG identik Anda (dengan sedikit metadata dan penambahan ditambahkan). Kemudian file tunggal ini dikirim melalui kompresor gzip untuk membuat satu file output terkompresi.

  Sayangnya, format DEFLATE hanya mendukung jendela kamus LZ77 sebesar 32768 byte. Jadi meskipun TAR berisi data berulang, jika file PNG Anda lebih besar dari 32 KiB maka pasti DEFLATE kompresor tidak dapat mengingat data cukup jauh untuk mengambil keuntungan dari fakta bahwa data identik berulang.

  Di sisi lain, jika Anda mencoba kembali pengalaman ini dengan, katakanlah, file PNG 20 KB digandakan 10 kali, maka sangat mungkin Anda akan mendapatkan file gzip hanya sedikit lebih besar dari 20 KB.

• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz

  Ini menciptakan file TAR seperti sebelumnya, dan kemudian menggunakan format xz dan kompresor LZMA / LZMA2. Saya tidak dapat menemukan informasi tentang LZMA dalam situasi ini, tetapi dari 7-Zip untuk Windows saya tahu itu dapat mendukung ukuran jendela kamus besar (misalnya 64 MiB). Jadi ada kemungkinan bahwa Anda menggunakan pengaturan suboptimal, dan bahwa LZMA codec mungkin dapat mengurangi file TAR menjadi hanya ukuran satu file PNG.

• zip -r folder.zip folder/

  Format ZIP tidak mendukung arsip "solid"; artinya, setiap file dikompresi secara independen. Kami mengasumsikan setiap file tidak dapat dimampatkan. Oleh karena itu fakta bahwa setiap file identik tidak dapat dieksploitasi, dan file ZIP akan sebesar gabungan langsung dari semua file.

Masalahnya adalah, skema kompresi (sebagian besar) tidak memiliki pengetahuan tentang data yang Anda miliki. Bahkan jika Anda mendekompres PNG Anda ke bitmap dan mengompresnya di tarball, Anda tidak akan mendapatkan (secara signifikan) hasil yang lebih kecil.

Dalam kasus banyak gambar yang serupa, skema kompresi yang sesuai adalah codec video.

Menggunakan pengkodean lossless Anda harus mencapai hampir hasil kompresi sempurna yang Anda harapkan.

Jika Anda ingin mengujinya, gunakan sesuatu seperti ini:

ffmpeg -i img%03d.png -c:v libx264 -c:v libx264 -profile:v high444 -crf 0 out.mp4

https://trac.ffmpeg.org/wiki/Create%20a%20video%20slideshow%20from%20images

PNG adalah kombinasi dari Filter + LZ77 + Huffman (kombinasi dari LZ77 + Huffman disebut Deflate) dengan urutan:

langkah 1) jika filter berbeda dari Tidak Ada, nilai piksel digantikan oleh perbedaan dari piksel yang berdekatan (untuk lebih jelasnya lihat http://www.libpng.org/pub/png/book/chapter09.html ) . Yang meningkatkan kompresi gambar dengan gradien (jadi ... 4 5 6 7 menjadi ... 1 1 1 1) dan itu dapat membantu di area dengan warna yang sama (... 3 3 3 5 5 5 5 5 menjadi 0 0 0 2 0 0 0 0 0). Secara default filter diaktifkan dalam gambar 24-bit dan dinonaktifkan dalam gambar 8-bit dengan palet.

langkah 2) data dikompres dengan LZ77 yang menggantikan string byte (match) yang diulang dengan tuple yang berisi jarak ke pertandingan dan panjang pertandingan.

langkah 3) hasil langkah 2 dikodekan dengan kode Huffman yang menggantikan simbol panjang tetap dengan kode panjang variabel, semakin sering simbol semakin pendek kode.

Ada beberapa masalah:

Perubahan kecil yang memengaruhi beberapa piksel akan menghasilkan perubahan hasil dari 3 langkah kompresi png:

1) Nilai yang disaring dari piksel yang berdekatan akan berubah (tergantung pada filter yang digunakan). Itu akan memperkuat efek dari perubahan kecil.

2) Perubahan akan berarti bahwa kecocokan dengan area itu akan berbeda. Misalnya mengubah 333333 menjadi 333533 menyebabkan kemunculan 333333 yang lain tidak lagi cocok sehingga akan memilih kecocokan lain menjadi 333333 dengan jarak yang berbeda atau akan memilih kecocokan yang sama tetapi dengan panjang yang lebih pendek dan kemudian kecocokan lainnya untuk 3 byte terakhir. Dengan sendirinya itu akan banyak mengubah hasil.

3) Masalah terbesar adalah pada langkah 3. Kode huffman menggunakan sejumlah variabel bit sehingga bahkan perubahan kecil akan menghasilkan bahwa segala sesuatu yang mengikuti tidak lagi selaras. AFAIK Kebanyakan algoritma kompresi tidak dapat mendeteksi kecocokan yang tidak selaras byte sehingga akan mencegah (atau setidaknya mengurangi banyak) kompresi pada data yang sudah dikompresi yang mengikuti perubahan kecuali kompresor dapat mendeteksi kecocokan yang tidak selaras byte.

Masalah lain sudah dicakup oleh balasan lain:

4) Gzip menggunakan algoritma Deflate yang sama dengan kamus 32KB, jadi jika file png lebih besar dari 32KB, kecocokan tidak akan terdeteksi meskipun mereka identik. Bzip2 lebih baik dalam aspek itu karena menggunakan blok 900 KB. XZ menggunakan LZMA, yang IIRC memiliki kamus 4 MB di tingkat kompresi standar. 5) Format zip tidak menggunakan kompresi padat sehingga tidak akan mengkompres file yang sama atau identik lebih baik.

Mungkin kompresor dari keluarga PAQ atau PPMD ​​akan memampatkan lebih baik tetapi jika Anda perlu mengompres banyak file gambar yang serupa maka Anda dapat mempertimbangkan 3 pendekatan:

1) Simpan gambar tanpa kompresi (dengan PNG -0 atau dalam format tanpa kompresi) dan kompres dengan kompresor dengan kamus besar atau ukuran blok. (LZMA akan bekerja dengan baik)

2) Pilihan lain adalah menyimpan filter tetapi menghapus kompresi Deflate dari PNG. Itu bisa dilakukan misalnya dengan utilitas ( AdvDef ). Lalu Anda kompres PNGs terkompresi yang dihasilkan. Setelah dekompresi, Anda dapat menyimpan PNG yang tidak terkompresi atau mengompresnya lagi dengan AdvDef (tetapi itu akan memakan waktu).

Anda perlu menguji kedua pendekatan untuk melihat kompres mana yang paling banyak.

3) Opsi terakhir adalah mengonversi gambar png dalam video, mengompresnya dengan kompresor video lossless seperti x264 lossless (dengan hati-hati menggunakan format warna yang tepat) dan kemudian mengekstraksi ekstrak frame ke gambar png individu. Itu bisa dilakukan dengan ffmpeg. Anda juga perlu menjaga pemetaan antara nomor bingkai dan nama asli.

Itu akan menjadi pendekatan yang paling kompleks tetapi jika pngs semua bagian dari animasi itu mungkin yang paling efektif. Namun Anda akan memerlukan format video yang mendukung transparansi jika Anda membutuhkannya.

Sunting: Ada juga format MNG yang tidak sering digunakan.

Saat Anda memiliki kumpulan data khusus, Anda menggunakan algoritme khusus, bukan alat multiguna.

Jawabannya adalah bahwa kompresi lossless yang Anda pilih tidak dibuat untuk apa yang Anda lakukan. Noone mengharapkan Anda untuk mengompres gambar yang sama dua kali, dan bahkan jika Anda melakukannya (secara tidak sengaja) memeriksa semua input sebelumnya akan membuat algoritma Anda O (n ^ 2) (mungkin sedikit lebih baik, tetapi pendekatan naif setidaknya akan menjadi n ^ 2).

Sebagian besar program kompresi yang Anda uji dijalankan di O (n), mereka menekankan kecepatan dibandingkan rasio kompresi yang optimal. Tidak seorang pun ingin menjalankan komputernya selama 5 jam hanya untuk menghemat beberapa mb, terutama hari-hari ini. Untuk input yang lebih besar, apa pun di atas O (n) menjadi masalah runtime.

Masalah lainnya adalah ram. Anda tidak dapat mengakses setiap bagian dari input Anda kapan saja, ketika inputnya cukup besar. Bahkan mengabaikan hal ini, kebanyakan orang tidak mau menyerahkan seluruh ram atau cpu mereka hanya untuk mengompres sesuatu.

Jika Anda memiliki pola dalam file yang ingin Anda kompres, Anda harus melakukan operasi manuel padanya, menulis kompresi Anda sendiri atau berpotensi menggunakan "arsip" -tipe-kompresi (nano). Kompresi untuk penyimpanan jangka panjang, itu terlalu lambat untuk penggunaan sehari-hari.

Pilihan lain yang berpotensi adalah kompresi video tanpa kehilangan.

Format file PNG sudah menggunakan algoritma kompresi DEFLATE secara internal. Ini adalah algoritma yang sama seperti yang digunakan oleh xz, gzip, dan zip - hanya dalam beberapa variasi. tar.gzdan dan tar.xzmemanfaatkan kesamaan antara file, yang ziptidak.

Jadi, pada kenyataannya, Anda melakukan kompresi DEFLATE di atas file terkompresi DEFLATE - inilah mengapa file tersebut mempertahankan ukuran hampir aslinya.

The bzip2Program (juga algoritma terkait) lebih baik ketika datang ke (hampir) file identik.

# for i in $(seq 4); do cp test.png test$i.png; done
# tar -cjf archive.tar.bz2 *.png
# ls -l
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test1.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test2.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test3.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test4.png
-rw-r--r-- 1 abcde users  68115 15. Jul 08:47 archive.tar.bz2