[TTG4J3] KODING DAN KOMPRESI
Oleh : Ledya Novamizanti Astri Novianty Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom
Teknik Dictionary memanfaatkan kelompok simbol, kata, dan frase yang dinyatakan dengan indeks. Pada teknik ini dibuat daftar (list) pola simbol (pattern) yang umum muncul. Pattern di‐encode dengan mengirimkan nomor indeksnya ke dalam list. Indeks digunakan dalam transmisi data, dan penerima menerjemahkan kembali ke bentuk aslinya dengan menggunakan dictionary yang sama dengan pengirim. [TTG4J3] Koding dan Kompresi
Dictionary Technique
2
Teknik ini cocok untuk source berupa teks dan instruksi komputer. Teknik Dictionary dapat berupa statis (Static Dictionary) atau dinamis (Dynamic Dictionary)
[TTG4J3] Koding dan Kompresi
Dictionary Technique
3
Tetap sama sepanjang proses encoding Akronim : CEO, ASCII Singkatan(Abbreviation) : dr, Bdg Coined abbreviation (M—male, #$—load instruction)
List pola simbol yg paling sering Æ dan codeword‐nya n‐gram Æ pola n deretan simbol yg sering digunakan (mis. tri‐gram dlm text Inggris: the, que, neu, ome, …)
Tidak efisien untuk semua situasi (language spesific, domain spesific)
Masalah parsing word [TTG4J3] Koding dan Kompresi
Dictionary Technique
4
Dibangun dan dimodifikasi secara dinamis selama proses encoding dan decoding Dibangun dari pola umum yang ditemukan di input Pola dikodekan dg index, offset atau address pd dictionary Kecepatan ditentukan oleh ukuran dictionary dan teknik pencarian Kebanyakan teknik didasarkan pd teori dari Jacob Ziv dan Abraham Lempel. [TTG4J3] Koding dan Kompresi
Dictionary Technique
5
Aplikasi utk Kompresi: LZ77: ARJT, LHarcT, PKZipT UC2T
LZ78/LZW: ARCT, PAKT, UNIXT, $ Compress, gif
[TTG4J3] Koding dan Kompresi
Dictionary Technique
6
Pendahulu LZW adalah LZ77 dan LZ78 yang dikembangkan oleh Jacob Ziv dan Abraham Lempel pada tahun 1977 dan 1978. Terry Welch mengembangkan teknik tersebut pada tahun 1984. Algoritma LZW adalah versi aplikasi dari LZ78 dg modifikasi signifikan, yaitu mengurangi output encoder dari pasangan ke bilangan tunggal (single) tanpa perlu mentransmisikan simbol (elemen kedua dari pasangan pd LZ78) [TTG4J3] Koding dan Kompresi
Dictionary Technique
7
Dictionary diinisialisasi dengan semua simbol dari sumber input, sehingga jika simbol muncul pertama kali dalam pesan, sudah memiliki sebuah entri dalam dictionary.
LZW mengeluarkan output codeword untuk string yang sudah ada dalam dictionary. Jika ditemukan string yang tidak ada dalam dictionary, tambahkan string ini dan output‐kan codeword untuk substring yang diketahui dari string [TTG4J3] Koding dan Kompresi
Dictionary Technique
8
1. 2. 3. 4.
Masukkan semua karakter ke dalam dictionary s ← karakter pertama pada stream karakter c ← karakter berikutnya pada stream karakter Apakah string (s + c) ada dalam dictionary ? Jika ya, maka s ←s + c. Jika tidak, maka : Output codeword dari s Tambahkan string (s + c) ke dalam dictionary iii. s ← c i. ii.
5.
Masih ada karakter berikutnya dalam stream karakter ? Jika ya, maka kembali ke langkah 3. Jika tidak, maka output codeword dari s, lalu terminasi proses (stop) [TTG4J3] Koding dan Kompresi
Dictionary Technique
9
Misal dictionary diinisialisasi dengan semua karakter dasar yang ada pada tabel ASCII. Tentukan hasil encoding dari pesan thisisthe menggunakan algoritma LZW
[TTG4J3] Koding dan Kompresi
Dictionary Technique
10
ASCII Table
[TTG4J3] Koding dan Kompresi
Dictionary Technique
11
[TTG4J3] Koding dan Kompresi
Dictionary Technique
12
1. 2. 3. 4.
5.
Masukkan semua karakter dan kode ke dalam dictionary c ← kode pertama dari stream kode; Output string c s ← c; c ← kode berikutnya dari stream kode Apakah string c ada dalam dictionary ? Jika ya, maka : i. Output string c ii. Tambahkan string (s +firstsymbol(c)) ke dalam dictionary Jika tidak, maka output string (s +firstsymbol(s)), dan tambahkan string tersebut ke dalam dictionary Masih ada kode berikutnya dalam stream kode ? Jika ya, maka kembali ke langkah 3. Jika tidak, maka terminasi proses (stop) [TTG4J3] Koding dan Kompresi
Dictionary Technique
13
Misal dictionary diinisialisasi dengan semua karakter dasar yang ada pada tabel ASCII. Diketahui deretan kode keluaran encoder adalah 116 104 105 115 258 256 101. Tentukan hasil decodingnya menggunakan algoritma LZW
[TTG4J3] Koding dan Kompresi
Dictionary Technique
14
[TTG4J3] Koding dan Kompresi
Dictionary Technique
15
Diketahui source {c, a, b, o, w}. Pesan yang akan di‐encode adalah: wabbacwabbacwabbacwabbacwoocwoocwoo Lakukan encoding dan decoding menggunakan LZW
[TTG4J3] Koding dan Kompresi
Dictionary Technique
16
Diketahui S = {a, r, s, y, $} Encode string berikut: a$ray$sarray$yassaray menggunakan LZW
[TTG4J3] Koding dan Kompresi
Dictionary Technique
17
1.
Adam Drozdek, Elements of Data Compression, Thomson Brooks/Cole, 2002
2.
Khalid Sayood, Introduction to Data Compression, Academic Press, 2000.
3.
T.M. Cover, J.A. Thomas, Elements of Information Theory, John Wiley&Sons.
4.
M. Nelson and J.‐L. Gailly. The Data Compression Book. M&T Books, CA, 1996.
5.
D. Salomon. Data Compression: The Complete Reference. Springer, 1998.
[TTG4J3] Koding dan Kompresi
Dictionary Technique
18
