Kompresi Data
Kompresi data
dilakukan untuk mereduksi ukuran data atau file.
Dengan melakukan kompresi atau pemadatan data maka ukuran file atau data akan lebih kecil sehingga dapat mengurangi waktu
transmisi sewaktu data dikirim dan tidak banyak banyak menghabiskan ruang media
penyimpan.
2.10.1 Teori
Kompresi Data
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.
Gambar
2.11 Claude E. Shannon
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.
