Mengenai Saya
|
| Algoritma Kompresi Data | Selasa, April 17, 2012 |
|
Filed under:
Algoritma Kompresi Data
|
|
I.
Sekilas 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. Kompresi berarti memampatkan / mengecilkan ukuran.
Berdasarkan
tipe peta kode yang digunakan untuk mengubah pesan awal (isi file input)
menjadi sekumpulancodeword, metode kompresi terbagi menjadi dua kelompok,
yaitu :
(a)
Metode statik :
Menggunakan
peta kode yang selalu sama. Metode ini membutuhkan dua fase (two-pass):
Fase pertama untuk menghitung probabilitas kemunculan tiap simbol/karakter dan
menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan
kode yang akan ditransmisikan. Contoh: algoritma Huffman statik.
(b)
Metode dinamik (adaptif) :
Menggunakan
peta kode yang dapat berubah dari waktu ke waktu. Metode ini disebut adaptif
karenapeta kode mampu beradaptasi terhadap perubahan karakteristik isi file
selama proses kompresi berlangsung. Metode ini bersifat onepass, karena hanya
diperlukan satu kali pembacaan terhadap isi file. Contoh: algoritma LZW dan
DMC.
Manfaat Kompresi Data
- Kompresi data menjadi sangat penting karena memperkecil kebutuhan penyimpanan data, mempercepat pengiriman data, memperkecil kebutuhan lebar-bidang (bandwidth).
- Teknik kompresi bisa dilakukan terhadap data teks/biner (zip), gambar (JPEG, PNG, TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263).
Teknik Kompresi Data:
1.
Losseles
Compression, Tekhnik kompresi yang tidak mengurangi ukuran aslinya. Losseles
artinya tidak ada data yang hilang, menggunakan algortima tertentu untuk
mengompres data (compress) dan mengembalikan ke ukuran semula (decompress),
dipakai untuk mengompres data dan program.
2.
Lossy
Compression, TEkhnoik kompresi yang mengurangi ukuran aslinya. Lossy artinya
ada data yang hilang, bertujuan untuk mengefisienkan data,biasanya dipakai
untuk mengompres data multimedia.
Kriteria Algoritma
dan Aplikasi Kompresi Data
Ø Kualitas data hasil
enkoding: ukuran lebih kecil, data tidak rusak untuk kompresi lossy.
Ø Kecepatan, ratio, dan
efisiensi proses kompresi dan dekompresi
Ø Ketepatan proses
dekompresi data: data hasil dekompresi tetap sama dengan data sebelum dikompres
(kompresi loseless)
II. Macam Algoritma Kompresi Data
II.1
Algoritma Huffman
Algoritma
Huffman adalah salah satu algoritma kompresi tertua
yang disusun oleh David Huffman pada tahun 1952. Algoritma tersebut digunakan
untuk membuat kompresi jenis lossy compression, yaitu pemampatan data dimana
tidak satu byte pun hilang sehingga data tersebut utuh dan disimpan sesuai
dengan aslinya. Algoritma Huffman
menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap
karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana
karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan
karakter yang jarang muncul dikodekan
dengan rangkaian bit yang lebih panjang.
Cara Kerja dalam menggunakan algoritma Huffman, yaitu:
- Mengubah sebuah string atau masukan dari user dan menghitung kemunculan setiap huruf. Setelah itu, buat daftar dari huruf tersebut beserta peluang kemunculannya karena huruf tersebut akan menjadi daun dalam pohon Huffman. . Kode ini biasanya identik dengan pohon biner yang diberi label 0 untuk cabang kiri dan 1 untuk cabang kanan.
- Mengubah kembali daftar yang telah dibuat untuk kemudian membedakan daun (berupa huruf dengan pelung terkecil) dan penjumlahan 2 daun yang akan menjadi akar dari dua daun sebelumnya.
ADADIAM
Tabel
kode ASCII
Terdapat
7 karakter dalam string , maka memori yang dibutuhkan adalah 7 x 8 bit = 56
bit.
Memori
= n x 8 bit
N
= jumlah karakter dalam sebuah string.
Selanjutnya
panjang kode pada tiap karakter dipersingkat, terutama untuk karakter yang
frekuensi kemunculan besar.
A = 3, D = 2, I = 1,
M = 1
Tabel Kode Huffman
Tree
Sehingga string ‘ADADIAM’ jika representasikan dalam bit menjadi
0100101100111
Maka, bit yang dibutuhkan hanya 13 bit dengan Algoritma Huffman. Lebih
kecil bukan ??
II.2. Algoritma LZW (Lempel-Ziv-Welch)
Algoritma LZW dikembangkan dari metode
kompresi yang dibuat oleh Ziv dan Lempel pada tahun 1977. Algoritma ini
melakukan kompresi dengan menggunakan dictionary, di mana
fragmen-fragmen teks digantikan dengan indeks yang diperoleh dari sebuah
“kamus”. Prinsip sejenis juga digunakan dalam kode Braille, di mana kode-kode
khusus digunakan untuk merepresentasikan kata-kata yang ada.
Pendekatan ini bersifat adaptif dan efektif karena
banyak karakter dapat dikodekan dengan mengacu pada string yang telah
muncul sebelumnya dalam teks. Prinsip kompresi tercapai jika referensi dalam
bentuk pointer dapat disimpan dalam jumlah bit yang lebih sedikit
dibandingkan string aslinya.
Kegunaan
: LZW banyak dipergunakan pada UNIX, GIF,V.42 untuk modem.
Algoritma Kompresi LZW(Lempel-Ziv-Welch) :
BEGIN
s
= next input character;
while
not EOF
{
c = next input character;
if s + c exists in the diactionary
s = s + c
else
{
Output the code for s;
Add string s + c to the dictionary with a new code
= c;
}
}
END
Contoh Soal : ABABBABCABABBA
Dengan mengikuti algoritma LZW maka di dapatkan penyelesaian dalam bentuk tabel berikut :
III.3. Algoritma DMC (Dynamic Markov
Compresion)
Algoritma DMC (Dynamic Markov Compresion) adalah
algoritma kompresi data lossless dikembangkan oleh Gordon Cormack dan Nigel
Horspool. Algoritma ini menggunakan pengkodean aritmatika prediksi oleh
pencocokan sebagian (PPM), kecuali bahwa input diperkirakan satu bit pada satu
waktu (bukan dari satu byte pada suatu waktu). DMC memiliki rasio kompresi yang
baik dan kecepatan moderat, mirip dengan PPM, tapi memerlukan sedikit lebih
banyak memori dan tidak diterapkan secara luas.
Pada DMC, simbol alfabet input diproses per bit, bukan per
byte. Setiap output transisi menandakan berapa banyak simbol tersebut muncul.
Penghitungan tersebut dipakai untuk memperkirakan probabilitas dari transisi.
Contoh: transisi yang keluar dari state 1 diberi label 0/5, artinya bit
0 di state 1 terjadi sebanyak 5 kali.
Secara umum, transisi ditandai dengan 0/p atau 1/q
dimana p dan q menunjukkan jumlah transisi dari state dengan
input 0 atau 1. Nilai probabilitas bahwa input selanjutnya bernilai 0 adalah p/(p+q)
dan input selanjutnya bernilai 1 adalah q/(p+q). Lalu bila
bit sesudahnya ternyata bernilai 0, jumlah bit 0 di transisi sekarang ditambah
satu menjadi p+1. Begitu pula bila bit sesudahnya ternyata bernilai 1,
jumlah bit 1 di transisi sekarang ditambah satu menjadi q+1.
Algoritma
kompresi DMC :
1.
s ß 1 ( jumlah state sekarang)
2.
t ß 1 (state sekarang)
3.
T[1][0] = T[1][1] ß 1
(model inisialisasi)
4.
C[1][0] = C[1][1] ß 1
(inisialisasi untuk menghindari masalah frekuensi nol)
5.
Untuk setiap input bit e :
· u ß t
· t ß T[u][e]
(ikuti transisi)
· Kodekan e dengan probabilitas : C[u][e]
/ (C[u][0] + C[u][1])
· C[u][e] ß
C[u][e]+1
· Jika ambang batas cloning tercapai, maka :
Ø
s ß
s +
1 (state baru t’)
Ø
T[u][e] ß s
; T[s][0] ß
T[t][0]
; T[s][1] ß T[t][1]
Ø
Pindahkan beberapa dari C[t]
ke C[s]
Masalah tidak terdapatnya kemunculan suatu bit pada state
dapat diatasi dengan menginisialisasi model awal state dengan satu.
Probabilitas dihitung menggunakan frekuensi relatif dari dua transisi yang
keluar dari state yang baru.
Jika
frekuensi transisi dari suatu state t ke state sebelumnya, yaitu state
u, sangat tinggi, maka state t dapat di-cloning. Ambang batas
nilai cloning harus disetujui oleh encoder dan decoder.
State yang di-cloning diberi simbol t’ (lihat Gambar 4 dan 5).
Aturan
cloning adalah sebagai berikut :
1.
Semua
transisi dari state u dikirim ke state t’. Semua transisi
dari state lain ke state t tidak berubah.
2.
Jumlah transisi yang keluar dari t’
harus mempunyai rasio yang sama (antara 0 dan 1) dengan jumlah transisi
yang keluar dari t.
3.
Jumlah transisi yang keluar dari t dan
t’ diatur supaya mempunyai nilai yang sama dengan jumlah transisi yang
masuk [2].
III.
Perbandingan Masing-Masing Algoritma
 |
| Blox Plot Rasio Kompresi Ke-3 Algoritma |
 |
| Blox Plot Kecepatan Kompresi Ke-3 Algoritma |
 |
| Grafik Perbandingan Ke-3 Algoritma |
 |
| Grafik Perbandingan Ke-3 Algoritma |
Dari grafik di atas,
dapat kita lihat bahwa secara rata-rata algoritma DMC menghasilkanrasio file
hasil kompresi yang terbaik (41.5% ± 25.9), diikuti algoritma
LZW (60.2% ± 28.9) dan terakhir algoritma Huffman (71.4% ± 15.4).
Dan dari grafik di
atas juga, dapat kita lihat bahwa secara rata-rata algoritma LZW membutuhkan
waktu kompresi yang tersingkat (kecepatan kompresinya = 1139
KByte/sec ± 192,5), diikuti oleh algoritma Huffman (555,8 KByte/sec ± 55,8),
dan terakhir DMC (218,1 KByte/sec ± 69,4). DMC mengorbankan kecepatan kompresi
untuk mendapatkan rasio hasil kompresi yang baik. File yang berukuran sangat
besar membutuhkan waktu yang sangat lama bila dikompresi dengan DMC.
IV. Kesimpulan
1.
Secara rata-rata algoritma DMC
menghasilkan rasio file hasil kompresi yang terbaik (41.5% ±25.9), diikuti
algoritma LZW (60.2% ± 28.9) dan terakhir algoritma Huffman (71.4% ±15.4).
2.
Untuk kategori file teks, source
code, file aplikasi, dan file basis data, DMC memberikan hasil
kompresi yang baik sekali. Sedangkan untuk file multimedia, hasil kompresinya
buruk (dapat > 100 %), karena pada umumnya file multimedia merupakan file
hasil kompresi juga, dan hasil kompresi DMC terhadap file yang telah
terkompresi sebelumnya memang kurang baik.
3.
Hasil kompresi Huffman lebih baik
dibandingkan LZW hanya pada kasus file biner, file multimedia, file
gambar, dan file hasil kompresi. Algoritma Huffman memberikan hasil yang
relatif hampir sama untuk setiap kasus uji, sedangkan LZW memberikan hasil
kompresi yang buruk (dapat > 100%) untuk file multimedia dan file hasil
kompresi.
4.
Secara rata-rata algoritma LZW
membutuhkan waktu kompresi yang tersingkat (kecepatan kompresinya = 1139
KByte/sec ± 192,5), diikuti oleh algoritma Huffman (555,8 KByte/sec ± 55,8),
dan terakhir DMC (218,1 KByte/sec ± 69,4).
5.
DMC mengorbankan kecepatan kompresi
untuk mendapatkan rasio hasil kompresi yang baik. File yang berukuran sangat
besar membutuhkan waktu yang sangat lama bila dikompresi dengan DMC (contoh:
file multimedia dengan ukuran 59 MB membutuhkan waktu kompresi 12,3 menit).
Kecepatan kompresi algoritma LZW secara signifikan berkurang pada file UNIX,
file executable, file gambar, file multimedia, dan file hasil
kompresi. Kecepatan kompresi algoritma DMC berkurang pada file gambar dan
file hasil kompresi, bahkan untuk file multimedia kecepatan kompresi berkurang
lebih dari sepertiga kalinya dibandingkan kecepatan kompresi rata-rata.
Kecepatan kompresi algoritma Huffman hampir merata untuk semua kategori file.
V. Referensi
1.
Howe, D., “Free On-line Dictionary
of Computing”, http://www.foldoc.org/,1993.
2.
Witten, I.H, et al., “Managing
Gigabytes”,Van Nostrand Reinhold, New York, 1994.
3.
Ben Zhao, et al., “Algorithm
in the Real World - (Compression) Scribe Notes”,http://www-2.cs.cmu.edu/~guyb/realworld/class-notes/all/,
1998, [17 Jan 2002]
4.
Compression Team, “The LZWAlgorithm”,
Data Compression ReferenceCenter, http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/LZW.html,
1997, [17Jan 2002]
5.
Ziviani, N., de Moura, E. S.,“Compression:
A Key for Next Generation Text Retrieval System”, Department of Computer
Science Univ. Federal de Minas Gerais, Brazil, 2000.
6.
University of Calgary, Calgary
Corpus,http://links.uwaterloo.ca/calgary.corpus.html, [26 Maret 2002]
7.
University of Canterbury, “The Canterbury
Corpus”, http://corpus.canterbury.ac.nz, [26 Feb 2002]
8.
Cormack, G.V., Horspool, R.N., “Data
Compression Using Dynamic Markov Compression”, University of Waterloo and
University of Victoria, 1986.
Langganan:
Posting Komentar (Atom)
3 komentar:
Kami juga mempunyai artikel yang terkait dengan
algoritma kompresi, bisa di download disini:
http://repository.gunadarma.ac.id/bitstream/123456789/2242/1/01-03-002-Peningkatan%5BEdi_Sukirman%5D.pdf
semoga bermanfaat :D
ada aplikasi nya gak mbak ?
http://repository.gunadarma.ac.id/bitstream/123456789/2242/1/01-03-002-Peningkatan%5BEdi_Sukirman%5D.pdf
moof maaf ni kak, untuk link tersebut hanya menampilkan file not found kak, ada link lain untuk repositori tersebut kak?
Posting Komentar