Pemodelan Sumber (Source Modeling)

Bayangkan bila kita pergi ke perpustakaan dimana perpustakaan tersebut mempunyai pilihan buku-buku yang banyak, katakanlah terdapat 100 juta buku dalam perpustakaan tersebut. Tiap buku dalam perpustakaan ini sangat tebal, sebagai contoh tiap buku mempunyai 100 juta karakter (atau huruf). Ketika anda pergi ke perpustakaan tersebut, mengambil sebuah buku secara acak dan meminjamnya. Buku yang dipilih tersebut merupakan informasi sumber yang akan dikompresi. Buku yang terkompresi tersebut disimpan pada zip disk untuk dibawa pulang, atau ditransmisi secara langsung melalui internet ke rumah anda ataupun bagaimana kasusnya.

Secara matematis buku yang dipilih tersebut didenotasikan sebagai:

X = (X₁, X₂, X₃, X₄, …)

Dimana X merepresentasikan seluruh buku, dan X₁ merepresentasikan karakter pertama dari buku tersebut, X₂ merepresentasikan karakter kedua, dan seterusnya. Meskipun pada kenyataannya panjang karakter dalam buku tersebut terbatas, secara matematis diasumsikan mempunyai panjang karakter yang tidak terbatas. Alasannya adalah buku tersebut terlalu tebal dan dapat dibayangkan jumlah karakternya terlalu banyak. Untuk menyederhanakan hal tersebut, misalkan diasumsi semua karakter dalam buku tersebut terdiri atas huruf kecil (‘a’ hingga ‘z’) atau SPACE. Sumber alphabet misalkan A didefinisikan merupakan kumpulan dari 27 kemungkinan nilai dari tiap karakter:

Sekarang jika seorang yang ingin merancang suatu algoritma kompresi maka sangat sulit baginya untuk mengetahui buku yang mana yang akan dipilih. Orang tersebut hanya mengetahui bahwa seseorang akan memilih sebuah buku dari perpustakaan tersebut. Dengan cara pandangnya, karakter-karakter dalam buku merupakan  (Xi, i = 1, 2 , …) merupakan variabel acak yang diambil dari nilai alphabet A. Keseluruhan buku, X merupakan urutan tak berhingga dari variabel acak, makanya X merupakan suatu proses acak. Ada beberapa cara untuk menyatakan model statistik dari buku tersebut:

A.        Zero-Order Model. Tiap karakter distatistik secara bebas dari semua karakter dan 27 kemungkinan nilai dalam alphabet A dinyatakan sama seperti yang muncul. Jika model tersebut akurat, maka cara tipikal untuk membuka sebuah buku adalah seperti berikut ini (semua contoh berasal dari paper Shannon “A Mathematical Theory of Communication“ di tahun 1948)

xfoml rxkhrjffjuj zlpwcfwkcyj ffjeyvkcqsghyd qpaamkbzaacibzlhjqd

B.         First-Order Model. Dalam bahasa Inggris diketahui beberapa huruf muncul lebih sering dibandingkan huruf yang lain. sebagai contoh, huruf ‘a’ dan ‘e’ lebih umum daripada huruf ‘q’ dan ‘z’. Jadi dalam model ini karakter masih secara bebas terhadap satu sama lain, tetapi distribusi probabilitas dari karakter-karakter tersebut menurut distribusi statistikal urutan pertama dari teks bahasa Inggris. Teks yang secara tipikal dari model ini berbentuk seperti ini:

ocroh hli rgwr nmielwis eu ll nbnesebya th eei alhenhttpa oobttva nah brl

C.        Second-Order Model. Dua model sebelumnya diasumsi menurut statistik secara bebas dari satu karakter hingga karakter berikutnya. Ini tidak begitu akurat dibandingkan dengan bahasa alami Inggris. Sebagai contoh, beberapa huruf dalam kalimat tersebut hilang. Bagaimanapun juga, kita masih  dapat menerka huruf-huruf tersebut  dengan mencarinya pada konteks kalimat. Ini mengimplikasikan beberapa ketergantungan antara karakter-karakter. Secara alami, karakter yang saling berhubungan dekat lebih saling bergantung daripada karakter yang berhubungan jauh satu sama lainnya. Pada model ini, karakter yang ada X_i bergantung pada karakter sebelumnya X_i−1, tetapi secara kondisional tidak bergantung dengan semua karakter (X₁, X₂, …, X_i−2). Menurut model ini, distribusi probabilitas dari karakter X_i beragram menurut karakter sebelumnya X_i−1. Sebagai contoh, huruf ‘u’ jarang muncul (probabilitas = 0.022). Bagaimanapun juga, jika dinyatakan karakter sebelumnya adalah ‘q’ maka probabilitas dari ‘u’ dalam karakter berikutnya lebih tinggi (probabilitas = 0.995). Teks tipikal untuk model ini terlihat seperti berikut:

on ie antsoutinys are t inctore st be s deamy achin d ilonasive tucoowe at teasonare fuso tizin andy tobe seace ctisbe

D.        Third-Order Model. Ini merupakan pengembangan model sebelumnya. Berikut ini merupakan karakter X_i yang bergantung pada dua karakter sebelumnya (X_i−2, X_i−1) tetapi secara kondisional tidak bergantung pada semua karakter sebelumnya sebelum: (X₁, X₂,…, X_i−3). Pada model ini, distribusi dari X_i beragam menurut (X_i−2, X_i−1). Teks tipikal dari model ini seperti bentuk berikut ini:

in no ist lat whey cratict froure birs grocid pondenome of demonstures of the reptagin is regoactiona of cre

Penyusunan kembali menjadi teks Inggris asli akan memudahkan tiap teks di atas dapat dibaca.

E.         General Model. Pada model ini, buku X  merupakan proses acak seimbang yang berubah-ubah. Properti statistikal pada model seperti ini terlalu kompleks untuk dipertimbangkan sebagai tujuan praktikal. Model ini disukai hanya dalam sudut pandang teoritikal saja.

Model A di atas merupakan kasus khusus dari model B. Model B merupakan kasus spesial dari Model C. Model C merupakan kasus spesial dari model D. Model D merupakan kasus spesial dari model 

 Next Pages...