Kompresi data dijelaskan

Setiap halaman web yang Anda muat, setiap berkas ZIP, dan setiap gambar PNG telah dikompresi: diperkecil tanpa kehilangan satu bit pun, lalu dibongkar lagi setibanya di tujuan. Metode di baliknya ternyata sangat sederhana. Metode-metode itu mencari hal yang berulang, dan mengatakan “sama seperti sebelumnya” alih-alih mengulanginya. Seberapa jauh gagasan itu bisa dibawa, dan di mana ia berhenti, adalah salah satu kisah paling elegan dalam ilmu komputer.

Sebaris teks yang bagian-bagian berulangnya diganti dengan panah yang menunjuk kembali ke kemunculan pertamanya, di samping batang yang menunjukkan ukuran asli dan ukuran terkompresi
Sebaris teks yang bagian-bagian berulangnya diganti dengan panah yang menunjuk kembali ke kemunculan pertamanya, di samping batang yang menunjukkan ukuran asli dan ukuran terkompresi

Lossless dan lossy

Kompresi ada dua jenis. Kompresi lossless mengembalikan data asli dengan persis, hal yang mutlak perlu untuk teks, program, spreadsheet, dan apa pun yang satu bit salahnya saja sudah berakibat. Kompresi lossy, yang dipakai untuk foto, musik, dan video, membuang detail yang hampir tidak dirasakan orang dan mencapai ukuran yang jauh lebih kecil, tetapi data aslinya hilang untuk selamanya. Halaman ini dan demonstratornya membahas kompresi lossless, yang bekerja dengan menemukan dan membuang redundansi: bagian-bagian data yang sebenarnya bisa diprediksi.

Run-length encoding

Metode paling sederhana mengganti deret simbol yang identik dengan jumlah dan simbolnya: dua belas piksel putih menjadi 12W. Mesin faks, format bitmap awal, dan format gambar PCX memakainya, karena halaman hasil pindaian dan gambar sederhana penuh dengan deret panjang. Pada teks biasa metode ini tidak berguna, bahkan merugikan: deret jarang muncul, dan menulis hitungan untuk setiap huruf membuat ukurannya dua kali lipat. Run-length encoding masih hidup di dalam metode lain, untuk deret nol yang tersisa setelah transformasi pertama.

LZ77: menunjuk ke belakang

Pada tahun 1977 Abraham Lempel dan Jacob Ziv, dua peneliti di Technion di Israel, menerbitkan sebuah metode yang mengubah bidang ini. Encoder menyimpan jendela berisi teks yang baru saja diprosesnya. Jika karakter berikutnya sudah pernah muncul di jendela itu, ia menulis sepasang angka: seberapa jauh ke belakang salinan sebelumnya dimulai dan berapa panjangnya. Jika tidak, ia menulis karakter itu sendiri. Decoder sama sekali tidak memerlukan kamus, hanya teks yang sudah dibangunnya kembali. Sebuah referensi bahkan boleh tumpang tindih dengan teks yang dihasilkannya, sehingga deret 100 huruf identik menjadi satu huruf dan satu referensi.

Abraham Lempel, yang bersama Jacob Ziv di Technion pada 1977 menerbitkan metode jendela dan rujukan yang kini dikenal sebagai LZ77.
Abraham Lempel, yang bersama Jacob Ziv di Technion pada 1977 menerbitkan metode jendela dan rujukan yang kini dikenal sebagai LZ77.

LZW: mempelajari kamus

Metode kedua Lempel dan Ziv, LZ78, membangun kamus alih-alih melihat ke belakang dalam sebuah jendela. Penyempurnaan oleh Terry Welch pada tahun 1984, LZW, dimulai dengan semua 256 nilai byte dan, pada setiap langkah, mengirimkan nomor string terpanjang yang sudah dikenalnya lalu menambahkan string itu beserta karakter berikutnya sebagai entri baru. Decoder membangun kembali kamus yang sama hanya dari nomor-nomor itu. LZW cepat dan sederhana, dan dipakai dalam perintah compress di Unix, format gambar GIF, dan berkas TIFF, hingga paten atasnya memicu sengketa panjang pada tahun 1990-an.

Deflate, ZIP, dan selanjutnya

Metode deflate karya Phil Katz, yang diperkenalkan bersama PKZIP 2 pada tahun 1993, menggabungkan LZ77 dengan pengodean Huffman: setelah menemukan pengulangan, ia memberi literal, panjang, dan jarak yang paling umum kode bit terpendek. Deflate dipakai dalam ZIP, gzip, gambar PNG, dan kompresi halaman web, dan inilah metode yang diukur demonstrator dengan kompresor bawaan browser. Metode yang lebih baru seperti Zstandard, Brotli, dan xz memakai jendela yang lebih besar, pencocokan yang lebih cerdas, dan pengodean entropi yang lebih presisi, serta memampatkan berkas biasa 10 hingga 30% lebih jauh.

Mengapa tidak semuanya bisa mengecil

Tidak ada metode yang dapat membuat setiap berkas lebih kecil. Ada 2ⁿ berkas berukuran n bit, tetapi hanya 2ⁿ − 1 berkas yang lebih pendek dari itu, sehingga jika sebuah metode memperkecil semuanya, dua berkas akan berakhir sama dan tidak mungkin keduanya dipulihkan: inilah prinsip sarang merpati. Karena itu setiap kompresor memperbesar sebagian masukan, biasanya data yang tampak acak seperti berkas terenkripsi, berkas yang sudah dikompresi, dan derau. Hal ini sekaligus menjadi uji keacakan: data yang tidak dapat diperkecil oleh kompresor mana pun tampak acak.

Batas entropi

Claude Shannon menunjukkan pada tahun 1948 bahwa entropi sebuah sumber adalah rata-rata jumlah bit per simbol terkecil yang mungkin bagi kode lossless apa pun. Jika dihitung huruf demi huruf, teks bahasa Inggris memiliki entropi sekitar 4 bit per huruf, separuh dari 8 bit tempat ia disimpan. Metode yang memakai konteks, seperti LZ77, berada di bawah angka per huruf itu pada teks yang berulang-ulang, karena satu referensi mewakili seluruh potongan teks sekaligus. Kompresor modern terbaik, yang memprediksi setiap huruf dari semua yang mendahuluinya, menurunkan bahasa Inggris hingga di bawah 2 bit per huruf.

Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.
Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.

Jelajahi sendiri

Buka demonstrator kompresi untuk menjalankan LZ77, LZW, dan run-length encoding pada sebuah paragraf, lagu dengan refrein, sebaris piksel, tabel data, huruf acak atau DNA, atau pada teks Anda sendiri. Klik referensi LZ77 mana pun untuk melihat apa yang disalinnya, saksikan kamus LZW bertambah, dan bandingkan semua metode dengan ZIP dan batas entropi.

Pertanyaan yang sering diajukan

Apa arti rasio kompresi 3 : 1?

Artinya data asli tiga kali lebih besar daripada versi terkompresinya, sehingga berkas terkompresi memakan sepertiga ruang dan menghemat dua pertiga. Teks biasanya mencapai 2 : 1 hingga 4 : 1 dengan ZIP; data dengan banyak pengulangan, seperti berkas log, sering jauh lebih tinggi.

Mengapa mengompresi berkas ZIP sekali lagi tidak membantu?

Proses pertama sudah membuang pengulangan, dan hasilnya tampak hampir acak. Proses kedua tidak menemukan apa pun untuk dirujuk kembali dan hanya menambahkan overhead-nya sendiri, sehingga ukuran berkas tetap sama atau sedikit bertambah.

Mengapa jendela LZ77 yang lebih besar lebih baik?

Jendela yang lebih besar memungkinkan encoder menemukan pengulangan yang letaknya lebih jauh ke belakang, seperti refrein yang kembali setelah beberapa bait. Harganya, setiap jarak membutuhkan lebih banyak bit untuk ditulis dan pencarian memakan waktu lebih lama; itulah sebabnya deflate berhenti di 32 KB sementara metode yang lebih baru mengizinkan hingga hitungan megabyte.

Apakah kompresi sama dengan enkripsi?

Tidak. Kompresi membuat data lebih kecil dan siapa pun dapat membalikkannya; enkripsi membuat data tidak terbaca tanpa kunci. Keduanya sering digabungkan, dan dalam hal itu data harus dikompresi lebih dulu: data terenkripsi tampak acak dan tidak dapat dikompresi lagi.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka demonstrator kompresi