Teori Kompresi Data

Claude E. Shannon

Dalam makalahnya di tahun 1948, “A Mathematical Theory of Communication”, Claude E. Shannon merumuskan teori kompresi data. Shannon membuktikan adanya batas dasar (fundamental limit) pada kompresi data jenis lossless. Batas ini, disebut dengan entropy rate dan dinyatakan dengan simbol H.  Nilai eksak dari H bergantung pada informasi data sumber,  lebih terperinci lagi, tergantung pada statistikal alami dari data sumber. Adalah mungkin untuk mengkompresi data sumber dalam suatu bentuk lossless, dengan laju kompresi (compression rate) mendekati H. Perhitungan secara matematis memungkinkan ini dilakukan lebih baik dari nilai H.
Shannon juga mengembangkan teori mengenai kompresi data lossy. Ini lebih dikenal sebagai rate-distortion theory. Pada kompresi data lossy,  proses dekompresi data tidak menghasilkan data yang sama persis dengan data aslinya. Selain itu, jumlah distorsi atau nilai D dapat ditoleransi. Shannon menunjukkan bahwa, untuk data sumber (dengan semua properti statistikal yang diketahui) dengan memberikan pengukuran distorsi, terdapat sebuah fungsi R(D) yang disebut dengan rate-distortion function. Pada teori ini dikemukakan jika D bersifat toleransi terhadap jumlah distorsi, maka R(D) adalah kemungkinan terbaik dari laju kompresi.
Ketika kompresi lossless (berarti tidak terdapat distorsi atau D = 0), kemungkinan laju kompresi terbaik adalah R(0) = H (untuk sumber alphabet yang terbatas). Dengan kata lain, laju kompresi terbaik yang mungkin adalah entropy rate. Dalam pengertian ini, teori rate-distortion adalah suatu penyamarataan dari teori kompresi data lossless, dimana dimulai dari tidak ada distorsi (D = 0) hingga terdapat beberapa distorsi (D > 0).
Teori kompresi data lossless dan teori rate-distortion dikenal secara kolektif sebagai teori pengkodean sumber (source coding theory). Teori pengkodean sumber menyatakan batas fundamental pada unjuk kerja dari seluruh algoritma kompresi data. Teori tersebut sendiri tidak dinyatakan secara tepat bagaimana merancang dan mengimplementasikan algoritma tersebut. Bagaimana pun juga algoritma tersebut menyediakan beberapa petunjuk dan panduan untuk memperoleh unjuk kerja yang optimal. Dalam bagian ini, akan dijelaskan bagaimana Shannon membuat model dari sumber informasi dalam istilah yang disebut dengan proses acak (random process).  Di bagian selanjutnya akan dijelaskan mengenai teorema pengkodean sumber lossless Shannon, dan teori Shannon mengenai rate-distortion. Latar belakang mengenai teori probabilitas diperlukan untuk menjelaskan teori tersebut.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s