Entropi dijelaskan

Pada tahun 1948, seorang insinyur di Bell Labs, Claude Shannon, mengajukan pertanyaan yang belum pernah dirumuskan secara tepat oleh siapa pun: berapa banyak informasi yang terkandung dalam sebuah pesan? Jawabannya adalah sebuah angka, diukur dalam bit, yang tidak bergantung pada makna pesan, melainkan pada seberapa mengejutkannya pesan itu. Angka itu, entropi, menetapkan batas setiap program kompresi, setiap jalur jaringan, dan setiap perangkat penyimpanan, serta menjelaskan mengapa sebagian teks menyusut menjadi sebagian kecil ukurannya sementara yang lain sama sekali tidak bisa dimampatkan.

Batang probabilitas huruf yang memudar dari yang umum ke yang langka, dengan kurva entropi yang turun seiring makin banyak konteks diketahui
Batang probabilitas huruf yang memudar dari yang umum ke yang langka, dengan kurva entropi yang turun seiring makin banyak konteks diketahui

Informasi adalah kejutan

Gagasan Shannon adalah mengukur informasi dari seberapa tak terduga sebuah pesan, bukan dari maknanya. Jika Anda sudah tahu jawabannya, mendengarnya tidak memberi tahu apa-apa; jika jawabannya bisa salah satu dari seribu hal, ia memberi tahu banyak. Pesan yang menunjuk satu dari dua kemungkinan yang sama mungkin membawa satu bit. Satu dari empat membutuhkan dua bit, satu dari delapan tiga bit, dan secara umum satu dari N kemungkinan yang sama mungkin membutuhkan log₂ N bit. Karena itu simbol yang muncul dengan probabilitas p membawa −log₂ p bit: makin langka simbol itu, makin banyak yang disampaikannya.

Rumus Shannon

Entropi adalah rata-rata informasi per simbol: H = −Σ p log₂ p, dijumlahkan atas setiap simbol dengan probabilitasnya p. Untuk koin yang adil, H adalah 1 bit. Untuk koin yang jatuh pada sisi gambar 90% dari waktu, nilainya hanya 0,47 bit, karena hasilnya biasanya tidak mengejutkan. Entropi paling besar ketika semua simbol sama mungkin, log₂ n bit untuk n simbol, dan nol ketika satu simbol sudah pasti. Shannon memilih nama ini atas saran John von Neumann, karena rumus yang sama muncul dalam fisika, tempat entropi mengukur ketidakteraturan.

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.

Batas kompresi

Teorema pengodean sumber Shannon menyatakan bahwa tidak ada kode lossless yang dapat memakai lebih sedikit bit per simbol, secara rata-rata, daripada entropi sumbernya, dan bahwa kode dapat mendekatinya sedekat yang diinginkan. Pengodean Huffman, yang ditemukan David Huffman pada tahun 1952 saat masih mahasiswa, memberi simbol yang sering muncul kode pendek dan simbol yang langka kode panjang, dan mencapai selisih kurang dari satu bit per simbol dari entropi; pengodean aritmetika bahkan lebih dekat lagi. Jadi entropi bukan sekadar deskripsi, melainkan batas mutlak: berkas berisi byte acak, dengan entropi 8 bit per byte, sama sekali tidak dapat dikompresi.

David Huffman, difoto saat menjadi profesor di UC Santa Cruz. Sebagai mahasiswa pascasarjana MIT pada tahun 1951, ia menemukan kode optimalnya dalam makalah untuk mata kuliah Robert Fano.
David Huffman, difoto saat menjadi profesor di UC Santa Cruz. Sebagai mahasiswa pascasarjana MIT pada tahun 1951, ia menemukan kode optimalnya dalam makalah untuk mata kuliah Robert Fano.

Konteks dan redundansi

Huruf-huruf dalam teks tidak saling bebas. Dalam bahasa Inggris, setelah Q datang U, setelah titik datang huruf kapital, dan kata yang diawali INFORMA hampir pasti berlanjut dengan TION. Memperhitungkan simbol-simbol sebelumnya menghasilkan entropi bersyarat, yang lebih rendah daripada entropi simbol yang dihitung satu per satu. Selisihnya adalah redundansi: bagian pesan yang sebenarnya bisa diprediksi. Program kompresi seperti ZIP, yang menggunakan metode deflate, mencari untaian yang berulang dan menggantinya dengan rujukan pendek, sedangkan kompresor modern memprediksi setiap simbol dari konteksnya.

Berapa banyak informasi dalam bahasa Inggris?

Jika dihitung huruf demi huruf dengan frekuensi bahasa Inggris, satu huruf membawa sekitar 4,1 bit, dibandingkan 4,7 bit untuk huruf yang dipilih secara acak. Pada tahun 1951 Shannon melangkah lebih jauh: ia menunjukkan awal sebuah teks kepada orang-orang dan meminta mereka menebak huruf berikutnya, sambil menghitung berapa tebakan yang mereka perlukan. Dari jawaban mereka ia memperkirakan bahwa bahasa Inggris hanya membawa sekitar 0,6 hingga 1,3 bit per huruf. Dengan kata lain, kira-kira tiga perempat bahasa Inggris tertulis adalah redundansi, itulah sebabnya teks yang kehilangan sebagian hurufnya biasanya masih bisa dibaca.

Keacakan dan kata sandi

Entropi juga mengukur ketidakterdugaan, dan di situlah keamanan bergantung. Kunci atau kata sandi yang dipilih secara seragam dari N kemungkinan memiliki entropi log₂ N bit, dan penyerang rata-rata harus mencoba sekitar separuhnya. Kata sandi acak 12 huruf dari 26 huruf kecil memiliki sekitar 56 bit; kata yang umum memiliki jauh lebih sedikit, sepanjang apa pun kata itu. Pembangkit bilangan acak diuji dengan memeriksa bahwa keluarannya memiliki entropi penuh sebuah sumber acak, dan sistem operasi mengumpulkan entropi dari derau pewaktuan untuk memberinya benih.

Di mana entropi muncul

Entropi menentukan berapa bit yang dibutuhkan panggilan telepon, foto, atau aliran video, dan seberapa dekat modem atau koneksi Wi-Fi dapat mencapai kapasitas kanalnya. Ahli biologi menggunakannya untuk mengukur informasi dalam DNA, tempat empat basa masing-masing dapat membawa paling banyak 2 bit, serta keanekaragaman sebuah ekosistem. Dalam pembelajaran mesin, pohon keputusan memilih pertanyaan yang paling banyak menurunkan entropi, dan fungsi kerugian entropi silang melatih sebagian besar jaringan saraf. Ahli bahasa membandingkan bahasa-bahasa berdasarkan entropinya per karakter dan per kata.

Jelajahi

Buka kalkulator entropi untuk mengukur teks apa pun per karakter, kata, atau byte. Bandingkan sebuah paragraf dengan huruf, bit, digit, dan DNA acak, lihat kejutan setiap simbol, berapa banyak informasi yang dikandung teks dibandingkan ukuran tersimpannya, dan bagaimana bit per simbol turun seiring makin banyak konteks diketahui, berdampingan dengan hasil nyata ZIP.

Pertanyaan yang sering diajukan

Mengapa entropi diukur dalam bit?

Karena Shannon menggunakan logaritma berbasis 2, sehingga satu pilihan ya-atau-tidak di antara dua opsi yang setara dihitung sebagai satu satuan. Dengan logaritma natural satuannya adalah nat, sekitar 1,44 bit, dan dengan basis 10 satuannya hartley, sekitar 3,32 bit; fisikawan dan sebagian ahli statistik memakai satuan-satuan itu.

Dapatkah sebuah teks memiliki entropi lebih besar daripada log₂ ukuran alfabetnya?

Tidak. Dengan n simbol berbeda, entropi paling banyak log₂ n bit per simbol, yang hanya tercapai bila semuanya sama seringnya. Setiap ketidakseimbangan, dan setiap keterdugaan dari konteks, menurunkannya.

Apakah entropi dalam teori informasi sama dengan entropi dalam fisika?

Bentuk rumusnya sama: Boltzmann dan Gibbs menulis entropi fisika sebagai jumlah atas probabilitas keadaan mikroskopis sebuah sistem. Maknanya pun berkaitan, karena keduanya mengukur seberapa banyak yang tidak Anda ketahui, dan fisikawan kemudian menunjukkan bahwa menghapus satu bit informasi pasti melepaskan sedikit panas.

Mengapa mengompresi berkas yang sudah dikompresi tidak membantu?

Kompresor yang baik menghilangkan sebagian besar redundansi, sehingga keluarannya mendekati acak, dengan entropi hampir 8 bit per byte. Tidak ada lagi yang bisa dihilangkan, dan mengompresinya lagi biasanya justru membuatnya sedikit lebih besar karena overhead kompresor itu sendiri.

Siap mencobanya?

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

Buka kalkulator entropi