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
= (X1, X2, X3, X4, …)
Dimana
X
merepresentasikan seluruh buku, dan X1
merepresentasikan karakter pertama dari buku tersebut, X2 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 Xi bergantung pada
karakter sebelumnya Xi−1, tetapi secara kondisional tidak bergantung
dengan semua karakter (X1, X2, …, Xi−2).
Menurut model ini, distribusi probabilitas dari karakter Xi beragram menurut
karakter sebelumnya Xi−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 Xi
yang bergantung pada dua karakter sebelumnya (Xi−2, Xi−1)
tetapi secara kondisional tidak bergantung pada semua karakter sebelumnya
sebelum: (X1, X2,…, Xi−3). Pada model
ini, distribusi dari Xi beragam menurut (Xi−2,
Xi−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