1. Prinsip Sarang Merpati: Mengapa Tidak Ada Kompresor Universal yang Bisa Mengecilkan Semua Berkas

Saat kita setiap hari menggunakan zip, gzip, zstd, 7z, atau PNG untuk menyusutkan dokumen, kode sumber, atau citra menjadi sepersekian dari ukuran aslinya dan saat diekstrak kembali utuh tanpa kehilangan satu bit pun (kompresi nirrugi / lossless), muncul sebuah pertanyaan intuitif: jika program kompresi mampu memperkecil berkas, mengapa kita tidak mengompresi ulang berkas .zip tersebut sepuluh kali berturut-turut hingga film atau basis data raksasa menyusut menjadi 1 byte saja?

Jawabannya tegas: itu mustahil secara matematis. Pembuktiannya bahkan tidak memerlukan teori informasi tingkat lanjut, melainkan cukup dengan Prinsip Sarang Merpati (Pigeonhole Principle) dari kombinatorika dasar.

Misalkan $E: \{0,1\}^* \to \{0,1\}^*$ adalah fungsi pengodean nirrugi dan $D: \{0,1\}^* \to \{0,1\}^*$ adalah fungsi pendekodeannya. Agar setiap berkas masukan $x$ dapat dipulihkan secara eksak ($D(E(x)) = x$), pemetaan $E$ wajib bersifat injektif (satu-ke-satu): sebab jika dua berkas berbeda $x_1 \ne x_2$ menghasilkan rangkaian bit terkompresi yang sama $y = E(x_1) = E(x_2)$, dekoder tidak akan pernah tahu apakah harus mengembalikan $x_1$ atau $x_2$!

Terdapat tepat $2^N$ kemungkinan berkas biner dengan panjang $N$ bit. Sebaliknya, jumlah total seluruh untai biner yang panjangnya строго lebih pendek daripada $N$ bit (yakni panjang $0$ hingga $N-1$) hanyalah:

Karena terdapat $2^N$ berkas masukan (“merpati”) tetapi hanya $2^N - 1$ untai yang lebih pendek (“sarang”), setiap algoritma kompresi nirrugi yang memperkecil setidaknya satu berkas WAJIB memperbesar (memekarkan) berkas lainnya! Lebih jauh lagi, proporsi berkas sepanjang $N$ bit yang dapat diperkecil minimal sebanyak $c$ bit dibatasi oleh:

Hampir semua untai biner acak tidak dapat dikompresi sama sekali. Kompresor kita bekerja sangat efektif setiap hari karena teks manusia, kode program, dan citra alami menempati subhimpunan yang sangat kecil, terstruktur, dan berentropi rendah di dalam $\{0,1\}^N$.

2. Teorema Pengodean Sumber Shannon dan Entropi: Batas Fisik Absolut

Pada tahun 1948, Claude E. Shannon menetapkan batas fundamental kompresi data dalam «A Mathematical Theory of Communication». Untuk sumber diskrit tanpa memori dengan alfabet $\mathcal{A} = \{s_1, \dots, s_m\}$ dan distribusi probabilitas $P = (p_1, \dots, p_m)$, informasi-diri (Surprisal) dari simbol $s_i$ beserta nilai harapannya, yaitu entropi Shannon $H(X)$, didefinisikan sebagai:

Setiap kode bebas-prefiks (instan) dengan panjang kata kode $\ell_1, \dots, \ell_m$ harus memenuhi ketaksamaan Kraft-McMillan:

Dengan memanfaatkan sifat non-negatif divergensi Kullback-Leibler $D_{\text{KL}}(P \,\|\, Q) \ge 0$ untuk $q_i = 2^{-\ell_i}/Z$ ($Z = \sum 2^{-\ell_i} \le 1$), diperoleh Teorema Pengodean Sumber Nirderau Shannon untuk panjang rata-rata $L = \sum_{i=1}^m p_i \ell_i$:

  flowchart TD
    A["Aliran Data Mentah (Teks / Citra / Biner)"] --> B["Tahap 1: Transformasi & Pemodelan Kamus (BWT / LZ77)"]
    B --> C["Distribusi Probabilitas P(s) Simbol & Pasangan (jarak, panjang)"]
    C --> D["Tahap 2: Pengodean Entropi Statistik (Huffman / Aritmetika / ANS)"]
    D --> E["Aliran Bit Padat Mendekati Batas Shannon N·H(X)"]

3. Tiga Generasi Pengodean Entropi: Huffman, Pengodean Aritmetika, dan ANS

3.1 Pengodean Huffman (1952): Pohon Prefiks Optimal Berpanjang Bilangan Bulat

Algoritma greedy karya David A. Huffman membangun pohon bebas-prefiks optimal dalam waktu $O(m \log m)$ dengan menggabungkan dua simpul berprobabilitas terkecil secara berulang. Kelemahan strukturalnya adalah setiap kata kode harus memiliki panjang bilangan bulat ($\ell_i \ge 1$ bit): simbol dengan probabilitas $p_1 = 0,99$ hanya membawa $-\log_2(0,99) \approx 0,0145\,\text{bit}$ informasi, tetapi tetap menghabiskan minimal $1\,\text{bit}$ penuh.

3.2 Pengodean Aritmetika (Arithmetic / Range Coding): Bit Pecahan

Pengodean aritmetika (Rissanen, Pasco, Witten dkk.) menembus batas bilangan bulat dengan memetakan seluruh rangkaian pesan $x_1 x_2 \dots x_N$ ke dalam satu sub-interval tunggal $[L_{\text{low}}, H_{\text{high}}) \subset [0, 1)$ yang lebar akhirnya $\Delta = \prod_{t=1}^N P(x_t)$ hanya membutuhkan $\lceil -\log_2 \Delta \rceil + 1 \approx N \cdot H(X)$ bit, menghasilkan bit pecahan per simbol dengan konsekuensi komputasi perkalian yang lebih lambat.

3.3 Asymmetric Numeral Systems (ANS, Jarek Duda 2009–2014)

Ditemukan oleh fisikawan dan ilmuwan komputer Polandia Jarek Duda, Asymmetric Numeral Systems (tANS dan rANS) menyatukan rasio kompresi optimal pengodean aritmetika dengan kecepatan tabel pencarian (lookup table) pengodean Huffman. Saat menyandikan simbol $s$ berprobabilitas $p_s$ ke dalam bilangan bulat keadaan $x \in \mathbb{N}$, keadaan diperbaruiตาม:

Saat ini ANS menjadi mesin utama di balik Zstandard (zstd) milik Meta, LZFSE milik Apple, dan JPEG XL milik Google.

4. Kompresi Kamus dan Transformasi: LZ77, DEFLATE, BWT, dan “Kompresi adalah Prediksi”

Untuk memanfaatkan pengulangan untai dan konteks urutan, kompresor modern memadukan pemodelan kamus dengan pengode entropi:

• LZ77 (Lempel & Ziv, 1977): mengganti untai berulang di dalam jendela geser (sliding window) dengan penunjuk balik (distance, length). Dipadukan dengan Huffman menghasilkan DEFLATE (gzip, zip, PNG); dipadukan dengan ANS menghasilkan Zstandard (zstd).
• Transformasi Burrows-Wheeler (BWT, 1994, bzip2): mengurutkan seluruh rotasi siklik blok data secara leksikografis dan mengambil kolom terakhir $L$, mengelompokkan karakter dengan konteks serupa agar mudah dikompresi oleh Move-To-Front (MTF) dan Run-Length Encoding (RLE).

  flowchart TD
    A["Aliran Byte Masukan"] --> B["Pencarian Kecocokan Terpanjang di Jendela Geser (LZ77)"]
    B --> C{"Panjang Kecocokan >= 3?"}
    C -- "Ya" --> D["Keluarkan Penunjuk Balik (distance, length)"]
    C -- "Tidak" --> E["Keluarkan Byte Literal Asli (Literal)"]
    D --> F["Pengodean Entropi via Huffman (DEFLATE) atau ANS (Zstandard)"]
    E --> F

Pada makna matematis terdalamnya, kompresi sepenuhnya setara dengan prediksi: model probabilistik apa pun (termasuk model bahasa besar Transformer) yang meminimalkan entropi silang $-\sum \log_2 P_\theta(x_t \mid x_{