BAB 2
TINJAUAN PUSTAKA
2.1. 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 enkoding tertentu. Contoh kompresi sederhana yang biasa kita lakukan misalnya adalah menyingkat kata-kata yang sering digunakan tapi sudah memiliki konvensi umum (Saputro, 2011). Misalnya: kata “dan sebagainya” dikompres menjadi kata “dsb”. Pengiriman data hasil kompresi dapat dilakukan jika pihak pengirim/yang melakukan kompresi dan pihak penerima memiliki aturan yang sama dalam hal kompresi data. Pihak pengirim harus menggunakan algoritma kompresi data yang sudah baku dan pihak penerima juga menggunakan teknik dekompresi data yang sama dengan pengirim sehingga data yang diterima dapat dibaca di-decode kembali dengan benar (Saputro, 2011). Proses kompresi data didasarkan pada kenyataan bahwa pada hampir semua jenis data selalu terdapat pengulangan pada komponen data yang dimilikinya, misalnya didalam suatu teks kalimat akan terdapat pengulangan penggunaan huruf alphabet dari huruf a sampai dengan huruf z (Sarifah, 2010). Kompresi data melalui proses encoding berusaha untuk menghilangkan unsur pengulangan ini dengan mengubahnya sedemikian rupa sehingga ukuran data menjadi lebih kecil. Kompresi data menjadi sangat penting karena memperkecil kebutuhan penyimpanan data, mempercepat pengiriman data, memperkecil kebutuhan bandwidth.Teknik kompresi bisa dilakukan terhadap data teks/biner (TXT, RTF, DOC), gambar (JPEG, PNG, TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263).
Universitas Sumatera Utara
Proses kompresi dan dekompresi data dapat ditunjukan melalui diagram blok seperti pada Gambar 2.1.
Kompresi
uncompressed data
compressed data
compressed data
Dekompresi
uncompressed data
Gambar 2.1. Diagram Blok Proses Kompresi dan Dekompresi Data
Kompresi data dibagi menjadi dua kategori yaitu: 1. Kompresi data bersifat loseless Algoritma kompresi tergolong lossless jika memungkinkan data yang sudah dikompres dapat direkonstruksi kembali persis sesuai dengan data original. Teknik ini menjamin tidak ada kehilangan sedikitpun detil atau kerusakan pada data (Saputro, 2011). Lossless compression disebut juga dengan reversible compression karena data asli bisa dikembalikan dengan sempurna. Akan tetapi rasio kompresinya sangat rendah, misalnya pada gambar seperti GIF dan PNG (Sarifah, 2010). Contoh data yang cocok adalah gambar medis, teks, program, spreadsheet dan lain-lain. Beberapa algoritma yang tergolong dalam jenis ini adalah algoritma Shannon-Fano, algoritma Run Length Coding, algoritma Variable Length Binary Encoding, algoritma Fixed Length Binary Encoding, algoritma Huffman, algoritma LZW, dan algoritma Arithmetic Coding (Saputro, 2011).
2. Kompresi data bersifat lossy Algoritma kompresi tergolong lossy jika tidak memungkinkan data yang sudah dikompres dapat direkonstuksi kembali persis sesuai dengan data asli.
Universitas Sumatera Utara
Kehilangan detil-detil yang tidak berarti dapat diterima pada waktu proses kompresi. Hal ini memanfaatkan keterbatasan panca indera manusia. Maka, sebuah perkiraan yang mendekati keadaan original dalam membangun kembali data merupakan hal yang diperlukan untuk mencapai keefektifan kompresi. Contoh data yang cocok adalah gambar, suara dan video. Adapun beberapa algoritma yang tergolong dalam jenis ini adalah algoritma Wavelet Compression, CELP, JPEG, MPEG-1 dan WMA (Saputro, 2011).
2.2. 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 pun kode EBCDIC (Pu, 2006). American Standard Code for Information Interchange (ASCII) dan Extended Binary Coded Decimal Interchange Code (EBCDIC) merupakan cikal bakal dari set karakter lainnya. ASCII merupakan set karakter yang paling umum digunakan hingga sekarang. Set karakter ASCII terdiri dari 128 buah karakter yang masing-masing memiliki lebar 7-bit atau tujuh angka 0 dan 1, dari 0000000 sampai dengan 1111111. Alasan mengapa lebar set karakter ASCII sebesar 7 bit adalah karena komputer pada awalnya memiliki ukuran memori yang sangat terbatas, dan 128 karakter dianggap memadai untuk menampung semua huruf Latin dengan tanda bacanya, dan beberapa karakter kontrol. ASCII terdiri dari huruf-huruf, angka-angka, dan tanda-tanda baca (Sudewa, 2003). EBCDIC merupakan set karakter yang merupakan ciptaan dari IBM. Salah satu penyebab IBM menggunakan set karakter di luar ASCII sebagai standar pada komputer ciptaan IBM adalah karena EBCDIC lebih mudah dikodekan pada punch card yang pada tahun 1960-an masih banyak digunakan. Penggunaan EBCDIC pada mainframe IBM masih ada hingga saat ini, walaupun punch card sudah tidak digunakan lagi.Seperti halnya ASCII, EBCDIC juga terdiri dari 128 karakter yang masing-masing berukuran 7-bit. Hampir semua karakter pada ASCII juga terdapat pada set karakter EBCDIC (Sudewa, 2003).
Universitas Sumatera Utara
Akhir dari sebuah text file sering ditandai dengan penempatan satu atau lebih karakter – karakter khusus yang dikenal dengan tanda end-of-file setelah baris terakhir di suatu file teks. Text file biasanya mempunyai jenis Multipurpose Internet Mail Extension (MIME) "text/plain", biasanya sebagai informasi tambahan yang menandakan suatu pengkodean. Pada sistem operasi Windows, suatu file dikenal sebagai suatu text file jika memiliki extention misalnya txt, rtf, doc, docx dan lain – lain (Khairi, 2011).
Gambar 2.2.Text File Sederhana
2.3. Algoritma
Algoritma diambil dari kata Al-Khwarizmi. Al-Khwarizmi adalah bagian dari nama seorang ahli Matematika dan Astronomi yaitu Abu Ja’far Muhammad Ibnu Musa AlKhwarizmi. Ia dianggap sebagai
pencetus pertama algoritma karena di dalam
bukunya yang berjudul “Aljabar wal muqabala” Abu Ja’far menjelaskan langkah dalam penyelesaian berbagai program Aritmatika (Aljabar). Seiring berjalannya waktu, Al-Khwarizmi berubah kata menjadi algorism, selanjutnya menjadi algorithm. Algoritma adalah teknik penyusunan langkah-langkah penyelesaian masalah dalam bentuk kalimat dengan jumlah kata terbatas tetapi tersusun secara logis dan sistematis (Purbasari, 2007).
Universitas Sumatera Utara
2.4.Algoritma Fixed Length Binary Encoding (FLBE)
Algoritma Fixed Length Binary Encoding (FLBE) sering dikenal sebagi kode blok yang sangat mudah diterapkan di dalam perangkat lunak. Sangat mudah untuk mengganti simbol asli dengan kode FLBE dan untuk memulai dengan string kode tersebut dan memecahnya menjadi kode yang individual kemudian digantikan oleh simbol-simbol asli (Salomon, 2007). Algoritma Fixed Length Binary Encoding adalah algoritma kompresi data yang mengkodekan
tiap
karakter
dengan
menggunakan
beberapa rangkaian
bit.
Pembentukan bit yang mewakili masing-masing karakter dibuat berdasarkan frekuensi kemunculan tiap karakter (Salomon, 2010).
Contoh: ILKOM USU
Data sebelum dikompresi
Character
Frequency
ASCII
ASCII
Desimal
Binary
Bit
Bit x Freq
I
1
73
01001001
8
8
L
1
76
01001100
8
8
K
1
75
01001011
8
8
O
1
79
01001111
8
8
M
1
77
01001104
8
8
Sp
1
32
00100000
8
8
U
2
85
01010101
8
16
S
1
83
01010010
8
8
Jumlah Bit x Frequency
72
Tabel 2.1 Tabel Data sebelum Dikompresi
Universitas Sumatera Utara
Data setelah dikompresi menggunakan algoritma Fixed Length Binary Encoding Character
Frequency
FLBE Code
Bit
Bit x Freq
I
1
000
3
3
L
1
001
3
3
K
1
010
3
3
O
1
011
3
3
M
1
100
3
3
Sp
1
101
3
3
U
2
110
3
6
S
1
111
3
3
Bit x frequency
27
Tabel 2.2. Tabel Data setelah Dikompresi dengan algoritma FLBE
2.5.Algoritma Variable Length Binary Encoding (VLBE)
Algoritma Variable Length Binary Encoding (FLBE)dalam teori pengkodean adalah kode yang memetakan simbol sumber untuk sejumlah variabel bit. Kode variabelpanjang dapat memungkinkan sumber yang akan dikompresi dengan nol kesalahan (kompresi data lossless) dan masih dapat dibaca kembali oleh simbol-simbol. (Salomon,2007). Algoritma Variable Length Binary Encoding adalah algoritma kompresi data yang mengkodekan tiap karakter dengan mengurutkan karakter berdasarkan frekuensi dan disortir secara stabil sehingga membentuk beberapa rangkaian bit(Salomon, 2010). Contoh : ILKOM USU Data sebelum dikompresi dapat dilihat di Tabel 2.1.Data setelah dikompresi menggunakan algoritma Variable Length Binary Encoding dapat dilihat di Tabel 2.3.
Universitas Sumatera Utara
Character
Frequency
VLBE Code
Bit
Freq x Bit
U
2
0
1
2
I
1
10
2
2
L
1
110
3
3
K
1
1110
4
4
O
1
11110
5
5
M
1
111110
6
6
Sp
1
1111110
7
7
S
1
1111111
7
7
Bit x Frequency
36
Tabel 2.3. Tabel Data setelah Dikompresi dengan Algoritma VLBE
2.6.Parameter Pembanding
Ada 4 parameter pembanding yang digunakan dalam peneltiaan ini, yaitu Ratio of Compression (RC), Compression Ratio (CR), Space Savings (SS) dan waktu kompresi.
a. Ratio of Compression (RC) Ratio of Compression (RC) adalah hasil perbandingan antara data yang belum dikompresi dengan data setelah dikompresi (Salomon, 2007) RC =
𝒖𝒌𝒖𝒓𝒂𝒏𝒅𝒂𝒕𝒂𝒔𝒆𝒃𝒆𝒍𝒖𝒎𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊 𝒖𝒌𝒖𝒓𝒂𝒏𝒅𝒂𝒕𝒂𝒔𝒆𝒕𝒆𝒍𝒂𝒉𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
Contoh : 1. Ratio of Compression dari contoh menggunakan algoritma Fixed Length Binary Encoding (FLBE) RC =
72 27
= 2,6
Universitas Sumatera Utara
2. Ratio of Compression dari contoh menggunakan algoritma Variable Length Binary Encoding (VLBE) RC =
72 36
=2
b. Compression Ratio (CR) Compression Ratio (CR) adalah persentase besar data terkompresi, hasil perbandingan antara data yang sudah dikompresi dengan data yang belum dikompresi (Salomon, 2007). CR =
𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒕𝒆𝒍𝒂𝒉 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒃𝒆𝒍𝒖𝒎 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
× 𝟏𝟎𝟎%
Contoh : 1. Compression Ratio dari contoh menggunakan algoritma Fixed Length Binary Encoding (FLBE) CR =
27 72
× 100% = 37,5 %
2. Compression Ratio dari contoh menggunakan algoritma Variable Length Binary Encoding (VLBE) CR =
36 72
× 100% = 50 %
c. Space Savings(SS) Space Savings adalah persentase selisih antara data yang belum dikompresi dengan besar data yang dikompresi (Salomon, 2007). SS = 1 – CR
Universitas Sumatera Utara
Contoh: 1. Space Savings dari contoh menggunakan algoritma Fixed Length Binary Encoding (FLBE) Rd = 100% - 37,5% = 62,5% 2. Space Savingsdari contoh menggunakan algoritma Variable Length Binary Encoding (VLBE) Rd = 100% - 50% = 50%
d. Waktu Kompresi Waktu kompresi merupakan waktu yang dibutuhkan oleh sebuah sistem untuk menginput text file yang akan dikompresi sampai dengan selesainya proses kompresi. Semakin sedikit waktu yang dibutuhkan oleh sebuah sistem untuk melakukan sebuah kompresi, maka metode kompresi yang digunakan semakin efektif.
Universitas Sumatera Utara
