Kompres File Serupa Secara Efisien

11

Saya sering memiliki kebutuhan untuk mengkompres file yang sangat mirip satu sama lain.

Saat ini saya menggunakan 7Zip, yang memampatkan file 16GB ke 1,2GB dalam waktu sekitar 35 menit menggunakan 8 core dengan pengaturan Ultra.

Tampaknya bagi saya banyak waktu yang dihabiskan menghitung kamus untuk digunakan untuk kompresi. Karena file-file tersebut sangat mirip, kamus yang sebenarnya digunakan kemungkinan juga mirip.

Apakah ada alat kompresi berbasis Windows (7Zip dengan opsi yang tidak saya sadari, atau alat lain) yang dapat menyimpan kamus dan menggunakan kembali kamus yang disimpan itu untuk file selanjutnya?

Apakah ada cara yang lebih baik untuk mendekati masalah mempertahankan rasio kompresi yang serupa dengan yang saya miliki, sementara mengompres secara signifikan lebih cepat?

Eric J.
sumber

Jawaban:

5

The Lempel-Ziv-Welch (LZW) kompresi algoritma secara inheren komputasi intensif, dengan mayoritas pekerjaan itu sendiri menjadi benar-benar komputasi kamus. Ini secara harfiah cara LZW bekerja.

Algoritme itu sendiri menambahkan satu entri kamus baru untuk setiap "simbol" berikutnya yang dipindai, dan dengan demikian selama setiap iterasi tunggal, entri baru ditambahkan ke kamus. Akibatnya, kamus menjadi salinan file terkompresi, dan dengan demikian sebenarnya satu - satunya kompresi LZW menghabiskan waktu komputasi yang signifikan di tempat pertama.


Jika Anda menggunakan sesuatu seperti pengkodean Huffman , penggunaan kembali kamus memang dimungkinkan (dengan mengorbankan tingkat kompresi / ukuran yang mungkin kurang optimal). Namun, sebagian besar algoritma & alat kompresi modern menggunakan algoritma LZW untuk efisiensi dan kecepatan (kompresi Huffman akan membutuhkan dua lintasan data [satu untuk menghasilkan pohon Huffman / tabel, yang lain untuk benar-benar memampatkan data], sedangkan LZW dapat diselesaikan dalam satu pass).

Penerobosan
sumber
1
Dengan Huffman dan kamus yang telah ditentukan, apakah hanya satu pass diperlukan? Apakah ada alat Huffman yang tersedia di luar rak yang mendukung kamus yang disimpan?
Eric J.
@EricJ. ya, dengan kamus yang sudah ditentukan itu akan menjadi single-pass encoding. Saya tidak tahu ada perangkat lunak yang bisa melakukan ini, walaupun saya secara pribadi telah menulis program yang melakukannya. Walaupun saya belum mencobanya, alat ini sepertinya bisa melakukan hal itu. Namun, perlu diketahui bahwa (sekali lagi, tidak seperti LZW) untuk mendekode bitstream yang dikodekan Huffman, Anda masih memerlukan kamus asli untuk mendekompres data.
Terobosan
Berdasarkan usia alat itu, saya kira itu adalah single-threaded. Saya kira menggunakan 1 inti daripada 8 akan mengimbangi manfaat apa pun ke kamus tetap :-( Memiliki kamus yang tersedia di ujung yang lain layak dalam skenario saya (mentransfer file besar antara pusat data).
Eric J.
2

Berbeda dengan algoritma DEFLATE, LZMA 7-Zip menggunakan kompresi solid secara default, yang memanfaatkan redundansi antar file. Ini akan berfungsi dengan pengaturan default selama file cukup kecil.

Dengan pengaturan default 2 GB untuk ukuran Solid Block , file 16 GB sebenarnya dikompresi sebagai 8 potongan terpisah.

Seperti yang sudah dikatakan @Breakthorugh, kamus dibuat dengan cepat. Anda dapat memverifikasi ini secara empiris dengan mengatur ukuran Blok Padat ke Padat (kompres semua file sekaligus) dan Non-padat (kompres setiap file secara terpisah).

Meningkatkan ukuran Blok Padat sebenarnya akan menghasilkan pelambatan, tetapi dapat menghasilkan rasio kompresi yang jauh lebih baik. Misalnya, mengompresi dua file yang identik akan menghasilkan arsip hampir dua kali lebih besar dengan kompresi non-padat.

Dennis
sumber
1
Dalam kasus saya, saya kompres file yang sama satu per satu, pada kesempatan yang berbeda. Hanya ada satu file 16GB-ish dalam arsip yang diberikan.
Eric J.
Ah, baiklah. Saya salah menafsirkan itu. Apakah arsip lama dihapus saat yang baru dibuat? Jika tidak, apakah bisa menyimpan beberapa file dalam satu arsip? Itu tidak akan membantu dengan kecepatan kompresi, tetapi tergantung pada seberapa mirip file sebenarnya, mungkin membantu dengan rasio.
Dennis
1
Tidak apa-apa, tidak. Memperbarui arsip padat membutuhkan lebih banyak waktu, tetapi tidak menghasilkan kompresi yang lebih baik.
Dennis