SMS Compression over mobile phone using Huffman Algorithm

Algoritma Huffman adalah sebuah algoritma yang cukup rumit, sehingga membutuhkan kesabaran untuk dapat mempelajarinya dengan baik.
Dasar pemikiran algoritma ini adalah bahwa setiap karakter ASCII biasanya diwakili oleh 8 bits. Jadi misalnya suatu file berisi deretan karakter “ABACAD” maka ukuran file tersebut adalah 6 x 8 bits = 48 bit atau 6 bytes. Jika setiap karakter tersebut di beri kode lain misalnya A=1, B=00, C=010, dan D=011, berarti kita hanya perlu file dengan ukuran 11 bits (10010101011), yang perlu diperhatikan ialah bahwa kode – kode tersebut harus unik atau dengan kata lain suatu kode tidak dapat dibentuk dari kode – kode yang lain. Pada contoh diatas jika kode D kita ganti dengan 001, maka kode tersebut dapat dibentuk dari kode B ditambah dengan kode A yaitu 00 dan 1, tapi kode 011 tidak dapat dibentuk dari kode-kode yang lain. Selain itu karakter yang paling sering muncul, kodenya diusahakan lebih kecil jumlah bitnya dibandingkan dengan karakter yang jarang muncul. Pada contoh di atas karakter A lebih sering muncul (3 kali), jadi kodenya dibuat lebih kecil jumlah bitnya dibanding karakter lain.

Untuk menetukan kode-kode dengan kriteria bahwa kode harus unik dan karakter yang sering muncul dibuat kecil jumlah bitnya, kita dapat menggunakan algoritma Huffman.
Sebagai contoh, sebuah file yang akan dimampatkan berisi karakter-karakter “PERKARA”. Dalam kode ASCII masing-masing karakter dikodekan sebagai:
P = 50H = 01010000B
E = 45H = 01000101B
R = 52H = 01010010B
K = 4BH = 01001011B
A = 41H = 01000001B
Maka jika diubah dalam rangkaian bit, “PERKARA” menjadi:
01010000 01000101 01010010 01001011 01000001 01010010 01000001
P E R K A R A
yang berukuran 56 bit.
Tugas kita yang pertama adalah menghitung frekuensi kemunculan masing-masing karakter, jika kita hitung ternyata P muncul sebanyak 1 kali, E sebanyak 1 kali, R sebanyak 2 kali, K sebanyak 1 kali dan A sebanyak 2 kali. Jika disusun dari yang kecil:
E = 1
K = 1
P = 1
A = 2
R = 2
Untuk karakter yang memiliki frekuensi kemunculan sama seperti E, K dan P disusun menurut kode ASCII-nya, begitu pula untuk A dan R.
Selanjutnya buatlah node masing-masing karakter beserta frekuensinya sebagai berikut:
huffman_1

Ambil 2 node yang paling kiri (P dan E), lalu buat node baru yang merupakan gabungan dua node tersebut, node gabungan ini akan memiliki cabang masing-masing 2 node yang digabungkan tersebut. Frekuensi dari node gabungan ini adalah jumlah frekuensi cabang-cabangnya. Jika kita gambarkan akan menjadi seperti berikut ini:
Jika kita lihat frekuensi tiap node pada level paling atas, EK=2, P=1, A=2, dan R=2. Node-node tersebut harus diurutkan lagi dari yang paling kecil, jadi node EK harus digeser ke sebelah kanan node P dan ingat jika menggeser suatu node yang memiliki cabang, maka seluruh cabangnya harus diikutkan juga. Setelah diuurutkan hasilnya akan menjadi sebagai berikut:
Setelah node pada level paling atas diurutkan (level berikutnya tidak perlu diurutkan), berikutnya kita gabungkan kembali 2 node paling kiri seperti yang pernah dikerjakan sebelumnya. Node P digabung dengan node EK menjadi node PEK dengan frekuensi 3 dan gambarnya akan menjadi seperti berikut ini:
Kemudian diurutkan lagi menjadi:
Demikian seterusnya sampai diperoleh pohon Huffman seperti gambar berikut ini:
Setelah pohon Huffman terbentuk, berikan tanda bit 0 untuk setiap cabang ke kiri dan bit 1 untuk setiap cabang ke kanan seperti gambar berikut:
Untuk mendapatkan kode Huffman masing-masing karakter, telusuri karakter tersebut dari node yang paling atas (PEKAR) sampai ke node karakter tersebut dan susunlah bit – bit yang dilaluinya. Untuk mendapatkan kode Karakter E, dari node PEKAR kita harus menuju ke node PEK melalui bit 0 dan selanjutnya menuju ke node EK melalui bit 1, dilanjutkan ke node E melalui bit 0, jadi kode dari karakter E adalah 010.
Untuk mendapatkan kode Karakter K, dari node PEKAR kita harus menuju ke node PEK melalui bit 0 dan selanjutnya menuju ke node EK melalui bit 1, dilanjutkan ke node K melalui bit 1, jadi kode dari karakter K adalah 011.
Untuk mendapatkan kode Karakter P, dari node PEKAR kita harus menuju ke node PEK melalui bit 0 dan selanjutnya menuju ke node P melalui bit 0, jadi kode dari karakter P adalah 00. Untuk mendapatkan kode Karakter A, dari node PEKAR kita harus menuju ke node AR melalui bit 1 dan selanjutnya menuju ke node A melalui bit 0, jadi kode dari karakter A adalah 10. Terakhir, untuk mendapatkan kode Karakter R, dari node PEKAR kita harus menuju ke node AR melalui bit 1 dan selanjutnya menuju ke node R melalui bit 1, jadi kode dari karakter R adalah 11.
Hasil akhir kode Huffman dari file di atas adalah:
E = 010
K = 011
P = 00
A = 10
R = 11
Dengan kode ini, file yang berisi karakter-karakter “PERKARA” akan menjadi lebih kecil, yaitu:
00 010 11 011 10 11 10 = 16 bit
P E R K A R A
Dengan Algoritma Huffman berarti file ini dapat kita hemat sebanyak 56-16 = 40 bit.
Untuk proses pengembalian ke file aslinya, kita harus mengacu kembali kepada kode Huffman yang telah dihasilkan, seperti contoh di atas hasil pemampatan adalah:
000101101100 1110
dengan Kode Huffman :
E = 010
K = 011
P = 00
A = 10
R = 11
Ambillah satu-persatu bit hasil pemampatan mulai dari kiri, jika bit tersebut termasuk dalam daftar kode, lakukan pengembalian, jika tidak ambil kembali bit selanjutnya dan jumlahkan bit tersebut. Bit pertama dari hasil pemampatan diatas adalah 0, karena 0 tidak termasuk dalam daftar kode kita ambil lagi bit kedua yaitu 0, lalu digabungkan menjadi 00, jika kita lihat daftar kode 00 adalah kode dari karakter P.
Selanjutnya bit ketiga diambil yaitu 0, karena 0 tidak terdapat dalam daftar kode, kita ambil lagi bit keempat yaitu 1 dan kita gabungkan menjadi 01. 01 juga tidak terdapat dalam daftar, jadi kita ambil kembali bit selanjutnya yaitu 0 dan digabungkan menjadi 010. 010 terdapat dalam daftar kode yaitu karakter E. Demikian selanjutnya dikerjakan sampai bit terakhir sehingga akan didapatkan hasil pengembalian yaitu PERKARA. Agar lebih jelas kita ambil contoh lain sebuah file yang berisi karakter-karakter “TERTUTUP”. Pertama-tama kita hitung frekuensi kemunculan masing – masing karakter, jika kita hitung ternyata T muncul sebanyak 3 kali, E sebanyak 1 kali, R sebanyak 1 kali, U sebanyak 2 kali dan P sebanyak 1 kali. Jika disusun dari yang kecil (jika sama urutkan berdasarkan kode ASCII):
E = 1
P = 1
R = 1
U = 2
T = 3
Selanjutnya buatlah node masing – masing karakter beserta frekuensinya sebagai berikut:
Setelah dilakukan pembuatan pohon Huffman seperti yang sudah pernah kita lakukan, hasilnya akan menjadi seperti gambar berikut ini:
Dari pohon Huffman di atas, kita bisa membuat daftar kode untuk masing-masing karakter seperti berikut ini:
E = 1110
P = 1111
R = 110
U = 10
T = 0
Dengan kode ini file pemampatan menjadi berisi:
011101100100101111 = 18 bit
Bandingkan file aslinya yang berukuran 64 bit.
Sekarang coba anda kerjakan sendiri untuk mendapatkan file hasil pemampatan dengan algoritma Huffman dari file yang berisi karakter – karakter “PEMAMPATAN”.
Kerjakanlah dengan tahap – tahap berikut :
1. Hitung frekuensi kemunculan masing-masing karakter.
2. Susun berdasakan jumlah frekuensi dari yang kecil, jika sama lihat kode ASCII-nya.
3. Gambarkan pohon Huffman dari karakter-karakter tersebut.
4. Buat daftar Kode Huffman dari pohon Huffman.
5. Kodekan setiap karakter dalam file asli berdasarkan Kode Huffman secara berurutan.
Jika anda lakukan dengan benar, maka daftar kode yang didapatkan adalah:
E = 1010
N = 1011
T = 100
M = 00
P = 01
A = 11
Sehingga file pemampatannya menjadi:
0110100011000111100111011 = 25 bit.
Coba anda lakukan pengembalian ke file aslinya, apakah menghasilkan file yang sama baik dalam jumlah bit dan isinya?
Jika anda melakukan pemerograman dengan menggunakan algoritma Huffman, jangan lupa menyertakan daftar kodenya dalam file pemampatan, selain itu jumlah byte juga harus disertakan sebagai acuan apakah file pengembalian sama dengan file aslinya. Contoh pemerogramannya lebih jelas dapat dipelajari pada BAB V.
(Sujaini, H. dan Yessi Mulyani, “Algoritma Run Length, Half Byte dan Huffman untuk Pemampatan File”, “Mata Kuliah Jaringan Komputer (EL-592)”, ITB, Mei 2000).
Dari artikel diatas, kemudian saya buat sebuah aplikasi khusus untuk berkirim sms yang dapat dikompresi dengan menggunakan algoritma Huffman. Aplkasi ini dibuat dengan program java micro edition dan dikembangkan dengan teknologi CLDC 1.1 dan MIDP 2.0.

Contoh:
sample_1

sample_s2

sample_s3

sampe_s4

sample_s5

sample_s6

sample_s7

sample_s8

Iklan

Orang baik akan berkomentar yang baik

Please log in using one of these methods to post your comment:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s