Jenis-Jenis Algoritma Kompresi Data
Algoritma
kompresi untuk jenis kompresi lossless (tanpa
kehilangan data) yang banyak digunakan diantaranya : Huffman, RLE, LZ77, LZ78
dan LZW. Sedangkan untuk jenis kompresi lossy
(kehilangan beberapa bagian data), algoritma yang banyak digunakan antara lain:
Differential Modulation, Adaptive Coding dan
Discrete Cosine Transform (DCT).
Algoritma
Kompresi Huffman
Algoritma
kompresi Huffman dinamakan sesuai dengan nama penemunya yaitu David Huffman,
seorang profesor di MIT (Massachusets
Instuate of Technology).
Kompresi Huffman merupakan algoritma
kompresi lossless dan ideal untuk
mengkompresi teks atau file program.
Ini yang menyebabkan mengapa algoritma
ini banyak dipakai dalam program kompresi.
Kompresi Huffman termasuk dalam
algoritma keluarga dengan variable
codeword length. Ini berarti simbol individual (karakter dalam sebuah file teks sebagai contoh) digantikan oleh
urutan bit yang mempunyai suatu
panjang yang nyata (distinct length).
Jadi simbol yang muncul cukup banyak dalam file
akan memberikan urutan yang pendek sementara simbol yang jarang dipakai akan
mempunyai urutan bit yang lebih
panjang.
Contoh
praktis berikut ini menunjukkan cara kerja dari algoritma Huffman. Misalkan
akan dikompresi potongan data seperti berikut ini:
ACDABA
Distribusi frekuensi untuk
karakter di atas seperti berikut ini:
|
Karakter
|
A
|
B
|
C
|
D
|
|
Frekuensi
|
3
|
1
|
1
|
1
|
Selanjutnya dibentuk node seperti bentuk berikut ini
berdasarkan frekuensi di atas, disusun mulai dari frekuensi terbesar hingga
terkecil. Kemudian dibentuk pohon Huffman agar didapat kode simbol atau kode
pengganti untuk karakter-karakter di atas.
Kemudian diurutkan dari node
dengan frekuensi terkecil hingga terbesar
Selanjutnya dua buah node
terkecil digabung membentuk satu node
baru dimana frekuensinya merupakan penjumlahan dari keduanya.
Setelah
itu diurutkan kembali berdasarkan frekuensi tiap node secara urutan menaik.
Kemudian
dua buah node terkecil digabung
menjadi satu kembali untuk membentuk node baru.
Setelah itu diurutkan kembali
berdasarkan frekuensi tiap node
secara urutan menaik.
Kemudian dua node terakhir ini digabung membentuk
satu pohon tunggal yang disebut dengan pohon Huffman dengan node paling atas merupakan root.
Langkah terakhir adalah
memberikan label bit “0” untuk setiap sisi kiri dari pohon dan label bit “1”
untuk setiap sisi kanan dari pohon.
Karena potongan data tersebut
terdiri atas 6 karakter, maka teks tersebut terdiri atas 6 byte atau 48 bit. Dengan Huffman encoding, akan dicari simbol yang paling sering muncul (dalam kasus
ini adalah karakter ‘A’ muncul sebanyak 3 kali). dan kemudian sebuah pohon (tree) akan dibentuk untuk menggantikan
simbol dengan urutan bit yang lebih pendek. Pada kasus khusus ini, algoritma
akan menggunakan tabel pengganti sebagai berikut: A = 1, B = 010, C = 011, D =
00. Jika code word dipakai untuk
mengkompresi file, maka data yang
telah dikompresi akan terlihat seperti berikut ini. ACDABA
10110010101
Ini berarti hanya 11 bit yang dipakai selain 48 bit, berarti rasio kompresi adalah 4 : 1
untuk file tersebut.
Huffman encoding dapat dioptimalkan dengan dua cara yang berbeda yaitu
sebagai berikut:
1. Adaptive Huffman Code secara dinamis
mengubah code word menurut perubahan
dari probabilitas dari simbol.
2. Extended Huffman Compression dapat
meng-encode grup dari simbol daripada
pada melakukan encode pada simbol
tunggal.
Algoritma kompresi Huffman
secara umum efisien dalam mengkompresi teks atau file program. Untuk file
image biasanya dipakai algoritma yang lain. Kompresi Huffman secara umum dipakai dalam program kompresi seperti
PKZip, LHA, GZ, ZOO, dan ARJ. Algoritma ini juga dipakai dalam kompresi JPEG
dan MPEG.
Adapun bentuk algoritma dari
Huffman dalam membentuk sebuah pohon biner adalah sebagai berikut:
1.
Dimulai dengan penyusunan frekuensi simbol sebagai
frekuensi dari pohon
2.
Jika terdapat lebih dari satu pohon:
a.
Carilah dua pohon dengan jumlah weight yang paling kecil
b.
Gabungkan dua pohon tersebut menjadi satu dan mempunyai
nilai setara dengan jumlah keduanya, atur salah satunya yang bernilai paling
kecil sebagai child sisi kiri dan yang
lainnya sebagai child sisi kanan
3.
Lakukan langkah di atas hingga membentuk satu pohon
biner tunggal
Untuk setiap child
sisi kiri beri simbol ‘0’ dan beri simbol ‘1’ untuk merepresentasi child sisi kanan 