BAB 2 KAJIAN TEORITIS
2.1.
Deskripsi Teori Untuk memberikan dasar penulisan makalah ini, terlebih dahulu pada bagian ini
akan digambarkan secara ringkas konsep-konsep kompresi data, mulai dari definisi sampai pada beberapa teorema yang diperlukan untuk tujuan tersebut. 2.1.1. Data Data adalah representasi dari fakta, konsep, atau instruksi dalam format tertentu yang digunakan untuk komunikasi, interpretasi, atau di proses oleh manusia (Department of Defense Dictionary of Military and Associated
Terms,
http://www.its.bldrdoc.gov/fs-1037/dir-
010/_1401.htm). Data juga dapat diartikan suatu kumpulan angka, karakter, gambar yang sebelumnya tidak memiliki arti apa-apa hingga diproses
menjadi
informasi
melalui
pemrosesan
data
(http://en.wikipedia.org/wiki/Data).
2.1.2. Kompresi Data Kompresi data adalah proses perubahan dari aliran data (input /sumber data/data asli) ke suatu aliran data / output yang memiliki ukuran lebih kecil ( David Solomon, 2004, P. 1).
7 2.1.2.1 Tipe Kompresi Data Dalam bidang kompresi data, secara umum memiliki dua tipe kompresi data, yaitu : 1. Lossless Adalah tipe kompresi data yang memiliki sifat data sumber (asli) dan data setelah di kompresi kemudian dilakukan dekompresi kembali akan memiliki struktur file yang sama. Umumnya tipe data ini digunakan untuk kompresi data berbasis teks (Nelson, 2000,P. 13).
Gambar 2.1 Ilustrasi Tipe Kompresi Lossless
2. Lossy Adalah tipe kompresi data yang memiliki sifat data sumber (asli) dan data setelah dikompresi apabila dilakukan dekompresi kembali hasilnya tidak sesuai dengan data sumber-nya. Umumnya tipe data ini digunakan untuk kompresi data bertipe image (Nelson, 2000,P.14).
Gambar 2.2 Ilustrasi Tipe Kompresi Lossy
8 2.1.3. Dictionary Methods Kompresi
berbasis
metode
kamus
/
dictionary
tidak
menggunakan metode statistika, atau menggunakan kode-kode yang bervariasi ukurannya, melainkan dengan cara memilih kumpulan simbol / string, dan merubah setiap kumpulan/string sebagai token menggunakan kamus yang didefinisikan (David Solomon, 2004, P. 165).
2.1.4. Lempel-Ziv Algorithm Cara kerja algoritma ini yaitu dengan menggunakan bagian sebelumnya dari aliran input sebagai kamus / dictionary. Dan membandingkan aliran data yang sedang di encode dengan data yang ada di kamus / dictionary yang baru dimasukkan, cara kerja algoritma ini dikenal dengan sliding windows (David Solomon, 2004, P. 169). Dengan kata lain algoritma ini bertujuan merubah input data yang akan di kompresi menjadi blok-blok data yang tidak berulang (redundant) bersamaan dengan membangun dictionary blok-blok data.
Berikut
penulis sampaikan ilustrasi dari algoritma lempel-ziv ini : Langkah Algoritma : 1.
Memulai
inisialisasi
dictionary
untuk
mencakup
panjang blok yang terdapat dalam input data. 2.
Mencari blok terpanjang W yang muncul dalam dictionary.
3.
Merubah W berdasarkan indeks dalam dictionary.
9 4.
Masukkan W diikuti oleh simbol pertama dalam blok berikutnya ke dalam dictionary.
5.
Ulangi langkah ke-2.
Gambar 2.3 Langkah kerja Algoritma Lempel Ziv
2.1.5. LZ77 Menurut Arturo San Emeterio Campos dalam artikelnya ( http://www.arturocampos.com/ac_lz77.html
).
dibutuhkan dalam algoritma kompresi ini adalah : 1. Input Stream Kumpulan karakter yang akan di enkripsi. 2. Character Elemen dasar pada input stream.
Komponen
yang
10 3. Look-ahead buffer Kumpulan karakter yang belum di enkripsi, setelah token. 4. Search Buffer Kumpulan karakter yang telah di enkripsi, sebelum token. 5. Token Berisi kumpulan dari (offset, length dan next symbol). Lebih jelasnya penulis akan jabarkan di bawah ini. Prinsip kompresinya adalah menerima input stream data yang akan di kompres / enkripsi dan akan dibaca oleh search buffer dari kanan ke kiri seakan membentuk jendela yang bergerak (sliding windows) dari kanan ke kiri. Selama di search buffer, algoritma akan membaca per-bit karakter dan merekamnya ke dalam format token. Format-format token inilah yang disebut dengan dictionary pada algoritma kompresi ini. Sebagai contoh, kita mempunyai data yang akan di kompresi sebagai berikut : “jalan syahdan macet”. ( tanpa tanda kutip dua, serta spasi
di
ilustrasikan
dengan
symbol
‘_’
),
ilustrasi
berikut
menggambarkan bagaimana algoritma ini bekerja. Kolom sebelah kiri yang disebut search buffer dan kolom sebelah kanan disebut look-ahead buffer. Selama proses pembacaan input stream, token akan selalu mencatat : Offset : jarak bit ke symbol yang sama Length : Jumlah symbol yang sama sesudah offset. Next Symbol : symbol sesudah panjang length.
11 jalan_syahdan_macet
Î (0,0,”j”)
j alan_syahdan_macet
Î (0,0,”a”)
ja lan_syahdan_macet
Î (0,0,”l”)
jal an_syahdan_macet
Î (2,1,”n”)
jalan _syahdan_macet jalan_ syahdan_macet jalan_s yahdan_macet jalan_sy ahdan_macet jalan_syah dan_macet jalan_syahd an_macet jalan_syahdan_ macet jalan_syahdan_m acet jalan_syahdan_ma cet jalan_syahdan_mac et
Î (0,0,”_”) Î (0,0,”s”) Î (0,0,”y”) Î (5,1,”h”) Î (0,0,”d”) Î (8,3,”m”) Î (0,0,”m”) Î (4,1,”c”) Î (0,0,”j”) Î (0,0,”e”)
jalan_syahdan_mace t
Î (0,0,”t”)
jalan_syahdan_macet
Î (0,0,”ǿ”)
Kemudian hasil token-token tersebut di simpan dan akan digunakan untuk men-dekompresi kembali ke data utuh.
12 2.1.6. Markov-Chain Apabila suatu kejadian tertentu dari suatu rangkaian eksperimen tergantung dari beberapa kemungkinan kejadian, maka rangkaian eksperimen tersebut disebut proses stokastik ( Judge G.G and E.R Swanson, 1981, P.9) . Proses stokastik dengan waktu diskrit serta properti markov didefinisikan sebagai rantai markov. Misalkan suatu proses stokastik { Xn, n=0,1,2,… } apabila Xn = I, maka proses dikatakan berada pada state –i. Misalkan apabila proses berada pada state-i maka akan berpindah ke state-j dengan peluang pij, dimana pij tidak tergantung pada n. Proses Xn dinamakan rantai markov jika,
P ( X n +1 = j / X n = i, X n −1 = i n −i ,..., X 1 = i1 , X 0 = i0 ) = P ( X n +1 = j / X n = i )
(2.1)
Untuk semua i0, i1, …, in-1,i,j dan semua n > 0. Maka proses stokastik tersebut disebut Markov Chain Stationer. Persamaan (2.1) dapat diinterpretasikan sebagai berikut : Untuk suatu rantai markov, peluang bersyarat kejadian yang akan datang Xn+1, hanya tergantung pada kejadian sekarang Xn. Hal ini disebut markovian. Karena peluang dimulai
non-negatif dan proses harus
melakukan transisi ke berbagai state, maka :
pijµ 0, i,j µ 0 ;
∑ pij = 1, i = 0,1,2,...
(2.2)
j =1
Untuk selanjutnya,
mengingat aplikasi rantai markov pada
13 penulisan makalah ini untuk state yang terhingga, maka penulis hanya membatasi pada rantai markov stationer dengan state terhingga. Rantai markov dikatakan homogen jika ;
P ( X n +1 = j / X n = i) = P( X i = j / X 0 = i )
(2.3)
Untuk semua n,i dan j . Untuk selanjutnya akan di asumsikan bahwa suatu rantai markov adalah homogen. Probabilitas P ( X n +1 = j / X n = i ) dinamakan probabilitas transisi, dan selanjutnya akan disebut pij . Peluang transisi pij dapat dituliskan dalam bentuk matriks transisi P :
p11 p P = 21 ... p r1
p12
...
p 22
...
...
...
pr 2
...
p1r p2r ... p rr
(2.4)
Karena unsur-unsur P adalah non-negatif dan jumlah peluang semua unsur pada setiap baris sama dengan 1, maka tiap baris adalah vektor peluang dan P adalah matriks stokastik. Matriks tersebut bersama state awal secara lengkap mendefinisikan suatu proses rantai markov. Dengan kata lain, apabila informasi tersebut diketahui, kita dapat menentukan kejadian. Misalkan pada step ke- n, dalam bahasa matriks hal ini dapat dijelaskan sebagai berikut. Misalkan w0 melambangkan vektor awal atau state awal, maka :
14 w0P = w1 w1P = w2 wn-1P = wn
(2.5)
2.1.7. PPM ( Prediction by Partial Matching )
Adalah model kompresi data menggunakan teknik statistik dengan metode berbasiskan konteks dan peramalan / prediksi (Solomon, 2004, P.134). Selanjutnya disebut PPM, model ini menggunakan sekumpulan simbol yang belum di kompresi untuk memprediksi simbol berikutnya dalam aliran data. Kemudian PPM ini secara umum dikelompokkan dalam 2 jenis model. Model berbasis statistik menghitung jumlah simbol yang telah di kompresi dan memberikan nilai probabilitas ke sekumpulan simbol tersebut. Asumsikan terdapat 1217 simbol yang telah di input, 34 diantaranya adalah huruf q, maka probabilitas huruf q hingga saat pointer membaca input adalah 34/1217. Apabila terdapat simbol q berikutnya, maka probabilitasnya berubah menjadi 35/t ( dimana t adalah total simbol yang telah di kompresi hingga saat ini ). Model berikutnya adalah berbasis statistikal konteks dimana probabilitas simbol S ditentukan tidak hanya berdasarkan frekuensi keluarnya simbol S, tetapi juga berdasarkan konteks yang keluar hingga saat ini. Sebagai contoh dalam kamus bahasa inggris, apabila simbol t pada saat pointer membaca, maka kemungkinan diikuti oleh simbol h adalah sekitar 30% . Di lain pihak pada digram yang tidak lazim, apabila
15 simbol x diikuti oleh simbol h PPM memberikan nilai probabilitas lebih kecil dibandingkan dengan th .
2.1.8. Hidden Markov Model
Adalah sebuah model statistik dimana sistem yang akan dijadikan model di asumsikan sebagai proses markov dengan parameter probabilitas yang belum diketahui, hal ini bertentangan dengan konsep Markov Chain sebelumnya dimana dapat memprediksi masa depan dengan satuan probabilitas yang telah diketahui. Oleh karena itu disebut dengan istilah hidden markov model (G.V Cormack and N.S. Horspool, 1987,p354). Lebih lanjut markov chain model ini di kelompokkan ke dalam directed graph dengan nilai probabilitas di setiap edge –nya. Pada data kompresi ini, markov model mempunyai tugas menentukan nilai probabilitas pada edge di graph serta menentukan struktur graph itu sendiri.
2.1.9. Entropy Encoding
Adalah skema penugasan kode-kode ke dalam simbol sehingga memiliki panjang kode yang sama dengan probabilitas dari jumlah simbolnya (http://en.wikipedia.org/wiki/Entropy_coding).
16 2.1.10. Binary Tree
Adalah struktur data berbentuk pohon dimana tiap node memiliki child paling banyak 2. Umumnya child nodes dikenal dengan Left dan Right (http://en.wikipedia.org/wiki/Binary_tree).
2.1.11. Patricia Trie
Patricia adalah kependekan dari Practical Algorithm to Retrieve Information Coded in Alphanumeric, juga dikenal dengan Radix Tree, Crit Bit Tree, atau binary decision diagram. Adalah bentuk sederhana dari Trie ( Data terstruktur ) yang sudah di kompres dengan cara menggabungkan
single-child-nodes
dengan
parent
(http://en.wikipedia.org/wiki/Patricia_trie).
2.1.12. Lempel-Ziv-Markov Chain-Algorithm (LZMA)
Adalah versi terbaru dari algoritma LZ77, dengan menggunakan markov chain dan entropy encoding ( Solomon, 2004, P.206). Metode algoritma ini menggunakan bagian stream input sebelumnya sebagai kamus yang akan digunakan dalam kompresi data algoritma ini. Encoder menerima input dari kanan ke kiri bersamaan dengan keseluruhan data yang akan di kompresi. Metode ini juga disebut dengan istilah sliding windows . Windows ini dibagi menjadi dua bagian, bagian sebelah kiri dinamakan search buffer dan sebelah kanan disebut look-ahead buffer, yang berisi teks yang akan di kompresi.
17 Secara garis besar penerapan Markov Chain dalam algoritma Lempel-Ziv ini dapat penulis jelaskan sebagai berikut.
Ilustrasi 1.
Pada suatu kasus data sumber dengan keluaran (output) X1,X2, … Xn. Di asumsikan probabilitas output pada saat n memiliki ketergantungan kepada output pada saat n-1 dan n-2 seperti pada markov chain. Kedua output sebelumnya dijadikan suatu model state Sn-1. Hal ini yang akan diterapkan pada saat sliding windows LZ77 digunakan untuk membuat probabilitas susunan-susunan data input.
Pada markov chain dibutuhkan sebuah model probabilitas untuk memprediksi state berikutnya. Pada kasus kompresi data,
nilai
probabilitas ini adalah bervariasi tergantung oleh waktu. Dengan kata lain, pada bidang kompresi data memiliki sifat :
Jumlah simbol sumber dan jumlah simbol yang telah di encode/kompresi bervariasi, dengan kata lain simbol-simbol yang di encode bergantung pada waktu.
Tidak membutuhkan nilai statistik probabilitas sejak awal, karena seiring dengan input sumber nilai probabilitas akan beradaptasi. Mengingat bahwa LZMA adalah pengembangan dari LZ77, maka
alasan penerapan Markov Chain ke dalam algoritma lempel ziv dikarenakan bahwa LZ77 adalah algoritma berdasarkan informasi ( information-theoritic ), apabila AEP (Asymptotic Equipartition Property)
18 adalah sumber datanya / input, maka panjang sliding windows yang didefinisikan sebagai w akan menampung string yang sama hingga panjang n* yang juga memiliki ketergantungan oleh w dan sumber statistik yang belum diketahui. Sehingga rata-rata jumlah bit per simbol sumber memenuhi L ≈ (log w) / n * .
Dengan asumsi markov source adalah sumber input-nya. Maka dapat dikatakan bahwa L mendekati conditional entropy H ( X | S ) sumbernya.
2.1.13. Teknologi .NET
Teknologi yang dikembangkan oleh Microsoft yang mempunyai arti memberikan pemakai akses ke informasi, file atau program, setiap tempat, setiap saat, setiap platform dan setiap perangkat. Pemakai tidak perlu tahu di mana informasi berada atau bagaimana cara memanggilnya ( John Connel, 2004. P.2 ).
2.1.14. C#
Bahasa pemograman berbasis objek terbaru dengan menggunakan teknologi .NET untuk membuat aplikasi berbasis windows, aplikasi form web, layanan web XML dan aplikasi mobile. C# dibangun di atas fondasi .NET Framework serta dibangun berdasarkan metode yang digunakan bahasa pemograman C dan C++ (Simon Robinson, 2004. P.12) .
19 2.1.15. Dokumen
Dalam dunia teknologi informasi, dokumen adalah sebuah file yang dihasilkan oleh aplikasi pengolah kata (word processor). Dokumen kini semakin beragam hingga dapat menampung grafik, chart dan objekobjek
lainnya
seperti
audio
video
(http://en.wikipedia.org/wiki/Document).
2.1.16. Keamanan Komputer
Dalam dunia teknologi informasi, keamanan adalah teknik untuk menjaga data yang tersimpan di dalam komputer agar tidak dapat di baca/buka
oleh
individu
yang
(http://www.webopedia.com/TERM/s/security.html).
tidak Berikut
berhak adalah
macam-macam teknik yang umumnya terdapat pada bidang keamanan komputer : 2.1.16.1.
Enkripsi
Penterjemahan suatu data menjadi kode-kode yang tidak dapat dibaca oleh pengguna. Untuk dapat membacanya kembali, maka pengguna membutuhkan kunci atau password yang dapat mendecrypt. Umumnya data yang tidak terenkripsi disebut plain text sedangkan data yang telah di enkripsi disebut cipher text (http://www.webopedia.com/TERM/e/encryption.html).
20 2.2.
Penelitian yang Relevan
Algoritma Lempel-Ziv sebelum tahun 2001 pernah dipakai tapi tidak menggunakan Markov-Chain, melainkan dengan LZW ( Lempel-Ziv-Welch) . Aplikasi program yang beredar umum di dunia teknologi informasi kita kenal dengan prorgam PKZIP, ZIP, RAR, GunZIP, PDF yang menggunakan algoritma LZW. Program aplikasi tersebut diatas menggunakan beberapa algoritma LZW. Oleh karena itu, penulis mengacu pada penelitian tersebut, dan penulis akan menerapkan algoritma baru yaitu LZMA, Lempel-Ziv-Markov Chain-Algorithm.
2.3.
Kerangka Berpikir
Dengan menggunakan teori-teori yang telah penulis sebutkan, maka akan didapatkan suatu program aplikasi kompresi data dengan menggunakan teori yang bersangkutan untuk tujuan efisiensi waktu pengiriman data melalui media internet.
