Tutorial Algoritma Lz77 Disertai Rujukan Dan Pengembangannya
Okay, kali ini saya akan ajarkan apa itu algoritma LZ77 !
Bagi yang buka tutorial ini niscaya udah tau dong apa itu LZ77.. Ya LZ77 yakni sebuah algoritma kompresi yang cukup efisien.
Tapi kali ini saya gak terlalu bahas perihal sejarah LZ77 atau teori2 sejenisnya tapi saya akan eksklusif berikran cara eksklusif memakai algoritma LZ77 ini.
Sebenarnya algoritma LZ77 ini mudah, tapi terkadang dibentuk sulit oleh beberapa orang.. hahaha .. Kali ini saya akan ajarkan cara yang cukup simpel dipahami dan cukup jelas..Ini beliau caranya :
CONTOH 1
Kata : "akuadalahaku" (tanpa tanda petik)
pertama beri warna merah pada karakter pertama
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
ingat2 aja, jikalau untuk karakter pertama eksklusif tulis output :
(0,0,a)
selanjutnya warna merah digeser ke kanan
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
sekarang warna merah berada pada goresan pena "k". Lihat disebelah kiri "k" ada gak goresan pena "k" ?? gak ada kan ? orang disebelah kiri goresan pena "k" itu cuman "a" doang.. berarti sama menyerupai tadi cara penulisannya
(0,0,k)
lanjut lagi, warna merah digeser..
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
kini warna merah berada pada goresan pena "u". Lihat sebelah kiri "u" ada gak goresan pena "u" ? gak ada kan ?? orang disebelah kiri goresan pena "u" cuman ada "ak" doang.. berarti sama menyerupai tadi penulisannya
(0,0,u)
lanjut, geser lagi merahnya..
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
kini warna merahnya kan ada di "a". Lihat sebelah kiri "a" ada gak goresan pena "a"? wow, ternyata ada.. yaitu di index ke 0. Nah jadi pada index ke 3 dan ke 0 memiliki karakter yang sama yaitu "a".
Lalu kini tambahkan kedua index dengan 1. Kaprikornus kini index ke 4 dan ke 1. Sekarang di cek, apakah index ke 4 dan ke 1 sama.
Index ke 4 : d
index ke 1 : k
oh, beda ternyata. Berarti yang sama cuman index ke 0 dan 3 saja.Iyalah diliat aja udah keliatan..
saya kasi warna oranye untuk a disebelah kiri ya.
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
Terus, cara penulisannya begini gan
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jadi :
Jarak antara merah dengan karakter yang sama dikirinya : 3 ya
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
|------|
jarak = 3
Panjang goresan pena yang sama : 1 ya. Panjangnya kan emang 1. Orang yang sama itu cuman goresan pena "a" doang, berarti ya panjangnya SATU. Kalau misal yg sama goresan pena "anjing" berarti panjangnya 6. Tapi dlm masalah ini yg sama cuman "a" jadi ya SATU
karakter setelah merah : "d" ya. Karakter setelah merah ya "d". Merahnya kan "a" sesudahnya ya "d"..
Jadi penulisannya jadi menyerupai ini :
(3,1,d)
Nah ingat2 ya, jikalau kasusnya ada karakter yang sama menyerupai ini, maka penggeseran dilakukan hingga pada karakter setelah karakter setelah merah yaitu "d". Ngerti gak ? hehe.. jadi merahnya di "a" index ke 5
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
okay, cukup rumit ya... tapi hening nanti jikalau udah biasa juga sangat mudah, bahkan diliat aja udah eksklusif ketemu.. haha
Lanjuttt!!
sekarang merah berada di index ke 5 yaitu "a"
di sebelah kiri "a" itu kita cek apakah ada karakter "a" lagi. Oh iya, saya lupa mengingatkan.. Saat pengecekan apakah ada yg sama atau tidak, itu dilakukan mulai dari karakter berwarna merah hingga ke kiri.
Jadi jikalau mau cara panjangnya sanggup diliat menyerupai ini :
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah d = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah a = a ? IYA ! maka kini tambahkan kedua index sama
menyerupai cara sebelumnya.. ketika ini index ada di 3 dan 5, maka
tambahkan masing2 dengan SATU. jadi indexnya 4 dan 6, kemudian cek!
index ke 4 : d
index ke 6 : a
sama atau gak ? jikalau sama, tambahin lagi hingga beda! TAPI INI
UDAH BEDA.. jadi stop!
okai, kini simpen dulu di notepad/kertas/tangan tulis aja index
yg sama index ke 3 dan 5. kini lanjutkan penggeseran sampai
paling kiri!
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah u = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah k = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah a = a ? IYA ! Maka kini tambahkan kedua index sama
menyerupai cara diatas.. Kaprikornus index ke 1 dan index ke 6. kini lihat :
index ke 1 : k
index ke 6 : l
sama atua gak ? beda kan! berarti stop hingga disitu. berarti
kini index yang sama 0 dan 5.
Nah pada kasus2 menyerupai ini, yang sama kan ada 2 yaitu : index ke 3
dan 5 sama index ke 0 dan 5
Pilih yang mana ? sebab keduanya panjangnya sama2 SATU(kok
sanggup satu ? iyalah yg sama cuman "a" doang, sedangkan karakter
setelah "a" juga beda kan abis di cek tadi) maka pilih yang indexnya
paling besar.
3 dan 5 => index yang paling besar itu yakni 3 dan 5. yang kita
cek 3 dan 0 sedangkan 5nya gak usah soalnya sama, 3
dan 0 kan paling besar kan 3. maka 3 dan 5 lah yang
kita pilih
0 dan 5 = > tidak dipilih !
Nah kini kita mendapat index ke 3 dan 5
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
cara penulisannya sama menyerupai tadi :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jarak antara merah dengan karakter yang sama dikirinya : 2 sebab liat sendiri dah antara karakter "a"(index ke 5) dengan karakter "a"(index ke 3) jaraknya kan ya tinggal 5-3 = 2.. --"
panjang goresan pena yang sama : SATU sebab cuman "a"
karakter setelah merah : "l"
maka penulisannya jadi menyerupai ini :
(2,1,l)
setelah itu penggeseran dilakukan setelah karakter "l" tadi ya. jadi eksklusif aja jadi spt ini :
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
caranya menyerupai tadi, tinggal di cek satu2 ya. dari l(index 6) hingga a(index 0)
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah l = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah a = a ? IYA. Maka menyerupai cara sebelumnya, cek karakter sesudahnya
dengan cara menyerupai tadi. karakter sesudahnya kan ya "l" dan
"h" sama gak ?beda ya. berarti panjangnya cuman 1. skrg
catat di kertas atau notepad. yaitu index ke 5 dan 7
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah d = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah a = a ? IYA. Maka menyerupai cara sebelumnya, cek karakter sesudahnya
dengan cara menyerupai diatas ya. Karakter sesudahnya yaitu "d" dan "h". Sama
gak ?? beda kan. berarti stop disitu dan artinya panjangnya cuman 1. trus
tulis di kertas/notepad : index ke 3 dan 7
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah u = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah k = a ? tidak ! maka cek kirinya lagi !
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 apakah a = a ? IYA. Maka spt cara sebelum. cek karakter sesudahnya yaitu
"k" dan "h" sama gak ? beda kan? maka panjang karakternya 1 saja. trus tulis
di kertas/notepad : index ke 0 dan 7
Sekarang kan kita udah sanggup 3 macam kesamaan yaitu
index ke 5 dan 7 panjang karakter : 1
index ke 3 dan 7 panjang karakter : 1
index ke 0 dan 7 panjang karakter : 1
diatas saya lupa kasi tau bagaimana cara menentukan dari ketiga pilihan tersebut. Yang pertama cari panjang karakter yang paling panjang. Dalam masalah ini panjangnya sama. Lalu jikalau masih sama, cari indexnya paling besar yaitu index ke 5 dan 7. Yg dicek indexnyaitu yg 5,3,0 ya.. Kaprikornus yang dipilih yakni index ke 5 dan 7 dengan panjang karakter : 1
cara penulisan sama menyerupai diatas :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jarak antara merah dengan karakter yang sama dikirinya : 2 sebab liat sendiri dah antara karakter "a"(index ke 7) dengan karakter "a"(index ke 5) jaraknya kan ya tinggal 7-5 = 2.. --"
panjang goresan pena yang sama : SATU sebab cuman "a"
karakter setelah merah : "h"
jadi :
(2,1,h)
kini geser warna merah setelah "h" jadi spt ini :
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
nah, disini sanggup dicek lagi sama kok caranya menyerupai tadi :
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 BEDA
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 SAMA! maka cek karakter sesudahnya yaitu "h" dan "k", beda ya "h" sama"k"
maka tulis di kertas/notepad : index ke 7 dan 9 dengan panjang karakter 1
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 BEDA
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 SAMA! karakter sesudahnya yaitu "l" dan "k" yang ternyata beda. Berarti tulis
di kertas/notepad : index ke 5 dan 9 dengan panjang karakter 1
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 BEDA
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 SAMA! karakter sesudahnya yaitu "d" dan "k" yang ternyata BEDA. Berarti tulis
di kertas/notepad : index ke 3 dan 9 dengan panjang karakter 1
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 BEDA
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 BEDA
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11 SAMA! Nah ini dia.. Setelah itu kan di cek karakter setelahnya yaitu index ke 1
dan index ke 10.
Index ke 1 : "k"
Index ke 10 : "k"
wahh, ternyata sama nih.. berarti lanjut lagi indexnya tambah 1 terus sampai
keduanya BEDA, jadi kini index ke 2 dan ke 11
index ke 2 : "u"
index ke 11 : "u"
wah sama, nah kini stop hingga disitu..kenapa kok stop ? iyalah indexnya
udah mentok hingga 11, mau ditambah 1 lagi gak bisalah, udah mentok.
Nah pengecekan ke kanan itu dipakai untuk mengetahui panjang karakternya.
Pada sebelum2nya panjang karakter yg sama selalu 1, sebab memang yg sama
cuman 1 karakter. Kalau ini berarti 3 karakter ? yups, dalam masalah ini, yang
sama yakni 3 karakter. maka tetap ditulis : index ke 0 dan 9 dgn pjg karakter 3
a k u a d a l a h a k u
0 1 2 3 4 5 6 7 8 9 10 11
Bisa dilihat ya, yang sama 3 karakter. Nah sama menyerupai tadi, kita kumpulkan index2 yang sama tadi :
Index ke 7 dan 9 dengan panjang karakter 1
Index ke 5 dan 9 dengan panjang karakter 1
Index ke 3 dan 9 dengan panjang karakter 1
Index ke 0 dan 9 dengan panjang karakter 3
sama menyerupai tadi, lihat panjang karakter terbesar. Yaitu index ke 0 dan 9.. YA udah, berarti itu yang kita pilih
Trus cara penulisannya sama menyerupai tadi :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jarak antara merah dengan karakter yang sama dikirinya : 7 sebab liat sendiri dah antara karakter "a"(index ke 9) dengan karakter "a"(index ke 2) jaraknya kan ya tinggal 9-2 = 7
panjang goresan pena yang sama : TIGA sebab yg sama itu goresan pena "aku"
karakter setelah merah : HABIS ALIAS KOSONG ALIAS NULL, jadi anggap aja 0 (nol)
(7,3,0)
Lalu kini kumpulkan tulisan2 berwarna biru :
(0,0,a)
(0,0,k)
(0,0,u)
(3,1,d)
(2,1,l)
(2,1,h)
(7,3,0)
Selesaii sudah, simpel kan ?
lalu gimana caranya buat decompress ?
mudah saja tinggal tulis spt ini :
(0,0,a) -> eksklusif tulis "a"
a
(0,0,k) -> eksklusif tulis "k"
ak
(0,0,u) -> eksklusif tulis "u"
aku
(3,1,d) -> mundur 3 langkah, dengan panjang 1 trus tambah "d"
aku
mundur 3 langkah maksudnya ya itung 3 karakter dari belakang dan didapat "a", panjangnya 1, maka tetep "a" trus ditambah "d" maka jadi "ad"
akuad
(2,1,l) -> mundur 2 langkah, dengan panjang 1 trus tambah "l"
akuad
mundur 2 langkah maksudnya itung 2 karakter dari belakang dan didapat "a", panjangnya 1, maka tetep "a" trus ditambah "l" maka jadi "al"
akuadal
(2,1,h) -> mundur 2 langkah, dengan panjang 1 trus tambah "h"
akuadal
mundur 2 langkah berarti didapat karakter "a", panjangnya 1, maka tetep "a", trus ditambah "h" maka jadi "ah"
akuadalah
(7,3,0) -> mundur 7 langkah, dengan panjang 3 trus tambah"0" (ingat jikalau 0 itu null atau kosong)
akuadalah
mundur 7 langkah berarti didapat karakter "a" panjangnya 3, maka jadi "aku" trus ditambah 0 / null / kosong, akhirnya tetep "aku"
akuadalahaku
wah kayaknya kok panjang banget caranya..? gak kok, sebetulnya simple aja, pada dasarnya kan cuma nyari kata yg dobel2 aja, dan dobelnya niscaya yang paling panjang lah, kalo pendek ya kompressnya gak optimal.. tapi gpp, kita lanjut ke teladan 2, saya akan lebih cepat
CONTOH 2
Kata : "indonesiaraya" (tanpa tanda petik)
okai, kali ini saya ajarkan cara cepatnya aja, untuk teladan 1 tadi saya ajarkan cara panjang sebab memang untuk mengaplikasikannya di bahasa pemrograman.
Mari kita lihat,
i n d o n e s i a r a y a
0 1 2 3 4 5 6 7 8 9 10 11 12
baca karakter(karakter itu 1 HURUF) dari kiri hingga ke kanan jadi dari "i" hingga "a"
disetiap anda membaca karakter, anda lihat di kirinya apakah ada yang sama kaya karakter yg anda baca atau tidak.
Misal anda baca mulai dari "i", terang tidak ada yang sama sebab "i" yakni karakter awal
(0,0,i)
lalu anda baca "n", tidak terdapat karakter yang sama dengan "n" disebelah kiri "n"
(0,0,n)
lalu anda baca "d", disebelah kiri "d" juga tidak ada karakter "d"
(0,0,d)
lalu anda baca "o", disebelah kiri "o" juga tidak ada karakter "o"
(0,0,o)
lalu anda baca "n", ternyata ada karakter yang sama dengan "n" disebelah kirinya "n". yaitu "n" index ke 1 sama dengan "n" index ke 4, trus ingat! jikalau ketika ngecek ternyata ada yang sama, berarti kita cek karakter sesudahnya
i n d o n e s i a r a y a
0 1 2 3 4 5 6 7 8 9 10 11 12
i n d o n e s i a r a y a
0 1 2 3 4 5 6 7 8 9 10 11 12
wah ternyata "d" sama "e" beda, berarti yang sama cuma sebatas "n" aja yang artinya jumlah karakter yang sama yakni SATU! kemudian ingat rumus ini :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jaraknya : 3 (4 - 1 = 3)
panjangnya : 1
karakter setelah merah : e
(3,1,e)
nah sebab ada yang sama tadi ya, anda melanjutkan membaca karakter dimulai dari "s"(index ke 6), sebab jikalau ada yang sama anda harus mulai membacanya lagi dari karakter setelah "e". ngerti ya tadi udah saya jelasin diatas
Lalu anda baca "s", disebelah kiri "s" tidak ada karakter "s"
(0,0,s)
Lalu anda baca "i", disebelah kiri "i" ternyata ada karakter "i", maka eksklusif aja kita cek karakter setelah "i" beda ya, soalnya karakter setelahnya "n" dan "a" jadi panjang karakter cuma 1
(7,1,a)
ingat, pembacaan dimulai setelah "a", yaitu "r"
Lalu anda baca "r", disebelah kiri "r" tidak ada karakter "r"
(0,0,r)
Lalu anda baca "a", disebelah kiri "a" ada karakter "a" pada index ke 8. Index setelahnya pun juga berbeda keduanya. Berarti panjang karakter 1
(2,1,y)
pembacaan dilanjutkan setelah "y" yaitu "a"
Terakhir, anda baca "a", disebelah kiri ada "a", kemudian kan ada 2 "a" nih yaitu "a" index ke 10 dan "a" index ke 8.
Panjang karakter masing2 satu ya. Uda banyak saya jelasin cara mencari panjang karakter.
Berarti jikalau panjang karakter sama, kita harus cari index terbesar yaitu "a" pada index ke 10
Jadi menyerupai ini
(2,1,0)
tau ya kok sanggup 0 kenapa. sebab udah karakter terakhir.
Selesai dah, ini beliau hasil kompresinya.
(0,0,i)
(0,0,n)
(0,0,d)
(0,0,o)
(3,1,e)
(0,0,s)
(7,1,a)
(0,0,r)
(2,1,y)
(2,1,0)
Sekarang cara DECOMPRESSnya :
ingat cara cepatnya, jikalau angka depannya 0,0 berarti eksklusif tulis aja
(0,0,i)
i
(0,0,n)
in
(0,0,d)
ind
(0,0,o)
indo
(3,1,e)
3 karakter dari belakang yaitu "n" sepanjang 1. jadi ya tetep "n" . trus tambah "e". Kaprikornus "ne"
indone
(0,0,s)
indones
(7,1,a)
7 karakter dari belakang yaitu "i" sepanjang 1. Kaprikornus ya tetep "i". trus tambah "a". Kaprikornus "ia"
indonesia
(0,0,r)
indonesiar
(2,1,y)
2 karakter dari belakang yaitu "a" sepanjang 1. Kaprikornus ya tetep "a". trus tambah "y" jadi "ay"
indonesiaray
(2,1,0)
2 karakter dari belakang yaitu "a" sepanjang 1. Kaprikornus ya tetep "a". trus tambah "0" alias null alias kosong gak usah ditambah jadi "a" doang
indonesiaraya
CONTOH 3
Kata : "sayalagimakansayakamu"
sekarang kita akan mengerjakan ini sedikit lebih cepat. Ingat inti dari algoritma LZ77 hanya mencari kata2 yang dobel saja..!
Tapi tata caranya harus sama menyerupai diatas
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
langsung aja :
(0,0,s)
(0,0,a)
(0,0,y)
karena "a" dikiri ada dan panjang karakter yang sama cuman 1 yaitu "a" saja(karakter selanjutnya beda), maka
(3-1,1,l)
(2,1,l)
setelah karakter "l" kita cek karakter "a".
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
kalau anda udah baca dari teladan satu, niscaya eksklusif tau. "a" di kiri ada 2 yang sama, keduanya juga memiliki panjang karakter 1 semua(kenapa satu ? baca di teladan 1 dan 2), maka kita pilih dengan index yang paling besar yaitu "a" pada index ke 3. kenapa gak "a" yg index ke 1? iyalah 3 lebih besar daripada 1, kan udah saya bilang pilih yg paling besar. Kaprikornus penulisannya spt ini
(2,1,g)
kita lanjutkan cek setelah karakter "g". yaitu "i". kita cek "i" dan gak ada yg sama
(0,0,i)
(0,0,m)
nah kini kita cek "a" lagi. Oh iya, saya kasi tips aja jikalau kalian masih blm ngerti panjang karakter yg sebelum2nya udah gw bahas berkali2. kan begini, ketika ini kita cek karakter "a", ternyata dikirinya ada karakter "a". Okai, kita lanjut cek "ag", dikiri ternyata gak ada. Kaprikornus yang ada cuma karakter "a", maka dari itu "a" sendiri itu panjang karakternya SATU. Kalau misal aja, ternyata di kiri ada kata "ag", kita lanjutkan cek dikiri ada kata "agi", jikalau ada lanjut lagi "agim" jikalau ada lanjut terus dan seterusnya hingga gak ada.. tapi dalam masalah ini kita sanggup liat bahwa yang ada itu cuman karakter "a" doang. maka penulisannya :
(4,1,k)
nah, abis ini kan kita cek karakter "a" lagi.. sama menyerupai sebelumnya, saya anggap udah mengerti caranya.
(2,1,n)
nah ini beliau yang penting dan gak ada di teladan sebelum2nya.. Mohon baca baik2 dan dipahami betul!
saat ini kita cek karakter "s"
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
saya kasi tips semoga mudah. Setelah karakter "s" sanggup kita lihat yaitu "a" jikalau digabung "sa"
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
kita cek apakah dikiri ada kata "sa" dan ternyata ADA
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
sebab ada, kita lanjutkan. Setelah kata "sa", kita lanjutkan jadi "say"
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
kita cek apakah dikiri ada kata "say" dan ternyata ADA
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
sebab ada, kita lanjutkan. Setelah kata "say", kita lanjutkan jadi "saya"
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
kita cek apakah dikiri ada kata "saya" dan ternyata ADA
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
sebab ada, kita lanjutkan. Setelah kata "saya", kita lanjutkan jadi "sayak"
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
kita cek apakah dikiri ada kata "sayak" dan ternyata TIDAK ADA.
s a y a l a g i m a k a n s a y a k a m u
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Maka sanggup kita simpulkan! bahwa kata yang sama itu cuman "saya" bukan "sayak" atau "sayal" TAPI "saya" saja.
Setelah itu, kita masukan penulisannya sama persis menyerupai diatas.
(Jarak antara merah dengan karakter yang sama dikirinya , panjang goresan pena yang sama , karakter setelah merah)
jaraknya berapa ?? tinggal itung dari karakter "s" jangan dari karakter "a" atau "k" atau "l" TAPI "s"
"s" nya yang kanan kan berindex 13, dan yang kiri berindex 0, berarti jaraknya 13-0 = 13
jarak : 13
panjang goresan pena yang sama = 4 (S A Y A ITU ADA 4 KARAKTER)
karakter setelah merah = "k" SESUDAH MERAH artinya merah yang paling akhir, kita sanggup liat bahwa merah yang paling tamat yakni "a" di index ke 16, berarti sesudahnya ya "k"
(13,4,k)
kini kita baca karakter setelah "k" yaitu "a", tak perlu saya jelasin lagiya.
(2,1,m)
dan yang terakhir yakni "u"
(0,0,u)
Selesai sudah, mari kita gabung
(0,0,s)
(0,0,a)
(0,0,y)
(2,1,l)
(2,1,g)
(0,0,i)
(0,0,m)
(4,1,k)
(2,1,n)
(13,4,k)
(2,1,m)
(0,0,u)
Itulah hasil compress dengan algoritma LZ77.
Sekarang mari kita decompress!
ingat ketika decompress itu jikalau depannya 0,0 eksklusif tulis aja!
(0,0,s)
s
(0,0,a)
sa
(0,0,y)
say
(2,1,l)
jangan hingga lupa, caranya tinggal baca 2 karakter dari belakang dengan panjang karakter 1 tambahkan "l"
sayal
sayal
(2,1,g)
caranya sama !
sayalag
(0,0,i)
sayalagi
(0,0,m)
sayalagim
(4,1,k)
sayalagimak
(2,1,n)
sayalagimakan
(13,4,k)
nah ini caranya juga sama, baca 13 karakter dari belakang dengan panjang karakter 4 trus tambahkan "k"
sayalagimakansayak
sayalagimakansayak
(2,1,m)
sayalagimakansayakam
(0,0,u)
sayalagimakansayakamu
CONTOH 4
Kata : "iloveyouandyouloveme" (tanpa tanda petik)
caranya sama, kini kita lebih cepattt lagiii!
(0,0,i)
(0,0,l)
(0,0,o)
(0,0,v)
(0,0,e)
(0,0,y)
i l o v e y o u a n d y o u l o v e m e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
(4,1,u)
(0,0,a)
(0,0,n)
(0,0,d)
i l o v e y o u a n d y o u l o v e m e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
(6,3,l)
i l o v e y o u a n d y o u l o v e m e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
(13,3,m)
i l o v e y o u a n d y o u l o v e m e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
(2,1,0)
kalau digabung jadi spt ini :
(0,0,i)
(0,0,l)
(0,0,o)
(0,0,v)
(0,0,e)
(0,0,y)
(4,1,u)
(0,0,a)
(0,0,n)
(0,0,d)
(6,3,l)
(13,3,m)
(2,1,0)
Sekarang kita decompress :
(0,0,i)
i
(0,0,l)
il
(0,0,o)
ilo
(0,0,v)
ilov
(0,0,e)
ilove
(0,0,y)
ilovey
(4,1,u)
iloveyou
(0,0,a)
iloveyoua
(0,0,n)
iloveyouan
(0,0,d)
iloveyouand
(6,3,l)
iloveyouandyoul
(13,3,m)
iloveyouandyoulovem
(2,1,0)
iloveyouandyouloveme
CONTOH 5
Kata : "Tutorial Algoritma LZ77 Disertai Contoh Dan Pengembangannya" (DENGAN TANDA PETIK 2)
ini cukup sulit, sebab dicampur dengan abjad besar abjad kecil dan tanda baca.
Ingat!! Huruf BESAR dan Huruf kecil itu BERBEDA. Jangan disamain.
Ingat!! Spasi itu termasuk KARATER. disini sebab tidak ada karakter berupa "_" maka karakter spasi silahkan diganti dengan "_" semoga simpel !
Nah, kali ini buat teladan yang k-5 silahkan kerjakan sendiri ya.. ini buat latihan aja..
Kalau mau tau jawabannya, silahkan cek di fans page komputer67
nah, kalo anda masih belum mengerti juga (parah amat udah gw kasi 5 cth msh ga ngerti) lu sanggup tanya di komentar dibawah ini.
PENGEMBANGAN LZ77
Nah, kali ini kita akan berguru mengenai pengembangan LZ77.
Teman-teman, saudara2, kita sanggup lihat tadi kata2 sebelum dan setelah di kompress menyerupai apa..!
SEBELUM KOMPRESS : iloveyouandyouloveme (20 karakter)
SETELAH DIKOMPRESS :
(0,0,i)
(0,0,l)(0,0,o)
(0,0,v)
(0,0,e)
(0,0,y)
(4,1,u)
(0,0,a)
(0,0,n)
(0,0,d)
(6,3,l)
(13,3,m)
(2,1,0)
Total : 92 karakter
Kita lihat ya !! dari 20 karakter ke 92 karakter(kok sanggup 92 karakter, itung aja dari koma nya angka 0 nya tanda baca ( dan ) )
kalo dari 20 karakter ke 92 karakter itu namanya bukan kompress dong ? tenang,,
berarti kita harus melaksanakan optimasi!!
Nah, disini caranya memang banyak. tapi saya hanya menunjukkan apa yang saya pernah pikirkan,. haha
Caranya begini gan,
Kita tau bahwa (0,0,i) itu yakni karakter "i" ! kenapa gak eksklusif aja tulis "i" ya kan ?
jadi jikalau dari kata "iloveyouandyouloveme" akan menjadi
ilovey(4,1,u)and(6,3,l)(13,3,m)(2,1,0)nah, liat kini jadi berapa karakter ? yaitu 38 karakter
sanggup di meningkatkan secara optimal lagi gak ? terang bisa!
kita lihat (4,1,u) kenapa harus pake u ? kalo enggak kan juga gpp kan ?
ilovey(4,1)uand(6,3)l(13,3)m(2,1,0)
kita lihat lagi, jadi berapa karakter ? yaitu 35 karakter
lumayan kan ?
ternyata masih sanggup lagi..
kita lihat kurung yang paling akir yaitu (2,1,0) "0" itu artinya kan udah habis. kenapa gak di ilangin sekalian ??
jadi :
ilovey(4,1)uand(6,3)l(13,3)m(2,1)
sekarang jadi 33 karakter..
ternyataaa masih sanggup dikecilin lagi.. caranya gimana ? kita lihat bahwa gini aja biar simpel :
saat ada kata yang sama, kan biasanya dikurung. Nah jikalau kata yang sama itu panjang karakternya cuman SATU, artinya harus dikurung trus dikasi koma dll, kan buang2 aja nih.
Nah caranya ya kita harus beri batas misal, 10 - 256 karakter yang sama. Apa maksudnya ?
Jadi jikalau ada kata yang sama sebanyak 1-9 itu gak akan dikurung. Kaprikornus pengurungannya mulai dari 10-256.
Itu aja dari saya(admin komputer67)
oh iya, embel-embel aja, ada orang lain yang bilang sanggup juga di kecilin lewat algoritma HUFFMAN. Nah lain kali akan saya bahas mengenai algoritma HUFFMAN.
Semoga bermanfaat, dan jangan lupa like fanspage KOMPUTER67 dibawah ini :
Sumber http://komputer67.blogspot.com
0 Response to "Tutorial Algoritma Lz77 Disertai Rujukan Dan Pengembangannya"
Posting Komentar