Bagaimana cara kerja kompresi file?

Jadi, saya menyadari hari ini saya menerima kompresi file begitu saja. Kemampuan untuk menggabungkan beberapa file menjadi satu, dan membuatnya lebih kecil daripada yang lain, adalah sesuatu yang saya terima sebagai fakta, tetapi bagaimana cara kerjanya?

Saya memiliki pengetahuan terbatas tentang itu yang mencakup sesuatu yang harus dilakukan dengan mengganti semua entri duplikat dengan pointer, untuk menyusut seperti itu, tetapi di luar itu saya cukup mengerti!

Karena saya selalu terbuka untuk pengetahuan baru, seperti yang saya bayangkan kebanyakan dari kita di sini, saya pikir saya akan bertanya. Jadi, SuperUser, bagaimana kompresi sebenarnya bekerja?

Kompresi lossless

Kompresi lossless adalah di mana tidak ada data yang hilang. Segala sesuatu yang dimasukkan dapat diambil dengan sempurna. Ini berfungsi baik untuk file teks atau biner di mana kesalahan terkecil akan terlihat.

Kompresi file berfungsi dengan mengambil file dan memindai pola, dan menerjemahkan pola-pola itu ke dalam hal lain yang membutuhkan lebih sedikit ruang.

Misalnya "AAAAAAAA" dapat diubah menjadi "8A".

Memang itu bukan cara kerjanya karena Anda memiliki masalah bagaimana jika "8A" ada di plaintext. Anda akan mengompres file dan itu akan salah. Tempat yang baik untuk memulai adalah Wikipedia atau Algoritma Kompresi Data LZW .

Ada beberapa kode psuedo sederhana untuk disalin di bawah ini:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

Semua kompresi menggunakan kamus pencarian yang digunakan untuk kompres dan dekompresi file. Semakin besar kamus, semakin banyak yang bisa Anda kompres, meskipun Anda mengalami Law of Diminishing Returns .

Perlu dicatat juga bahwa kompresi tidak selalu menghasilkan file yang lebih kecil. Ada situasi (dengan file kecil, atau saat mengompresi data acak ) bahwa Anda tidak akan mendapatkan file yang lebih kecil setelah kompresi. Ada beberapa tantangan menyenangkan terkait dengan kemampuan untuk mengompresi data acak.

Kompresi "Lossy"

Di atas sebagian besar berkaitan dengan kompresi lossless . Jenis kompresi lain yang digunakan dalam aplikasi video / audio seperti MP3, JPG, dan h.264 adalah contoh kompresi lossy .

Kompresi lossy bekerja dengan membuang data yang paling tidak mungkin diperhatikan. Dalam audio ini terdengar sekitar 30.000 Hrz dan di bawah 100 Hrz, bersama dengan berbagai hal lainnya. Dalam gambar (statis) ia menghapus berbagai hal dan menggabungkan piksel bersama-sama, bersama dengan membuang data.

Kompresi lossy adalah bentuk transformasi coding . Ini mengeluarkan data rata-rata untuk mengurangi ukuran keseluruhan. Misalnya blok 10 piksel dalam suatu gambar, semua warna yang sedikit berbeda dapat digabungkan menjadi satu warna dan dengan demikian dikompresi.

Dalam kompresi video, sering kali instruksi akan ditempatkan hanya redraw piksel yang telah berubah sejak frame terakhir, atau bingkai kunci .

Kompresi bekerja dengan menemukan pola dalam data, kemudian mengganti pola-pola ini dengan pola yang lebih kecil khusus. Dekompresi adalah kebalikannya: temukan pola khusus, dan gantilah dengan pola yang lebih besar yang mereka wakili. Mengetahui pola apa yang mungkin terjadi adalah penting; misalnya, pola yang ditemukan dalam teks mungkin sangat berbeda dari yang ditemukan dalam gambar. Beberapa teknik kompresi bersifat lossy; mereka tidak menjamin ekspansi akan memulihkan input dengan tepat. Ini biasanya baik untuk data analog, seperti musik dan gambar, jika kerugiannya cukup kecil. Tetapi data seperti teks harus dikompres dengan teknik lossless.

Penting untuk menyadari bahwa tidak mungkin untuk memampatkan, tanpa kehilangan, data acak bahkan dengan sedikit pun. Pertimbangkan file dengan N bit data biner. Ada 2 ^ N file yang mungkin. Jika Anda mengkompres salah satu file ini dengan satu bit, sehingga file yang dikompresi berukuran N-1 bit, hanya ada 2 ^ (N-1) kemungkinan representasi terkompresi. Dengan kata lain, setiap file terkompresi yang mungkin harus mewakili lebih dari satu file terkompresi yang mungkin. Tanpa representasi terkompresi yang unik, algoritma dekompresi tidak dapat menjamin dekompresi lossless.