Okay, kali ini saya akan ajarkan apa itu algoritma LZ77 !
Bagi yang buka tutorial ini pasti udah tau dong apa itu LZ77.. Ya LZ77 adalah sebuah algoritma kompresi yang cukup efisien.
Tapi kali ini saya gak terlalu bahas tentang sejarah LZ77 atau teori2 sejenisnya tapi saya akan langsung berikran cara langsung menggunakan algoritma LZ77 ini.
Sebenarnya algoritma LZ77 ini mudah, tapi terkadang dibuat sulit oleh beberapa orang.. hahaha .. Kali ini saya akan ajarkan cara yang cukup mudah dipahami dan cukup jelas..Ini dia 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, kalau untuk karakter pertama langsung 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 tulisan "k". Lihat disebelah kiri "k" ada gak tulisan "k" ?? gak ada kan ? orang disebelah kiri tulisan "k" itu cuman "a" doang.. berarti sama seperti 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
sekarang warna merah berada pada tulisan "u". Lihat sebelah kiri "u" ada gak tulisan "u" ? gak ada kan ?? orang disebelah kiri tulisan "u" cuman ada "ak" doang.. berarti sama seperti 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
sekarang warna merahnya kan ada di "a". Lihat sebelah kiri "a" ada gak tulisan "a"? wow, ternyata ada.. yaitu di index ke 0. Nah jadi pada index ke 3 dan ke 0 mempunyai karakter yang sama yaitu "a".
Lalu sekarang tambahkan kedua index dengan 1. Jadi sekarang 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 tulisan yang sama , karakter sesudah 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 tulisan yang sama : 1 ya. Panjangnya kan emang 1. Orang yang sama itu cuman tulisan "a" doang, berarti ya panjangnya SATU. Kalau misal yg sama tulisan "anjing" berarti panjangnya 6. Tapi dlm kasus ini yg sama cuman "a" jadi ya SATU
karakter sesudah merah : "d" ya. Karakter sesudah merah ya "d". Merahnya kan "a" sesudahnya ya "d"..
Jadi penulisannya jadi seperti ini :
(3,1,d)
Nah ingat2 ya, kalau kasusnya ada karakter yang sama seperti ini, maka penggeseran dilakukan sampai pada karakter sesudah karakter sesudah 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 tenang nanti kalau udah biasa juga sangat mudah, bahkan diliat aja udah langsung 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 sampai ke kiri.
Jadi kalau mau cara panjangnya bisa diliat seperti 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 sekarang tambahkan kedua index sama
seperti cara sebelumnya.. saat ini index ada di 3 dan 5, maka
tambahkan masing2 dengan SATU. jadi indexnya 4 dan 6, lalu cek!
index ke 4 : d
index ke 6 : a
sama atau gak ? kalau sama, tambahin lagi sampai beda! TAPI INI
UDAH BEDA.. jadi stop!
okai, sekarang simpen dulu di notepad/kertas/tangan tulis aja index
yg sama index ke 3 dan 5. sekarang 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 sekarang tambahkan kedua index sama
seperti cara diatas.. Jadi index ke 1 dan index ke 6. sekarang lihat :
index ke 1 : k
index ke 6 : l
sama atua gak ? beda kan! berarti stop sampai disitu. berarti
sekarang index yang sama 0 dan 5.
Nah pada kasus2 seperti ini, yang sama kan ada 2 yaitu : index ke 3
dan 5 sama index ke 0 dan 5
Pilih yang mana ? karena keduanya panjangnya sama2 SATU(kok
bisa 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 adalah 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 sekarang kita mendapatkan 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 seperti tadi :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang tulisan yang sama , karakter sesudah merah)
jarak antara merah dengan karakter yang sama dikirinya : 2 karena liat sendiri dah antara karakter "a"(index ke 5) dengan karakter "a"(index ke 3) jaraknya kan ya tinggal 5-3 = 2.. --"
panjang tulisan yang sama : SATU karena cuman "a"
karakter sesudah merah : "l"
maka penulisannya jadi seperti ini :
(2,1,l)
setelah itu penggeseran dilakukan sesudah karakter "l" tadi ya. jadi langsung 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 seperti tadi, tinggal di cek satu2 ya. dari l(index 6) sampai 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 seperti cara sebelumnya, cek karakter sesudahnya
dengan cara seperti 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 seperti cara sebelumnya, cek karakter sesudahnya
dengan cara seperti 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 dapat 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 memilih dari ketiga pilihan tersebut. Yang pertama cari panjang karakter yang paling panjang. Dalam kasus ini panjangnya sama. Lalu kalau masih sama, cari indexnya paling besar yaitu index ke 5 dan 7. Yg dicek indexnyaitu yg 5,3,0 ya.. Jadi yang dipilih adalah index ke 5 dan 7 dengan panjang karakter : 1
cara penulisan sama seperti diatas :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang tulisan yang sama , karakter sesudah merah)
jarak antara merah dengan karakter yang sama dikirinya : 2 karena liat sendiri dah antara karakter "a"(index ke 7) dengan karakter "a"(index ke 5) jaraknya kan ya tinggal 7-5 = 2.. --"
panjang tulisan yang sama : SATU karena cuman "a"
karakter sesudah merah : "h"
jadi :
(2,1,h)
sekarang geser warna merah sesudah "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 bisa dicek lagi sama kok caranya seperti 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 sekarang index ke 2 dan ke 11
index ke 2 : "u"
index ke 11 : "u"
wah sama, nah sekarang stop sampai disitu..kenapa kok stop ? iyalah indexnya
udah mentok sampai 11, mau ditambah 1 lagi gak bisalah, udah mentok.
Nah pengecekan ke kanan itu digunakan untuk mengetahui panjang karakternya.
Pada sebelum2nya panjang karakter yg sama selalu 1, karena memang yg sama
cuman 1 karakter. Kalau ini berarti 3 karakter ? yups, dalam kasus ini, yang
sama adalah 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 seperti 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 seperti tadi, lihat panjang karakter terbesar. Yaitu index ke 0 dan 9.. YA udah, berarti itu yang kita pilih
Trus cara penulisannya sama seperti tadi :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang tulisan yang sama , karakter sesudah merah)
jarak antara merah dengan karakter yang sama dikirinya : 7 karena liat sendiri dah antara karakter "a"(index ke 9) dengan karakter "a"(index ke 2) jaraknya kan ya tinggal 9-2 = 7
panjang tulisan yang sama : TIGA karena yg sama itu tulisan "aku"
karakter sesudah merah : HABIS ALIAS KOSONG ALIAS NULL, jadi anggap aja 0 (nol)
(7,3,0)
Lalu sekarang 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, mudah kan ?
lalu gimana caranya buat decompress ?
mudah saja tinggal tulis spt ini :
(0,0,a) -> langsung tulis "a"
a
(0,0,k) -> langsung tulis "k"
ak
(0,0,u) -> langsung 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 kalau 0 itu null atau kosong)
akuadalah
mundur 7 langkah berarti didapat karakter "a" panjangnya 3, maka jadi "aku" trus ditambah 0 / null / kosong, jadinya tetep "aku"
akuadalahaku
wah kayaknya kok panjang banget caranya..? gak kok, sebenarnya simple aja, intinya kan cuma nyari kata yg dobel2 aja, dan dobelnya pasti yang paling panjang lah, kalo pendek ya kompressnya gak optimal.. tapi gpp, kita lanjut ke contoh 2, saya akan lebih cepat
CONTOH 2
Kata : "indonesiaraya" (tanpa tanda petik)
okai, kali ini saya ajarkan cara cepatnya aja, untuk contoh 1 tadi saya ajarkan cara panjang karena 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 sampai ke kanan jadi dari "i" sampai "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", jelas tidak ada yang sama karena "i" adalah 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! kalau saat 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 adalah SATU! lalu ingat rumus ini :
(Jarak antara merah dengan karakter yang sama dikirinya , panjang tulisan yang sama , karakter sesudah merah)
jaraknya : 3 (4 - 1 = 3)
panjangnya : 1
karakter sesudah merah : e
(3,1,e)
nah karena ada yang sama tadi ya, anda melanjutkan membaca karakter dimulai dari "s"(index ke 6), karena kalau 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 langsung 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", lalu 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 kalau panjang karakter sama, kita harus cari index terbesar yaitu "a" pada index ke 10
Jadi seperti ini
(2,1,0)
tau ya kok bisa 0 kenapa. karena udah karakter terakhir.
Selesai dah, ini dia 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, kalau angka depannya 0,0 berarti langsung 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". Jadi "ne"
indone
(0,0,s)
indones
(7,1,a)
7 karakter dari belakang yaitu "i" sepanjang 1. Jadi ya tetep "i". trus tambah "a". Jadi "ia"
indonesia
(0,0,r)
indonesiar
(2,1,y)
2 karakter dari belakang yaitu "a" sepanjang 1. Jadi ya tetep "a". trus tambah "y" jadi "ay"
indonesiaray
(2,1,0)
2 karakter dari belakang yaitu "a" sepanjang 1. Jadi 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 seperti 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 contoh satu, pasti langsung tau. "a" di kiri ada 2 yang sama, keduanya juga mempunyai panjang karakter 1 semua(kenapa satu ? baca di contoh 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. Jadi 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 sekarang kita cek "a" lagi. Oh iya, saya kasi tips aja kalau kalian masih blm ngerti panjang karakter yg sebelum2nya udah gw bahas berkali2. kan begini, saat ini kita cek karakter "a", ternyata dikirinya ada karakter "a". Okai, kita lanjut cek "ag", dikiri ternyata gak ada. Jadi 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", kalau ada lanjut lagi "agim" kalau ada lanjut terus dan seterusnya sampai gak ada.. tapi dalam kasus ini kita bisa liat bahwa yang ada itu cuman karakter "a" doang. maka penulisannya :
(4,1,k)
nah, abis ini kan kita cek karakter "a" lagi.. sama seperti sebelumnya, saya anggap udah mengerti caranya.
(2,1,n)
nah ini dia yang penting dan gak ada di contoh 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 agar mudah. Setelah karakter "s" bisa kita lihat yaitu "a" kalau 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
karena 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
karena 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
karena 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 bisa kita simpulkan! bahwa kata yang sama itu cuman "saya" bukan "sayak" atau "sayal" TAPI "saya" saja.
Setelah itu, kita masukan penulisannya sama persis seperti diatas.
(Jarak antara merah dengan karakter yang sama dikirinya , panjang tulisan yang sama , karakter sesudah 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 tulisan yang sama = 4 (S A Y A ITU ADA 4 KARAKTER)
karakter sesudah merah = "k" SESUDAH MERAH artinya merah yang paling akhir, kita bisa liat bahwa merah yang paling akhir adalah "a" di index ke 16, berarti sesudahnya ya "k"
(13,4,k)
sekarang kita baca karakter sesudah "k" yaitu "a", tak perlu saya jelasin lagiya.
(2,1,m)
dan yang terakhir adalah "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 saat decompress itu kalau depannya 0,0 langsung tulis aja!
(0,0,s)
s
(0,0,a)
sa
(0,0,y)
say
(2,1,l)
jangan sampai 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, sekarang 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, karena dicampur dengan huruf besar huruf kecil dan tanda baca.
Ingat!! Huruf BESAR dan Huruf kecil itu BERBEDA. Jangan disamain.
Ingat!! Spasi itu termasuk KARATER. disini karena tidak ada karakter berupa "_" maka karakter spasi silahkan diganti dengan "_" agar mudah !
Nah, kali ini buat contoh 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 bisa tanya di komentar dibawah ini.
PENGEMBANGAN LZ77
Nah, kali ini kita akan belajar mengenai pengembangan LZ77.
Teman-teman, saudara2, kita bisa lihat tadi kata2 sebelum dan setelah di kompress seperti 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 bisa 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 melakukan optimasi!!
Nah, disini caranya memang banyak. tapi saya hanya memberikan apa yang saya pernah pikirkan,. haha
Caranya begini gan,
Kita tau bahwa (0,0,i) itu adalah karakter "i" ! kenapa gak langsung aja tulis "i" ya kan ?
jadi kalau dari kata "iloveyouandyouloveme" akan menjadi
ilovey(4,1,u)and(6,3,l)(13,3,m)(2,1,0)nah, liat sekarang jadi berapa karakter ? yaitu 38 karakter
bisa di optimasi lagi gak ? jelas 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 bisa 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 bisa dikecilin lagi.. caranya gimana ? kita lihat bahwa gini aja biar gampang :
saat ada kata yang sama, kan biasanya dikurung. Nah kalau 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 kalau ada kata yang sama sebanyak 1-9 itu gak akan dikurung. Jadi pengurungannya mulai dari 10-256.
Itu aja dari saya(admin komputer67)
oh iya, tambahan aja, ada orang lain yang bilang bisa 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 :
0 komentar :
Post a Comment