Algoritma Encoding LZ77
Source: Slide Tekod, Fakultas Informatika, Telkom University.
Algoritma Decoding LZ77
Source: Slide Tekod, Fakultas Informatika, Telkom University
Contoh Cara Mencari Encoding LZ77
Encoding Of The String : kakikakek
Jawab :
#Sebelumnya Encoding LZ77 dibagi menjadi 2 bagian gan, yaitu:
- Search Buffer, yaitu berisikan kamus
- Look-Ahead Buffer, yaitu berisikan teks yang belum terencode
Lanjut gan, Maka hasil Encode dari kakikakek adalah :
Encodingnya : (00k00a21i43e81)
Penjelasannya :
- Buat dulu tabel seperti diatas. banyaknya index ditentukan dengan banyaknya jumlah karakter yang mau di encode ya gan. disini ada 9 index pada karakter kakikakek
- Kenapa hasil Encode pertama (0,0,k) ?. Coba bisa kita lihat. pada output pertama, untuk dua output pertama bernilai 0 karena pada bagian seacrh fuffer kita masih kosong. sedangkan karakter k karena karakter pertama yang akan digeser ke search fuffer adalah huruf k. sehingga huruf k digeser ke index ke-1. maka output look-ahead buffer menjadi akikakek.
- Kenapa hasil Encode kedua (0,0,a) ?. coba perhatikan tabel diatas gan. karakter selanjutnya yang akan digeser ke search buffer adalah a, dan disini kita akan mencari karakter a tersebut ada tidak di index search buffer?. ternyata tidak ada gan. maka encodenya adalah 0 dan panjang karakter yang sama adalah 0 karakter. sehingga Jadi encodingnya (0,0,a). terus huruf a digeser ke search buffer ke index ke-1 dan huruf k digeser ke index ke-2. output look-ahead buffernya jadi kikakek.
- Kenapa hasil Encode ketiga (2,1,i) ?. perhatikan tabel diatas gan. karakter selanjutnya yang akan digeser ke search buffer adalah k, dan disini kita akan mencari karakter k tersebut ada tidak di index search buffer?. ehh ternyata ada gan. nah jika ada, cek karakter selanjutnya gan yaitu i. ada gak? ternyata gak ada. yaudah gan, jadi cuman karakter k kan yang ada di search buffer. nah pada index berapa hayoo? ternyata ada pada diindex ke-2 dan panjang karakter yang sama adalah 1 karakter. sehingga jadi encodingnya (karakter di L-AB ada di SB pada index ke-2, sepanjang 1 karakter, jika karakter di L-AB ada di SB maka karakter selanjutanya yang gak ada di SB ) atau (2,1,i) hehehe :D. terus karakter k i digeser ke search buffer ke index ke-2 dan karakter k a digeser ke index ke-4. output look-ahead buffernya jadi kakek.
- Kenapa hasil Encode keempat (4,3,e) ?. ya sama aja gan kaya yang tadi. jadi kan karakter selanjutnya yang akan digeser ke search buffer adalah k. nah di cek ada gak di search buffer. eh ternyata ada gan. jika ada cek lagi karakter selanjutnya yaitu a. eh ternyata ada lagi gan. hmmm yaudah cek terus lagi gan. yaitu karakter k lagi gan. ternyata ada juga. lanjut terus gan di cek lagi. karakter selanjutnya adalah e. ada gak di search buffer?. ternyata gak ada gan. yaudah gan jadi tadi kan yang ada setelah di cek yaitu karakter k a k kan gan?. nah itu tuh adanya pada index keberapa pada search buffer? ternyata pada index ke-4 kan gan. sepanjang 3 karakter. sehingga jadi encodingnya adalah (4,3,e). terus karakter k a k e digeser ke search buffer ke index ke-4 dan karakter k a k i digeser ke index ke-8. output look-ahead buffernya jadi k doang gan.
- Terakhir gan, kenapa hasil encode kelima (8,1) ?. yaaa karena coba kita cek. pada karakter selanjutnya yang akan di cek di search buffer adalah karakter k. ada gak di search buffer? ternyata ada gan. nah berarti jika ada, cek karakter selanjutnya. tapi disini karakter selanjutnya udah habis gan. ya udah langsung aja eksekusi. karakter k kan ada tuh di search buffer, pada index keberapa?. ternyata pada index ke-8 gan, sepanjang 1 karakter. jadi hasil encodingnya adalah (8,1). terus karakter k digeser ke search buffer ke index ke-1 dan karakter k a k i k a k e digeser ke index ke-9. output look-ahead buffernya gak ada gan.
- Selesai deh gan, jadi hasil encoding kakikakek menggunakan kompresi jenis LZ77 adalah (00k00a21i43e81).
Contoh Cara Mencari Decoding LZ77#contoh decodingnya dari hasil encoding kakikakek ya gan. yaitu (00k00a21i43e81).
tentukan hasil decoding dari (00k00a21i43e81) menggunakan LZ77...!!!
Jawab :
(00k00a21i43e81)
dibuat dulu kayak gini gan:
(0,0,k)
(0,0,a)
(2,1,i)
(4,3,e)
(8,1,-)
nah udah dibut gitu terus:
(0,0,k) → index ke 0, sepanjang 0, k → k
(0,0,a) → index ke 0, sepanjang 0, a → a
(2,1,i) → index ke 2, sepanjang 1, i → k+i
(4,3,e) → index ke 4, sepanjang 3, e → kak+e
(8,1,-) → index ke 8, sepanjang 1, - →k
Decoding → kakikakek
Penjelasannya :
Ket: ingat melihat index dari bawah ke atas dan dari kanan ke kiri... :D
(0,0,k) → index ke 0, sepanjang 0, k → k
(0,0,a) → index ke 0, sepanjang 0, a → a
(2,1,i) → index ke 2, sepanjang 1, i → k+i
- (0,0,k) → k (index 0)
- (0,0,a) → a (index 0)
-------------------------------------------------------
(0,0,k) → k (index 2)
(0,0,a) → a (index 1)
- Ingat gan. Menghitung indexnya dari bawah ke atas gan. jadi disitu pada encoding (2,1,i) bisa dapet k+i karena index ke-2 adalah k, sepanjang 1 karakter yaitu k dan karakter selanjutnya adalah i. sehingga hasil decodingnya adalah k+1
------------------------------------------------------
(0,0,k) → k (index 4)
(0,0,a) → a (index 3)
(2,1,i) → k + i (k index ke-2 dan i index ke-1)
- Pada encoding (4,3,e) bisa dapat decodingnya kak+e karena index ke-4 adalah k, sepanjang 3 karakter yaitu kak dan karakter selanjutnya adalah e. sehingga hasil decodingnya adalah kak+e
------------------------------------------------------
(0,0,k) → k (index 8)
(0,0,a) → a (index 7)
(2,1,i) → k + i (k index ke-6 dan i index ke-5)
(4,3,e) → kak+e (k index ke-4, a index ke-3, k index ke-2 dan e index ke-1)
- Pada encoding (8,1,-) bisa didapat decodingnya k karena index ke-8 adalah k, sepanjang 1 karakter yaitu k dan karakter selanjutnya tida ada. sehingga hasil decodingnya adalah k
- Jadi Decoding keseluruhannya adalah kakikakek.
No comments:
Post a Comment