BAB 2
TINJAUAN PUSTAKA
2.1 Definisi Kompresi Data dan Klasifikasi Algoritma Kompresi Data
Kompresi data adalah proses mengkodekan informasi menggunakan bit atau information-bearing unit yang lain yang lebih rendah daripada representasi data yang tidak terkodekan dengan suatu sistem encoding tertentu. Menurut Ida Mengyi Pu (2006:1) kompresi data adalah ilmu atau seni merepresentasikan informasi dalam bentuk yang lebih compact. Sedangkan David Salomon (2007:2) mengatakan bahwa data kompresi adalah proses mengkonversikan sebuah input data stream (stream sumber, atau data mentah asli) menjadi data stream lainnya (bitstream hasil, atau stream yang telah terkompresi) yang berukuran lebih kecil.
Kompresi data adalah proses yang dapat mengubah sebuah aliran data masukan (sumber atau data asli) ke dalam aliran data yang lain (keluaran atau data yang dimampatkan) yang memiliki ukuran yang lebih kecil (Salomon, 2007). Kompresi data adalah (dalam bidang ilmu komputer, ilmu pengetahuan dan seni) sebuah penyajian informasi ke dalam bentuk yang lebih sederhana (Pu, 2006). Dalam ilmu komputer dan teori informasi, kompresi data atau source coding adalah proses meng-encode informasi dengan menggunakan lebih sedikit bit dari suatu sumber yang belum di-encode melalui penggunaan skema pengkodean yang spesifik
Tujuan dari kompresi data adalah untuk merepresentasikan suatu data digital dengan sesedikit mungkin bit, tetapi tetap mempertahankan kebutuhan minimum untuk membentuk kembali data aslinya. Data digital ini dapat berupa text, gambar, suara, dan kombinasi dari ketiganya, seperti video. Contoh kompresi sederhana yang biasa kita lakukan misalnya adalah menyingkat kata-kata yang sering digunakan tapi sudah memiliki konvensi umum. Misalnya: kata “yang” dikompres menjadi kata “yg”.
Universitas Sumatera Utara
Untuk membuat suatu data menjadi lebih kecil ukurannya daripada data asli, diperlukan tahapan-tahapan (algoritma) untuk mengolah data tersebut. Menurut Thomas H. Cormen
(2001:2) algoritma adalah suatu prosedur komputasi yang
didefinisikan secara baik, membutuhkan sebuah atau sekumpulan nilai sebagai input, dan menghasilkan sebuah atau sekumpulan nilai sebagai output. Dalam algoritma kompresi data, tidak ada algoritma yang cocok untuk semua jenis data. Hal ini disebabkan karena data yang akan dimampatkan harus dianalisis terlebih dahulu, dan berharap menemukan pola tertentu yang dapat digunakan untuk memperoleh data dalam ukuran yang lebih kecil. Karena itu, muncul banyak algoritma-algoritma kompresi data.
Kompresi data sangat populer sekarang ini karena dua alasan yaitu (Salomon, 2007) : 1. Orang – orang lebih suka mengumpulkan data. Tidak peduli seberapa besar media penyimpanan yang dimilikinya. Akan tetapi cepat atau lambat akan terjadi overflow. 2. Orang – orang benci menunggu waktu yang lama untuk memindahkan data. Misalnya ketika duduk di depan komputer untuk menunggu halaman Web terbuka atau men-download sebuah file.
Defenisi Algoritma : 1. Algoritma adalah urutan langkah – langkah berhingga untuk memecahkan masalah logika atau matematika 2. Algoritma adalah logika, metode dan tahapan (urutan) sistematis yang digunakan untuk memecahkan suatu permasalahan 3. Algoritma adalah urutan langkah – langkah logis penyelesaian masalah yang disusun secara sistematis dan logis.
Kriteria Algoritma dan Aplikasi Kompresi Data - Kualitas data hasil enkoding: ukuran lebih kecil, data tidak rusak untuk kompresi lossy.
Universitas Sumatera Utara
- Kecepatan, ratio, dan efisiensi proses kompresi dan dekompresi - Ketepatan proses dekompresi data: data hasil dekompresi tetap sama dengan data sebelum dikompres (kompresi loseless)
Secara garis besar, terdapat 2 penggolongan algoritma kompresi data: kompresi lossy, dan kompresi lossless.
a.
Kompresi Lossy Algoritma kompresi dikatakan lossy atau disebut juga irreversible jika tidak dimungkinkan untuk membentuk data asli yang tepat sama dari data yang sudah dikompresi. Ada beberapa detail yang hilang selama proses kompresi. Contoh penggunaan algoritma lossy seperti pada data gambar, suara dan video. Karena cara kerja sistem pengelihatan dan pendengaran manusia yang terbatas, beberapa detail dapat dihilangkan, sehingga didapat data hasil kompresi yang seolah-olah sama dengan data asli.
b.
Kompresi Lossless Algoritma kompresi dikatakan lossless atau disebut juga reversible jika dimungkinkan untuk membentuk data asli yang tepat sama dari data yang sudah dikompresi. Tidak ada informasi yang hilang selama proses kompresi dan dekompresi. Teknik ini digunakan jika data tersebut sangat penting, jadi tidak di mungkinkan untuk menghilangkan beberapa detail. Untuk kompresi Lossless, berdasarkan cara mereduksi data yang akan dikompresi, terbagi lagi menjadi 2 kelompok besar algoritma:
(i).
Algoritma berbasis Entropi Algoritma berbasis Entropi, atau disebut juga berbasis statistik, menggunakan model statistik dan probabilitas untuk memodelkan data, keefisienan kompresi bergantung kepada berapa banyak karakter yang digunakan dan seberapa besar distribusi probabilitas pada data asli. Contoh algoritma yang berbasis entropi adalah: Huffman Coding, Adaptive Huffman, dan Shannon Fano, Run Length,Burrows wheeler transform
Universitas Sumatera Utara
(ii). Algoritma berbasis dictionary Algoritma berbasis dictionary, bekerja dengan cara menyimpan pola masukan sebelumnya, dan menggunakan index dalam mengakses pola tersebut jika terdapat perulangan. Contoh algoritma yang berbasis dictionary adalah: LZ77, LZ78, LZW, DEFLATE, dan LZMA.
Dalam dunia komputer dan internet, pemanpatan file digunakan dalam berbagai keperluan jika ingin membackup data tidak perlu menyalin semua file aslinya, dengan memampatkan (mengecilkan ukurannya) file tersebut terlebih dahulu maka kapasitas tempat penyimpanan yang diperlukan akan menjadi lebih kecil. Jika sewaktu-waktu data tersebut diperlukan, baru dikembalikan lagi ke file aslinya
2.2 Transformasi Burrows Wheeler (Burrows Wheeler Transform)
Michael Burrows dan David Wheleer mengeluarkan sebuah laporan penelitian pada tahun 1994 yang berisi mengenai pekerjaan yang telah mereka lakukan di Digital System ResearchCenter yang terletak di Palo Alto, California. Makalah mereka yang berjudul “A block-sorting Lossless data compression Algorithm” menyajikan sebuah algoritma kompresi data berdasarkan pada suatu tranformasi. Tranformasi ini pertamakali ditemukan oleh David Wheeler pada tahun 1983 ketika ia bekerja di AT&T Bell Laboratories yang sebelumnya dipublikasikan. Sementara makalah yang dikemukakan membahas algoritma yang menyeluruh mengenai kompresi dan dekompresi, namun sesungguhnya inti yang terkandung dalam makalah tersebut adalah pembahasan mengenai metode Burrows-Wheeler Transformatio (BWT). (Nelson,1996)
Menurut M.Burrows dan D.J.Wheeler (1994),cara kerja transformasi BurrowsWheeler ini tidak memproses data masukan secara antrian, tapi memproses langsung satu blok data teks sebagai satuan. Hal ini dimulai dari gagasan diterapkannya transformasi terhadap blok data teks menjadi suatu bentuk baru yang tetap mengandung karakter yang sama, namun lebih mudah untuk dimampatkan menggunakan algoritma kompresi yang sederhana. Tranformasi ini cenderung untuk mengelompokkan karakter secara bersama-sama sehingga peluang untuk menemukan
Universitas Sumatera Utara
karakter yang sama secara berurutan akan meningkat.Menurut M.Burrows and D.J.Wheeler (1994), Tranformasi ini memiliki sifat reversible yaitu dapat mengembalikan data teks yang telah ditransformasikan kebentuk yang sama persis dengan data asalnya. Dengan kata lain BWT adalah algoritma transformasi yang memproses sebuah blok data teks dan menyusunnya dengan algoritma pengurutan, sehingga hasilnya adalah blok data yang sama dengan sebelumnya, hanya saja urutannya yang berbeda. Proses dari algoritma BWT adalah mentransformasikan sebuah string S yang memiliki N karakter dengan cara melakukan rotasi (cyclic shift) atau permutasi sebanyak N kali setelah itu mengurutkan setiap string hasil permutasi, kemudian mengambil setiap karakter terakhir dari setiap string hasil permutasi yang telah diurutkan.
Sebuah string baru L akan terbentuk dari karakter-karakter ini, jadi karakter L adalah karakter terakhir dari string rotasi yang telah diurutkan. Pada saat string L dibentuk akan diperoleh pula indek I yang menunjukan posisi string yang asli dalam daftar rotasi string yang telah diurutkan. Hal yang luar biasa adalah ditemukannya algoritma yang efisien untuk membentuk kembali string asli S dengan hanya mengetahui string L dan indeks I. Operasi pengurutan yang dilakukan akan membuat string hasil rotasi yang memiliki karakter awal yang sama menjadi berdekatan. Mengingat karakter awal F dari setip rotasi string yang telah terurut merupakan karakter yang berdekatan dengan karakter terakhir, maka urutan karakter di L akan mirip dengan string F dan dapat dperkirakan string L akan lebih mudah dimanpaatkan dengan menggunakan algoritma yang sesuai.
Prinsip kerja sebagai berikut :misalkan input text yaitu”BANANA” Langkah 1. Mengurutkan rotasi String S=”BANANA”, jumlah input text 6,N = 6; Membentuk matriks M yang memiliki ordo N x N yang elemennya adalah karakter dan barisnya adalah merupakan rotasi setiap permutasi (cyclic shifts) dari string S yang terurut secara abjad (lexicographical). Salah satu dari baris matriks M adalah merupakan string asli S sedangkan I adalah indeks yang menunjukan urutan baris untuk string asli dalam matriks M dengan penomoran dimulai dari nol. Berikut ini merupakan gambaran dari konsep matriks M :
Universitas Sumatera Utara
N
0
1
2
3
4
5
N
0
1
2
3
4
5
0
B
A
N
A
N
A
0
A
B
A
N
A
N
1
A
N
A
N
A
B
1
A
N
A
B
A
N
2
N
A
N
A
B
A
2
A
N
A
N
A
B
3
A
N
A
B
A
N
3
B
A
N
A
N
A
4
N
A
B
A
N
A
4
N
A
B
A
N
A
5
A
B
A
N
A
N
5
N
A
N
A
B
A
Pengurutan
Gambar 2.1 Pengurutan Rotasi
Langkah 2. Ambil karakter terakhir dari rotasi Berdasarkan konsep matriks ini, maka string L dapat dibentuk dari kolom terakhir matriks M, yaitu karakter-karakter L[0], …, L[N-1] sama dengan M[0, N-1], …, M[N1, N-1], pada contoh sebelumnya, string L yang dihasilkan adalah ‘NNBAAA’ dengan indeks I = 4. Jadi dengan kata lain, hasil dari transformasi ini adalah pasangan L dan I L
seperti yang terlihat dibawah ini :
I
N
0
1
2
3
4
5
0
A
B
A
N
A
N
1
A
N
A
B
A
N
2
A
N
A
N
A
B
3
B
A
N
A
N
A
4
N
A
B
A
N
A
5
N
A
N
A
B
A
Gambar 2.2 Hasil Rotasi Jadi hasil yang diperoleh dari input text “BANANA” yaitu L=“NNBAAA” I=”3” Algoritma dasar Burrow Wheler Tranform Encoding : 1. Sort the N input characters using the preceding characters as the sort key, create permuted array P [ 1 . . . N]
Universitas Sumatera Utara
2. Output the position in L that contains the first character from the compressed file 3: Output the permuted array P Pseudocode : function BWT (string s) create a table, rows are all possible rotations of s sort rows alphabetically return (last column of the table) function inverseBWT (string s) create empty table repeat length(s) times insert s as a column of table before first column of the table // first insert creates first column sort rows of the table alphabetically return (row that ends with the 'EOF' character)
Pembalikkan Transformasi Dalam pembalikkan dari trasformasi burrows wheeler diperlukan pasangan L dan I yang akan digunakan sebagai masukan untuk membentuk string asli S sepanjang N karakter dengan langkah – langkah sebagai berikut: 1. Membentuk karakter pertama dari rotasi Langkah ini akan membentuk kolom pertama F dari matriks M. Hal ini dapat dilakukan dengan cara mengurutkan karakter – karakter string L membentuk string F. Mengingat setiap kolom matriks M merupakan permutasi dari string asli S maka baik L maupun F juga merupakan permutasi dari string S.Oleh karena string F adalah kolom pertama dari matriks M maka setiap karakter dalam F juga terurut. Maka string F yang diperoleh yaitu F=‘AAABNN 2. Membentuk kembali string asli S Tahap ini mengenai pembentukkan kembali string asli S berdasarkan string L, indeks dan string F
yang telah diperoleh pada langkah sebelumnya. Indeks I adalah
merupakan kunci yang memungkinkan string asli S dibentuk kembali karena I menunjukkan karakter pertama dari string asli. Semenjak permutasi blok data teks telah diurut secara lexicograpical, sehingga karakter – karakter pada kolom pertama
Universitas Sumatera Utara
dan kolom terakhir dari blok data tersebut memiliki urutan posisi yang sama pula. Berdasarkan sifat yang dimiliki oleh blok data teks inilah maka karakter kedua dan seterusnya dari string asli S dapat diketahui. Berikut ini merupakan gambaran dari proses pembentukkan string asli S berdasarkan string L,F, dan indeks I baris
F
T
L
0
A
3
N
1
A
4
N
A
5
B
B
2
A
N
0
A
1
A
2 I
3
indeks
4 5
N
Gambar 2.3 Proses Pembentukkan string asli S.
Dalam tahapan proses ini akan diperoleh satu vektor tranformasi T yaitu suatu array yang setiap elemennya menunjukkan korelasi atau pemetaan dari elemen-elemen string F ke string L secara berkesinambungan. Pemetaan dari string F ke L dilakukan sampai seluruh elemen F dipetakan ke L. Langkah ini akan diulang sampai seluruh elemen F dipetakan. Berdasarkan tahapan proses tersebut maka string asli S dapat disusun kembali. Dibawah
ini proses pembalikkan transformasi
sorting
dengan diketahui
L=”NNBAAA” dan I=3 sebagai berikut :
Tabel 2.1 Pembalikkan transformasi berdasarkan pengurutan Add 1
Sort1
Add2
Sort2
N
A
NA
AB
N
A
NA
AN
B
A
BA
AN
A
B
AB
BA
A
N
AN
NA
A
N
AN
NA
Universitas Sumatera Utara
Add3
Sort3
Add4
Sort4
NAB
ABA
NABA
ABAN
NAN
ANA
NANA
ANAB
BAN
ANA
BANA
ANAN
ABA
BAN
ABAN
BANA
ANA
NAB
ANAB
NABA
ANA
NAN
ANAN
NANA
Add5
Sort5
Add6
Sort6
NABAN
ABANA
NABANA
ABANAN
NANAB
ANABA
NANABA
ANABAN
BANAN
ANANA
BANANA
ANANAB
ABANA
BANAN
ABANAN
BANANA
ANABA
NABAN
ANABAN
NABANA
ANANA
NANAB
ANANAB
NANABA
Hasil diperloeh =”BANANA” dengan melihat indeks I=”3” dari hasil sorting
2.2.1 Block Size (Ukuran Blok)
Burrrows Wheeler Transform merupakan algoritma blok sorting, tetapi transfomasi tidak tergantung atas ukuran dari blok, Burrows Wheeler Transfrom dapat digunakan pada blok dari berbagai ukuran namun semakin besar blok dibutuhkan banyak memori untuk menangani blok dan rotasinya. Jadi dibatasi dalam ukuran blok dengan ukuran yang dipakai 14096 byte karena itu dapat ditangani oleh kebanyakan komputer modern saat ini(Dipperstein,2009).
2.3. Algoritma Run Length Algoritma Run Length digunakan untuk memampatkan data yang berisi karakter-karakter berulang. Saat karakter yang sama diterima secara berderet empat kali atau lebih (lebih dari tiga), algoritma ini mengkompres data dalam suatu tiga karakter berderetan. Algoritma Run Length paling efektif pada file-file grafis, dimana biasanya berisi deretan panjang karakter yang sama.(Herry dan Yessi,1999).
Universitas Sumatera Utara
Metode yang digunakan pada algoritma ini adalah dengan mencari karakter yang berulang lebih dari 3 kali pada suatu file untuk kemudian diubah menjadi sebuah bit penanda (marker bit) diikuti oleh
sebuah bit yang memberikan
informasi jumlah karakter yang berulang dan kemudian ditutup dengan karakter yang dikompres (Herry dan Yessi,1999), yang dimaksud dengan bit penanda
disini
adalah deretan 8 bit yang membentuk suatu karakter ASCII. Jadi jika suatu file mengandung karakter yang berulang, misalnya AAAAAAAA atau dalam biner 01000001 sebanyak 8 kali , maka 00001000 01000001. Dengan
data tersebut dikompres menjadi 11111110
demikian kita dapat menghemat
sebanyak 5
bytes.Agar lebih jelas algoritma Run Length dapat dinyatakan sebagai berikut : Deretan data sebelah kiri merupakan deretan data pada file asli, sedangkan deretan data sebelah kanan merupakan deretan data hasil pemampatan dengan algoritma Run Length. Langkah-langkah yang dilakukan adalah : 1. Lihat apakah terdapat deretan karakter yang sama secara berurutan lebih dari tiga karakter, jika memenuhi lakukan pemampatan. Pada contoh di atas deretan karakter yang sama secara berurutan sebanyak 8 karakter, jadi lebih dari tiga dan dapat dilakukan pemampatan. 2. Berikan bit penanda pada file pemampatan, bit penanda disini berupa 8 deretan bit yang boleh dipilih sembarang asalkan digunakan secara konsisten pada seluruh bit penanda pemampatan. Bit penanda ini berfungsi untuk menandai bahwa karakter selanjutnya adalah karakter pemampatan sehingga tidak membingungkan pada saat mengembalikan file yang sudah dimampatkan ke file aslinya. Pada contoh di atas bit penanda ini dipilih 11111110. 3. Tambahkan deretan bit untuk menyatakan jumlah karakter yang sama berurutan, pada contoh diatas karakter yang sama berturutan sebanyak delapan kali, jadi diberikan deretan bit 00001000 (8 desimal). 4. Tambahkan deretan bit yang menyatakan karakter yang berulang, pada contoh diatas karakter yang berulang adalah 01000001 atau karakter A pada karakter ASCII. Untuk melakukan proses pengembalian ke data asli (decompression), dilakukan langkah-langkah berikut ini :
Universitas Sumatera Utara
1. Lihat karakter pada hasil pemampatan satu-persatu dari awal sampai akhir, jika ditemukan bit penanda, lakukan proses pengembalian. 2. Lihat karakter setelah bit penanda, konversikan ke bilangan desimal untuk menentukan jumlah karakter yang berurutan. 3. Lihat karakter berikutnya, kemudian lakukan penulisan karakter tersebut sebanyak bilangan yang telah diperoleh pada karakter sebelumnya (point 2). Pemilihan bit penanda diusahakan dipilih pada karakter yang paling sedikit jumlahnya terdapat pada file yang akan dimampatkan, sebab jika pada file asli ditemukan karakter yang sama dengan bit penanda, terpaksa anda harus menulis karakter tersebut sebanyak dua kali pada file pemampatan. Hal ini harus dilakukan untuk menghindari kesalahan mengenali apakah bit penanda pada file pemampatan tersebut benar-benar bit penanda atau memang karakter dari file yang asli. Sebagai contoh jika terdapat deretan data pada file asli seperti berikut ini : 11111110 11110000 11110000 11110000 11110000 11110000 11110000 10101010 10101010 10101010 Dengan cara seperti yang telah dijelaskan sebelumnya didapatkan hasil pemampatan sebagai berikut : 11111110 11111110
Universitas Sumatera Utara
00000110 10101010 10101010 10101010 Jika dilakukan proses pengembalian ke file aslinya (decompression) maka akan diperoleh hasil : 11111110 00000110 . (sebanyak 11111110 = 254 kali) . 00000110 11110000 10101010 10101010 10101010 Ternyata hasil tersebut tidak sesuai dengan file aslinya. Untuk menjaga agar hal tersebut tidak terjadi, jika pada file asli terdapat karakter yang sama dengan bit penanda, maka pada file pemampatan karakter tersebut ditulis sebanyak dua kali secara berturutan. Pada saat pengembalian ke file asli, jika ditemukan bit penanda yang berderetan sebanyak dua kali, hal itu berarti karakter tersebut bukan bit penanda, tapi karakter asli dari file aslinya. 2.4 Text File
Text file (disebut juga dengan flat file) adalah salah satu jenis file komputer yang tersusun dalam suatu urutan baris Data teks biasanya diwakili oleh 8 bit kode ASCII (atau EBCDIC) (Pu, 2006). Akhir dari sebuah file teks sering ditandai dengan penempatan satu atau lebih karakter – karakter khusus yang dikenal dengan tanda end-
Universitas Sumatera Utara
of-file setelah baris terakhir di suatu file teks. File teks biasanya mempunyai jenis MIME (Multipurpose Internet Mail Extension) "text/plain", biasanya sebagai informasi tambahan yang menandakan suatu pengkodean. pada sistem operasi Windows, suatu file dikenal sebagai suatu file teks jika memiliki extention misalnya txt, rtf, doc dan lain - lain.
Bagaimanapun, banyak akhiran lainnya digunakan untuk file teks dengan tujuan – tujuan yang spesifik. Sebagai contoh, source code program komputer biasanya dalam bentuk file teks yang mempunyai akhiran nama file tertentu yang menandakan jenis bahasa pemrograman yang digunakan. Sedangkan pada penelitian ini jenis file teks yang digunakan adalah file teks dengan extention txt, rtf, doc.
Universitas Sumatera Utara
