Cara Kerja Kompresi Data Lossless | Majalah Quanta

Dengan lebih dari 9 miliar gigabyte informasi yang beredar di internet setiap hari, para peneliti terus mencari cara baru untuk mengompresi data menjadi paket yang lebih kecil. Teknik mutakhir fokus pada pendekatan lossy, yang mencapai kompresi dengan sengaja "kehilangan" informasi dari transmisi. Google, misalnya, baru-baru ini meluncurkan strategi yang merugikan di mana komputer pengirim menjatuhkan detail dari sebuah gambar dan komputer penerima menggunakan kecerdasan buatan untuk menebak bagian yang hilang. Bahkan Netflix menggunakan pendekatan lossy, menurunkan kualitas video setiap kali perusahaan mendeteksi bahwa pengguna menonton di perangkat beresolusi rendah.

Sangat sedikit penelitian, sebaliknya, saat ini sedang dilakukan pada strategi lossless, di mana transmisi dibuat lebih kecil, tetapi tidak ada substansi yang dikorbankan. Alasannya? Pendekatan lossless sudah sangat efisien. Mereka menggerakkan segalanya mulai dari standar gambar JPEG hingga utilitas perangkat lunak PKZip yang ada di mana-mana. Dan itu semua karena seorang mahasiswa pascasarjana yang hanya mencari jalan keluar dari ujian akhir yang sulit.

Tujuh puluh tahun yang lalu, seorang profesor Institut Teknologi Massachusetts bernama Robert Fano menawarkan pilihan kepada siswa di kelas teori informasinya: Mengikuti ujian akhir tradisional, atau meningkatkan algoritme terkemuka untuk kompresi data. Fano mungkin atau mungkin tidak memberi tahu murid-muridnya bahwa dia adalah penulis algoritme yang ada, atau bahwa dia telah mencari perbaikan selama bertahun-tahun. Apa yang kita ketahui adalah bahwa Fano menawarkan tantangan berikut kepada murid-muridnya.

Pertimbangkan pesan yang terdiri dari huruf, angka, dan tanda baca. Cara langsung untuk menyandikan pesan semacam itu adalah dengan menetapkan setiap karakter nomor biner yang unik. Misalnya, komputer mungkin mewakili huruf A sebagai 01000001 dan tanda seru sebagai 00100001. Ini menghasilkan kode yang mudah diuraikan — setiap delapan digit, atau bit, sesuai dengan satu karakter unik — tetapi sangat tidak efisien, karena angka yang sama digit biner digunakan untuk entri umum dan tidak umum. Pendekatan yang lebih baik adalah sesuatu seperti kode Morse, di mana huruf E yang sering diwakili hanya dengan satu titik, sedangkan Q yang kurang umum membutuhkan tanda hubung-dash-titik-dash yang lebih panjang dan lebih melelahkan.

Namun kode Morse juga tidak efisien. Tentu, beberapa kode pendek dan lainnya panjang. Tetapi karena panjang kode berbeda-beda, pesan dalam kode Morse tidak dapat dipahami kecuali jika menyertakan periode hening singkat di antara setiap transmisi karakter. Memang, tanpa jeda yang mahal itu, penerima tidak akan memiliki cara untuk membedakan pesan Morse dash dot-dash-dot dot-dot dash dot (“trite”) dari dash dot-dash-dot dot-dot-dash dot (“true” ).

Fano telah memecahkan bagian masalah ini. Dia menyadari bahwa dia dapat menggunakan kode dengan panjang yang berbeda-beda tanpa memerlukan ruang yang mahal, selama dia tidak pernah menggunakan pola digit yang sama baik sebagai kode lengkap maupun awal kode lainnya. Misalnya, jika huruf S sangat umum dalam pesan tertentu sehingga Fano memberinya kode yang sangat pendek 01, maka tidak ada huruf lain dalam pesan itu yang akan disandikan dengan apa pun yang dimulai dengan 01; kode seperti 010, 011 atau 0101 semuanya akan dilarang. Hasilnya, pesan yang dikodekan dapat dibaca dari kiri ke kanan, tanpa ambiguitas. Misalnya huruf S diberi angka 01, huruf A diberi angka 000, huruf M diberi angka 001, dan huruf L diberi angka 1, tiba-tiba pesan 0100100011 bisa langsung diterjemahkan menjadi kata “kecil” padahal L diwakili satu digit, S dua digit, dan huruf lainnya masing-masing tiga digit.

Untuk benar-benar menentukan kodenya, Fano membuat pohon biner, menempatkan setiap huruf yang diperlukan di ujung cabang visual. Kode setiap huruf kemudian ditentukan oleh jalur dari atas ke bawah. Jika jalur bercabang ke kiri, Fano menambahkan 0; cabang kanan mendapat 1. Struktur pohon memudahkan Fano untuk menghindari tumpang tindih yang tidak diinginkan: Begitu Fano meletakkan huruf di pohon, cabang itu akan berakhir, artinya tidak ada kode di masa mendatang yang dapat dimulai dengan cara yang sama.

Untuk memutuskan surat mana yang akan dikirim ke mana, Fano dapat menguji secara mendalam setiap pola yang mungkin untuk efisiensi maksimum, tetapi itu tidak praktis. Jadi alih-alih dia mengembangkan perkiraan: Untuk setiap pesan, dia akan mengatur huruf yang relevan berdasarkan frekuensi dan kemudian menetapkan huruf ke cabang sehingga huruf di sebelah kiri dalam setiap pasangan cabang yang diberikan digunakan dalam pesan kira-kira sama banyaknya dengan huruf di sebelah kanan. Dengan cara ini, karakter yang sering digunakan akan berakhir di cabang yang lebih pendek dan kurang padat. Sejumlah kecil huruf frekuensi tinggi akan selalu mengimbangi sejumlah besar huruf frekuensi rendah.

Hasilnya adalah kompresi yang sangat efektif. Tapi itu hanya perkiraan; strategi kompresi yang lebih baik harus ada. Maka Fano menantang murid-muridnya untuk menemukannya.

Fano telah membangun pohonnya dari atas ke bawah, menjaga kesimetrisan sebanyak mungkin di antara cabang-cabang yang berpasangan. Muridnya David Huffman membalik proses itu, membangun jenis pohon yang sama tetapi dari bawah ke atas. Wawasan Huffman adalah bahwa, apa pun yang terjadi, dalam kode yang efisien, dua karakter yang paling tidak umum harus memiliki dua kode terpanjang. Jadi Huffman mengidentifikasi dua karakter yang paling tidak umum, mengelompokkannya sebagai pasangan bercabang, dan kemudian mengulangi prosesnya, kali ini mencari dua entri yang paling tidak umum dari antara karakter yang tersisa dan pasangan yang baru saja dibuatnya.

Pertimbangkan pesan di mana pendekatan Fano terputus-putus. Di "ruang sekolah", O muncul empat kali, dan S/C/H/L/R/M masing-masing muncul sekali. Pendekatan penyeimbangan Fano dimulai dengan menugaskan O dan satu huruf lainnya ke cabang kiri, dengan lima penggunaan total dari huruf-huruf tersebut menyeimbangkan lima kemunculan huruf yang tersisa. Pesan yang dihasilkan membutuhkan 27 bit.

Huffman, sebaliknya, memulai dengan dua huruf yang tidak umum — katakanlah, R dan M — dan mengelompokkannya, memperlakukan pasangan itu seperti satu huruf.

Bagan frekuensinya yang diperbarui kemudian memberinya empat pilihan: O yang muncul empat kali, simpul RM gabungan baru yang secara fungsional digunakan dua kali, dan satu huruf S, C, H, dan L. Huffman sekali lagi memilih dua opsi yang paling tidak umum, cocok (katakanlah) H dengan L.

Bagan diperbarui lagi: O masih memiliki bobot 4, RM dan HL sekarang masing-masing memiliki bobot 2, dan huruf S dan C berdiri sendiri. Huffman melanjutkan dari sana, di setiap langkah mengelompokkan dua opsi yang paling jarang muncul dan kemudian memperbarui pohon dan bagan frekuensi.

Pada akhirnya, "ruang sekolah" menjadi 11101111110000110110000101, memangkas sedikit pendekatan top-down Fano.

Satu bit mungkin tidak terdengar banyak, tetapi penghematan kecil pun tumbuh sangat besar ketika diskalakan hingga miliaran gigabyte.

Memang, pendekatan Huffman ternyata sangat kuat sehingga, hari ini, hampir setiap strategi kompresi lossless menggunakan wawasan Huffman secara keseluruhan atau sebagian. Perlu PKZip untuk mengompresi dokumen Word? Langkah pertama melibatkan strategi pintar lainnya untuk mengidentifikasi pengulangan dan dengan demikian mengompresi ukuran pesan, tetapi langkah kedua adalah mengambil pesan terkompresi yang dihasilkan dan menjalankannya melalui proses Huffman. Menyimpan gambar sebagai JPEG? Komputer Anda pertama-tama menerjemahkan gambar menjadi representasi berbasis teks dan kemudian, sekali lagi, menggunakan pengkodean Huffman untuk mengompres teks tersebut.

Lumayan untuk proyek yang awalnya dimotivasi oleh keinginan mahasiswa pascasarjana untuk melewatkan ujian akhir.