17
Secara
garis besar penerapan Markov Chain
dalam algoritma
Lempel-Ziv ini dapat penulis jelaskan sebagai berikut.
Ilustrasi 1.
Pada suatu kasus data
sumber dengan keluaran (output)
X1,X2,
…
X
n
.
Di
asumsikan
probabilitas
output
pada
saat
n
memiliki
ketergantungan
kepada
output
pada
saat
n-1
dan
n-2
seperti
pada
markov
chain.
Kedua
output
sebelumnya
dijadikan
suatu
model
state
S
n-1
.
Hal
ini
yang
akan
diterapkan
pada
saat
sliding
windows
LZ77
digunakan
untuk
membuat
probabilitas susunan-susunan data input.
Pada
markov
chain
dibutuhkan
sebuah
model
probabilitas
untuk
memprediksi state
berikutnya.
Pada
kasus
kompresi
data,
nilai
probabilitas
ini
adalah
bervariasi
tergantung
oleh
waktu.
Dengan
kata
lain, pada bidang kompresi data memiliki sifat :
Jumlah simbol sumber dan jumlah simbol
yang telah di
encode/kompresi bervariasi, dengan kata lain simbol-simbol yang
di encode bergantung pada waktu.
Tidak
membutuhkan
nilai statistik probabilitas sejak awal, karena
seiring dengan input sumber nilai probabilitas akan beradaptasi.
Mengingat bahwa LZMA adalah pengembangan dari
LZ77,
maka
alasan
penerapan
Markov Chain
ke
dalam
algoritma
lempel
ziv
dikarenakan bahwa LZ77 adalah algoritma berdasarkan informasi (
information-theoritic
), apabila
AEP
(Asymptotic
Equipartition
Property)
 |