Metode Kompresi LZ78

Adi SuheryadiPasca Sarjana Teknik Informatika

Universitas Telkom

Ide Kompresi LZ78 Karakteristik Encode Decode Rasio Kompresi Kesimpulan

Poin Persentasi

Menggunakan metode kamus (dictionary) Kamus merupakan daftar yang tak terbatas menggunakan token (i,s)

o i : index/posisi pada dictionaryo s : simbol input

Ide Kompresi LZ78

Bersifat lossless dictionary berupa daftar yg tak terbatas dari

frasa yang dilihat sebelumnya Mempunyai kemampuan menyimpan entries

secara permanen Mengembangkan entitas selama proses

encoding

Karakteristik

Encode LZ78

Algoritma Encode

Psudocodekamus kosong; prefix kosong; indexkamus 1;while(masih ada karakter){

kar next karakter; if(kar+ karakter ada di kamus) prefix prefix++ ; else { if(Prefix tidak ada) Codeindex 0 ; else Codeindex index kamus; Output: (Codeindex, kar) ;

insertInDictionary( ( indexkamus, Prefix + kar) ); Indexkamus++ ; Prefix kosong; }

}if(Prefix tidak kosong){

Codeindex indexkamus; Output: (CodeIndex , ) ;}

string ABBCBCABABCAABCAAB

Contoh Encode

Encode : (0,A)(0,B)(2,C)(3,A)(2,A)(4,A)(6,B)

string input : AAAAAAAAA

Contoh Encode (2)

Encode : (0,A)(1,A)(2,A)(3, )

Number of Bit Transmisi

Merubah hasil encode menjadi kode biner

Buat index terlebih dahulu: Compressed string( codewords): (i1, s1) (i2, s2) ... (in, sn)

Codeword index 1 2 ... n Konversi codeword ke biner dengan melihat tabel,

dimana: Melihat index untuk menghitung bit Melihat codeindex untuk menetukan biner

Contoh Number of Bit Transmisi

Data : ABBCBCABABCAABCAAB

Number of bits = Total number of characters * 8

= 18 * 8

= 144 bits

Codewords: (0, A) (0, B) (2, C) (3, A) (2, A) (4, A) (6, B)

Codeword index 1 2 3 4 5 6 7

Contoh Number of Bit Transmisi (2)

Codeword (0, A) (0, B) (2, C) (3, A) (2, A) (4, A) (6, B)index 1 2 3 4 5 6 7Bits: (1 + 8) + (1 + 8) + (2 + 8) + (2 + 8) + (3 + 8) + (3 + 8) + (3 + 8) = 71 bits

Hasil : 0A0B10C11A010A100A110B

Decode LZ78

Algoritma Decode

Psudocode

kamus kosong ; kamusIndex 1 ;while(masih ada token){

CodeWord next CodeWord;kar karakter cocokan dari kamus ;if(CodeWord = = 0)

String kosongkan;else String string index CodeWord di kamus ;Output: String + kar;

kamusIndex++;}

Contoh DecodeData encode : (0, A) (0, B) (2, C) (3, A) (2, A) (4, A) (6, B)

Hasil decode : ABBCBCABABCAABCAAB

Number of Bit Transmisi

Ubah biner menjadi codeword ASCII Lakukan seperti melakukan decode

Pesan : 0A 0B 10C 11A 010A 100A 110B

Menjadi : (0,A) (0,B) (2,C) (3,A) (2,A) (4,A) (6,B)

Rumusan Rasio Kompersi:

Data : ABBCBCABABCAABCAAB 100%-(71/144 x 100)= 50,7 %

Rasio Kompresi

Perbaikan LZ77 dan LZSS LZ78 mempunyai

kemampuan menyimpan entries secara permanen dan mengembangkan selama proses encoding

LZ78 berbeda dg LZ77 dan LZSS hanya menggunakan pasangan (i,s)o i : index/posisi pada dictionaryo s : simbol input

Jika pasangan (0,s) muncul indikasi simbol s tdk ada dlm dictionary dan harus ditambahkan

Kesimpulan

1. Persentasi : 082ICS202_17_LZ_Compression.ppt2. Persentasi : Commpression Algorithm LZ-Varian.ppt3. http://en.wikipedia.org/wiki/LZ77_and_LZ78

Referensi