Animasi Pada Multimedia

ANIMASI DAN MULLTIMEDIA

Animasi adalah gambar begerak berbentuk dari sekumpulan objek (gambar) yang disusun secara beraturan mengikuti alur pergerakan yang telah ditentukan pada setiap pertambahan hitungan waktu yang terjadi. Gambar atau objek yang dimaksud dalam definisi di atas bisa berupa gambar manusia, hewan, maupun tulisan. Pada proses pembuatannyam sang pembuat animasi atau yang lebih dikenal dengan animator harus menggunakan logika berfikir untuk menentukan alur gerak suatu objek dari keadaan awal hingga keadaan akhir objek tersebut. Perencanaan yang matang dalam perumusan alur gerak berdasarkan logika yang tepat akan menghasilkan animasi yang menarik untuk disaksikan.

Apabila kita perhatikan penjelasan sebelumnya, maka dapat disimpulkan bahwa terdapat dua hal penting yang harus diperhatikan dalam pembuatan animasi, yaitu Objek/ gambar dan alur gerak.

Atau juga Animasi merupakan suatu teknik menampilkan gambar berurut sedemikian rupa sehingga penonton merasakan adanya ilusi gerakan (motion) pada gambar yang ditampilkan. Secara umum ilusi gerakan merupakan perubahan yang dideteksi secara visual oleh mata penonton sehingga tidak harus perubahan yang terjadi merupakan perubahan posisi sebagai makna dari istilah ‘gerakan’. Perubahan seperti perubahan warna pun dapat dikatakan sebuah animasi.

Dalam bidang grafika pemodelan visual dapat dikategorikan sebagai dua kelompok yaitu pemodelan geometrik dan pemodelan penampilan (appearance). Pemodelan geometrik merupakan representasi dari bentuk objek yang ingin ditampilkan sedangkan pemodelan penampilan membuat representasi sifat visual atau penampakan objek tersebut. Contoh sifat visual diantaranya warna dan tekstur. Berdasarkan definisi animasi di atas bahwa sebuah animasi disusun oleh himpunan gambar yang ditampilkan secara berurut maka animasi dapat dikatakan sebuah fungsi terhadap waktu. Gambar dapat didefinisikan sebagai koleksi deskripsi geometris dan visual ataupun dapat berupa citra. Pada gambar yang merupakan koleksi deskripsi, maka animasi didefinisikan sebagai fungsi yang memetakan waktu kepada perubahan parameter-parameter dari deskripsi. Pada gambar yang merupakan citra, animasi didefinisikan sebagai fungsi yang memetakan waktu kepada tiap elemen citra.

Pengertian Multimedia

Multimedia adalah penggunaan komputer untuk menyajikan dan menggabungkan teks, suara, gambar, animasi dan video dengan alat bantu (tool) dan koneksi (link) sehingga pengguna dapat melakukan navigasi, berinteraksi, berkarya dan berkomunikasi. Multimedia sering digunakan dalam dunia hiburan. Selain dari dunia hiburan, Multimedia juga diadopsi oleh dunia game.

Multimedia dimanfaatkan juga dalam dunia pendidikan dan bisnis. Di dunia pendidikan, multimedia digunakan sebagai media pengajaran, baik dalam kelas maupun secara sendiri-sendiri. Di dunia bisnis, multimedia digunakan sebagai media profil perusahaan, profil produk, bahkan sebagai media kios informasi dan pelatihan dalam sistem e-learning.

Pada awalnya multimedia hanya mencakup media yang menjadi konsumsi indra penglihatan (gambar diam, teks, gambar gerak video, dan gambar gerak rekaan/animasi), dan konsumsi indra pendengaran (suara). Dalam perkembangannya multimedia mencakup juga kinetik (gerak) dan bau yang merupakan konsupsi indra penciuman. Multimedia mulai memasukkan unsur kinetik sejak diaplikasikan pada pertunjukan film 3 dimensi yang digabungkan dengan gerakan pada kursi tempat duduk penonton. Kinetik dan film 3 dimensi membangkitkan sense realistis.

Bau mulai menjadi bagian dari multimedia sejak ditemukan teknologi reproduksi bau melalui telekomunikasi. Dengan perangkat input pendeteksi bau, seorang operator dapat mengirimkan hasil digitizing bau tersebut melalui internet. Komputer penerima harus menyediakan perangkat output berupa mesin reproduksi bau. Mesin reproduksi bau ini mencampurkan berbagai jenis bahan bau yang setelah dicampur menghasilkan output berupa bau yang mirip dengan data yang dikirim dari internet. Dengan menganalogikan dengan printer, alat ini menjadikan feromon-feromor bau sebagai pengganti tinta. Output bukan berupa cetakan melainkan aroma.

Contoh dan Jenis – Jenis Animasi :

  1. Animasi 2D (2 Dimensi).
  2. Animasi 3D (3 Dimensi).
  3. Stop Motion Animasi.
  4. Animasi Jepang (Anime).
  5. Animasi Cell.
  6. Animasi Frame.
  7. Animasi Sprite.
  8. Animasi Path.
  9. Animasi Spline.
  10. Animasi Vektor.
  11. Morphing.
  12. Animasi Clay.
  13. Animasi Digital.
  14. Animasi Karakter.

12 Prinsip Animasi :

12 Prinsip Animasi. Kata “animasi” berasal dari kata “animate,” yang berarti untuk membuat obyek mati menjadi seperti hidup. Seorang Animator profesional sepertinya harus mengetahui dan memahami bagaimana sebuah animasi dibuat sedemikian rupa sehingga didapatkan hasil animasi yang menarik, dinamis dan tidak membosankan.

 

Dua orang animator profesional Thomas dan Johnston memberikan 12 prinsip animasi yang di adopsi dari animasi produksi Walt Disney. Animasi ini sebenarnya paling pas digunakan untuk animasi kartun. Ke-12 prinsip animasi tersebut adalah sebagai berikut :

1. Solid Drawing

Kemampuan menggambar sebagai dasar utama animasi memegang peranan yang menentukan “baik proses maupun hasil” sebuah animasi, terutama animasi klasik. Meskipun kini peran gambar yang dihasilkan sketsa manual sudah bisa digantikan oleh komputer, tetapi dengan pemahaman dasar dari prinsip ‘menggambar’ akan menghasilkan animasi yang lebih ‘peka’. Sebuah obyek/gambar dibuat sedemikian rupa sehingga memiliki karakteristik sebuah obyek (volume, pencahayaan dan konsistensi kualitas gambar/bentuk/karakter).

mickey

2. Timing & Spacing

Grim Natwick, seorang animator Disney pernah berkata, “Animasi adalah tentang timing dan spacing”. Timing adalah tentang menentukan waktu kapan sebuah gerakan harus dilakukan, sementara spacing adalah tentang menentukan percepatan dan perlambatan dari bermacam-macam jenis gerak.

Contoh Timing: Menentukan pada detik keberapa sebuah obyek/karakter berjalan sampai ke tujuan atau berhenti.

Contoh Spacing: Menentukan kepadatan gambar (yang pada animasi akan berpengaruh pada kecepatan gerak).

timing

3. Squash & Stretch

Squash and strecth adalah upaya penambahan efek lentur (plastis) pada objek atau figur sehingga seolah-olah ‘memuai’ atau ‘menyusut’ sehingga memberikan efek gerak yang lebih hidup. Penerapan squash and stretch pada figur atau benda hidup (misal: manusia, binatang, creatures) akan memberikan ‘enhancement’ sekaligus efek dinamis terhadap gerakan/action tertentu, sementara pada benda mati (misal : gelas, meja, botol) penerapan squash and stretch akan membuat mereka (benda-benda mati tersebut) tampak atau berlaku seperti benda hidup.

Contoh ketika sebuah bola dilemparkan. Pada saat bola menyentuh tanah maka dibuat seolah-olah bola yang semula bentuknya bulat sempurna menjadi sedikit lonjong horizontal, meskipun kenyataannya keadaan bola tidak selalu demikian. Hal ini memberikan efek pergerakan yang lebih dinamis dan ‘hidup’.

Untitled

4. Anticipation

Anticipation boleh juga dianggap sebagai persiapan/awalan gerak atau ancang-ancang.Seseorang yang bangkit dari duduk harus membungkukkan badannya terlebih dahulu sebelum benar-benar berdiri. Pada gerakan melompat, seseorang yang tadinya berdiri harus ada gerakan ‘membungkuk’ terlebih dulu sebelum akhirnya melompat.

Anticipation

5. Slow In and Slow Out

Slow In dan Slow Out menegaskan bahwa setiap gerakan memiliki percepatan dan perlambatan yang berbeda-beda. Slow in terjadi jika sebuah gerakan diawali secara lambat kemudian menjadi cepat. Slow out terjadi jika sebuah gerakan yang relatif cepat kemudian melambat. Contoh Slow In :

Slow in

6. Arcs

Pada animasi, sistem pergerakan tubuh pada manusia, binatang, atau makhluk hidup lainnya bergerak mengikuti pola/jalur (maya) yang disebut Arcs. Hal ini memungkinkan mereka bergerak secara ‘smooth’ dan lebih realistik, karena pergerakan mereka mengikuti suatu pola yang berbentuk lengkung (termasuk lingkaran, elips, atau parabola). Sebagai contoh, Arcs ditunjukkan pada lintasan tangan saat melempar bola dan lintasan gerak bola di udara.

Arcs

7. Secondary Action

Secondary action adalah gerakan-gerakan tambahan yang dimaksudkan untuk memperkuat gerakan utama supaya sebuah animasi tampak lebih realistik. Secondary action tidak dimaksudkan untuk menjadi ‘pusat perhatian’ sehingga mengaburkan atau mengalihkan perhatian dari gerakan utama. Kemunculannya lebih berfungsi memberikan emphasizeuntuk memperkuat gerakan utama.

Contoh: Ketika seseorang sedang berjalan, gerakan utamanya tentu adalah melangkahkan kaki sebagaimana berjalan seharusnya. Namun sambil berjalan ‘seorang’ figur atau karakter animasi dapat sambil mengayun-ayunkan tangannya. Gerakan mengayun-ayunkan tangan inilah yang disebut secondary action untuk gerakan berjalan.

8. Follow Through and Overlapping Action

Follow through adalah tentang bagian tubuh tertentu yang tetap bergerak meskipun seseorang telah berhenti bergerak. Misalnya, rambut yang tetap bergerak sesaat setelah melompat. Overlapping action secara mudah bisa dianggap sebagai gerakan saling-silang. Maksudnya, adalah serangkaian gerakan yang saling mendahului (overlapping). Contoh : Kelinci yang melompat. Sesaat setelah melompat telinganya masih bergerak-gerak meskipun gerakan utama melompat telah dilakukan.

Follow

9. Straight Ahead Action and Pose to Pose

Dari sisi resource dan pengerjaan, ada dua cara yang bisa dilakukan untuk membuat animasi. Yang pertama adalah Straight Ahead Action, yaitu membuat animasi dengan cara seorang animator menggambar satu per satu, frame by frame, dari awal sampai selesai seorang diri. Teknik ini memiliki kelebihan: kualitas gambar yang konsisten karena dikerjakan oleh satu orang saja. Tetapi memiliki kekurangan yaitu waktu pengerjaan yang lama.

straigh

Yang kedua adalah Pose to Pose, yaitu pembuatan animasi oleh seorang animator dengan cara menggambar hanya pada keyframe-keyframe tertentu saja, selanjutnya in-between atau interval antar keyframe digambar/dilanjutkan oleh asisten/animator lain. Cara kedua ini memiliki waktu pengerjaan lebih cepat karena melibatkan lebih banyak sumber daya sehingga lebih cocok diterapkan pada industri animasi.

straight pinguin

10. Staging

Staging dalam animasi meliputi bagaimana ‘lingkungan’ dibuat untuk mendukung suasana atau ‘mood’ yang ingin dicapai dalam sebagian atau keseluruhan scene. Biasanya berkaitan dengan posisi kamera pengambilan gambar. Posisi kamera bawah membuat karakter terlihat besar dan menakutkan, kamera atas membuat karakter tampak kecil dan bingung sedangkan posisi kamera samping membuat karakter tampak lebih dinamis dan menarik.

staging

11. Appeal

Appeal berkaitan dengan keseluruhan look atau gaya visual dalam animasi. Kita bisa dengan mudah mengidentifikasi gaya animasi buatan Jepang dengan hanya melihatnya sekilas. Kita juga bisa melihat style animasi buatan Disney atau Dreamworks cukup dengan melihatnya beberapa saat. Hal ini karena mereka memiliki appeal atau gaya tersendiri dalam pembuatan karakter animasi.

apareal

Ada juga yang berpendapat bahwa appeal adalah tentang penokohan, berkorelasi dengan ‘kharisma’ seorang tokoh atau karakter dalam animasi. Sehingga visualisasi animasi yang ada bisa mewakili karakter/sifat yang dimilkiki.

12. Exaggeration

Exaggeration merupakan upaya mendramatisir animasi dalam bentuk rekayasa gambar yang bersifat hiperbolis. Dibuat sedemikian rupa sehingga terlihat sebagai bentuk ekstrimitas ekspresi tertentu dan biasanya digunakan untuk keperluan komedik. Seringkali ditemui pada film-film animasi anak-anak (segala usia) seperti Tom & Jery, Donald Duck, Mickey Mouse, Sinchan, dsb.

Contoh : Tubuh Donald duck melayang mengikuti sumber asap saat hidung Donald cuck mencium aroma masakan/makanan lezat.

exageration

Ke-12 prinsip animasi diatas sering digunakan dalam teknik animasi stop motion dan dalam penerapannya tentu lebih tergantung pada sang animator. Semakin profesional seorang animator dalam menguasai, mengoptimalkan dan mengeksplorasi kemampuan dirinya dalam membuat animasi secara keseluruhan, tentunya ide cerita akan selalu menarik dan menghasilkan sebuah film animasi yang sangat dinamis dan tidak membosankan bahkan untuk kalangan yang bukan merupakan target utama pengguna.

 

Perbedaan antara Cell Animation dan Digital Animation.

Cell Animation atau Animasi cel berasal dari kata “celluloid”, yang merupakan  bahan dasar dalam pembuatan animasi jenis ini ketika tahun-tahun awal adanya animasi. Disebut cell animation karena dalam pembuatannya menggunakan lembaran-lembaran yang membentuk animasi tunggal, masing-masing cel merupakan bagian yang terpisah sebagai objek animasi, Digambar pada celluloid sheets (sehingga dinamakan Cel animation) yang sekarang digantikan oleh layer-layer digital.

cell animation

Digital Animation atau disebut Animasi Digital. Digital animation adalah animasi karakter imajinasi yang dibuat dari hasil proses kerja komputer. Sebelum menggunakan komputer, animasi diselesaikan dengan membuat film dari gambar tangan atau urutan-urutan gambar di atas plastik atau kertas (yang disebut dengan cels), satu frame untuk 1/60 detik. Komputer pertama kali digunakan untuk mengontrol pergerakan dari karakter.

digital animation

Perbedaannya terdapat pada pengerjaan. pada Cell Animation pengerjaan pembuatan animasi menggunakan beberapa cel gambar atau lembar cel yang digabung  dan di timpa pada satu layer atau lembar kanvas sehingga membentuk suatu animasi. Sedangkan Animasi digital adalah suatu pengerjaan animasi yang dilakukan dari menggambar suatu animasi pada kertas atau disebut cell dan di buat menggunakan media computer menggunakan aplikasi animasi, sehingga menjadi gambar bergerak serta kita juga dapat menambahkan special effect pada animasi tersebut.

 

Referensi :

  1. http://oprekzone.com/12-prinsip-animasi/
  2. http://muhajiraja.wordpress.com/2013/03/13/animasi-dan-multimedia/
  3. http://amirpklsicmultimedia.blogspot.com/2012/08/pengertian-dan-jenis-jenis-animasi.html
  4. http://waniperih.weebly.com/cell-animation.html
  5. http://indigiani.wordpress.com/animasi-digital/
  6. https://www.google.co.id/

 

 

 

 

 

 

 

KOMPRESI TEKS dengan MENGGUNAKAN ALGORITMA HUFFMAN

Abstrak

Algoritma Huffman adalah salah satu algoritma kompresi. Algoritma huffman merupakan algoritma yang paling terkenal untuk mengompres teks. Terdapat tiga fase dalam menggunakan algoritma Huffman untuk mengompres sebuah teks, pertama adalah fase pembentukan pohon Huffman, kedua fase encoding dan ketiga fase decoding. Prinsip yang digunakan oleh algoritma Huffman adalah karakter yang sering muncul di –encodingdengan rangkaian bit yang pendek dan karakter yang jarang muncul di-encoding dengan rangkaian bit yang lebih panjang. Teknik kompresi algoritma Huffman mampu memberikan penghematan pemakaian memori sampai 30%. Algoritma Huffman mempunyai kompleksitas O(log n) untuk himpunan dengan karakter.

Kata kunci: algoritma Huffman, pohon Huffman, encoding decoding

 

1. Pendahuluan

Teks adalah kumpulan dari karakter –karakter atau string yang menjadi satu kesatun. Teks yang memuat banyak karakter didalamnya selalu menimbulkan masalah pada media penyimpanan dan kecepatan waktu pada saat transmisi data. Media penyimpanan yang terbatas, membuat semua orang mencoba berpikir untuk menemukan sebuah cara yang dapat digunakan untuk mengompres teks.

Walaupun pada saat ini terdapat banyak algoritma untuk mengompres data termasuk teks, seperti LIFO, LZHUF, LZ77 dan variannya (LZ78, LZW, GZIP), Dynamic Markov Compression (DMC),Block -Sorting LosslessRun-Length, Shannon-FanoArithmetic, PPM (Prediction byPartialMatching), Burrows-Wheeler Block Sorting, dan Half Byte. Namun penulis menggunakan           algoritma Huffman, karena algoritma ini banyak digunakan dan mudah diimplementasikan dalam proses pengompresan teks.

Kompresi adalah proses pengubahan sekumpulan data menjadi bentuk kode dengan tujuan untuk menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi data[1]. Dengan menggunakan algoritma Huffman, proses pengompresan teks dilakukan dengan menggunakan prinsip pengkodean, yaitu tiap karakter dikodekan dengan rangkaian beberapa bit sehingga menghasilkan hasil yang lebih optimal.

Tujuan dari penulisan makalah ini adalah untuk mengetahui keefektifan algoritma Huffman dalam kompresi teks dan memaparkan cara-cara mengompresi teks dengan menggunakan algoritma Huffman.

Untuk mencapai tujuan diatas penulis melakukan serangkaian kegiatan yaitu mengumpulkan data dan referensi-referensi yang ada, serta melakukan studi pustaka.

 

2. Dasar Teori

2.1 Algoritma Huffman

Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks [2]. 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.

Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi data yang diinputkan) menjadi sekumpulan codeword, algoritma Huffman termasuk kedalam kelas algoritma yang menggunakan metode statik . Metoda statik adalah metoda yang selalu menggunakan peta kode yang sama, metoda ini membutuhkan dua fase (two-pass): fase pertama untuk menghitung probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan di taransmisikan.

Sedangkan berdasarkan teknik pengkodean simbol yang digunakan, algoritma Huffman menggunakan metode symbolwise. Metoda symbolwise adalah metode yang menghitung peluang kemunculan dari setiap simbol dalam satu waktu, dimana simbol yang lebih sering muncul diberi kode lebih pendek dibandingkan simbol yang jarang muncul.

 

2.1.1 Pembentukan Pohon Huffman

Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau label. Untuk cabang kiri pada pohon biner diberi label 0, sedangkan pada cabang kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan. Pohon biner ini biasa disebut pohon Huffman.

Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut [3] :

1. Baca semua karakter di dalam teks untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut.

2. Terapkan strategi algoritma greedy sebagai berikut : gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Setelah digabungkan akar tersebut akan mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-pohon penyusunnya.

3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua yang ada selalu terurut menaik berdasarkan frekuensi.

Sebagai contoh, dalam kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai berikut:

A = 01000001

B = 01000010

A = 01000001

C = 01000011

C = 01000011

D = 01000100

A = 01000001

Pada string di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1,

1

Gambar 1. Pohon H uffman untuk Karakter

“ABACCDA”

 

2.1.2 Proses Encoding

Encoding adalah cara menyusun string biner dari teks yang ada. Proses encoding untuk satu karakter dimulai dengan membuat pohon Huffman terlebih dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama string biner yang dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah untuk men-encoding suatu string biner adalah sebagai berikut

1. Tentukan karakter yang akan di-encoding

2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian sampai ketemu daun dimana karakter itu berada

3. Ulangi langkah 2 sampai seluruh karakter diencoding

Sebagai contoh kita dapat melihat tabel dibawah ini, yang merupakan hasil encoding untuk pohon Huffman pada gambar 1

Karakter String Biner Huffman

A                     0

B                     110

C                     10

D                     111

Tabel 1. Kode Huffman untuk Karakter “ABCD”

 

2.1.3 Proses Decoding

Decoding merupakan kebalikan dari encodingDecoding berarti menyusun kembali data daristring biner menjadi sebuah karakter kembali. Decoding dapat dilakukan dengan dua cara, yang pertama dengan menggunakan pohon Huffman dan yang kedua dengan menggunakan tabel kode Huffman.

Langkah-langkah men –decoding suatu string biner dengan menggunakan pohon Huffman adalah sebagai berikut :

1. Baca sebuah bit dari string biner.

2. Mulai dari akar

3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang bersesuaian.

4. Ulangi langkah 1, 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca dengan karakter di daun.

5. Ulangi dari langkah 1 sampai semua bit di dalam string habis. Sebagai contoh kita akan men-decoding string biner yang bernilai ”111”

2

Gambar 2. Proses Decoding dengan Menggunakan Pohon Huffman

setelah kita telusuri dari akar, maka kita akan menemukan bahwa string yang mempunyai kode Huffman “111” adalah karakter D.

Cara yang kedua adalah dengan menggunakan tabel kode Huffman. Sebagai contoh kita akan menggunakan kode Huffman pada Tabel 1 untuk merepresentasikan string “ABACCDA”. Dengan menggunakan Tabel 1 string tersebut akan direpresentasikan menjadi rangkaian bit : 0 110 0 10 10 1110. Jadi, jumlah bit yang dibutuhkan hanya 13 bit. Dari Tabel 1 tampak bahwa kode untuk sebuah simbol/karakter tidak boleh menjadi awalan dari kode simbol yang lain guna menghindari keraguan (ambiguitas) dalam proses dekompresi atau decoding. Karena tiap kode Huffman yang dihasilkan unik, maka proses decoding dapat dilakukan dengan mudah. Contoh: saat membaca kode bit pertama dalam rangkaian bit “011001010110”, yaitu bit “0”, dapat langsung disimpulkan bahwa kode bit “0” merupakan pemetaan dari simbol “A”. Kemudian baca kode bit selanjutnya, yaitu bit “1”. Tidak ada kode Huffman “1”, lalu baca kode bit selanjutnya, sehingga menjadi “11”. Tidak ada juga kode Huffman “11”, lalu baca lagi kode bit berikutnya, sehingga menjadi “110”. Rangkaian kode bit “110” adalah pemetaan dari simbol “B”.

 

2.1.4 Kompleksitas Algoritma Huffman

Algoritma Huffman mempunyai kompleksitas waktu O(n log n), karena dalam melakukan sekali

proses itersi pada saat penggabungan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar membutuhkan waktu O(log n), dan proses itu dilakukan berkali-kali sampai hanya tersisa satu buah pohon Huffman itu berarti dilakukan sebanyak n kali[4].

 

2.2 Algoritma Greedy

Algoritma greedy adalah salah satu algoritma yang digunakan untuk menyelsaikan persoalan optimasi, artinya persoalan yang menuntut pencarian solusi optimum, baik masalah maksimasi (maximization ) atau minimasi (Minimization).

Algoritma greedy adalah algoritma yangmecahkan masalah langkah per langkah, pada setiap langkahnya algoritma greedy melakukan [3] :

1. Mmengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

2. Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

 

2.2.1 Hubungan Algoritma Greedy dengan Algoritma Huffman

Pada awalnya David Huffman hanya menencoding karakter dengan hanya menggunakan pohon biner biasa, namun setelah itu David Huffman menemukan bahwa penggunaan algoritma greedy dapat membentuk kode prefiks yang optimal.

Penggunaan algoritma greedy pada algoritma Huffman adalah pada saat pemilihan dua pohon dengan frekuensi terkecil dalam membuat pohon Huffman. Algoritma greedy ini digunakan pada pembentukan pohon Huffman agar meminimumkan total cost yang dibutuhkan. Cost yang digunakan untuk menggabungkan dua buah pohon pada akar setara dengan jumlah frekuensi dua buah pohon yang digabungkan, oleh karena itu total costpembentukan pohon Huffman adalah jumlah total seluruh penggabungan. Penggabungan dua buah pohon dilakukan setiap langkah dan algoritma Huffman selalu memilih dua buah pohon yang mempunyai frekuensi terkecil untuk meminimumkan total cost. Oleh karena itu algoritma Huffman adalah salah satu contoh algoritma yang menggunaan dari algoritma greddy.

Sebagai contoh terdapat sebuah teks yang terdiri dari 120 karakter, yang masing-masing karakter mempunyai cost. Tujuan kita adalah menghitung total cost yang dikeluarkan untuk membentuk teks tersebut.

 

Karakter cost Kode Huffman Total cost

A        10           000             10×3=30

B        15             010             15×3=45

C         5             0010             5×5=25

D       15             011             15×3=45

E        20             111             20×3=60

F         5            00110           5×5=25

G        15             110            15×3=45

H        30             10               30×2=60

I          5             00111          5×5=25

Total cost                                   360

Tabel 2. Contoh Perhitungan Total Cost pada Suatu Teks

 

3. Pengujian Algoritma Huffman

Pada pengujian digunakan, kita akan menencoding sebuah teks yang berisi 100.000 string, diantaranya 45.000 karakter ‘g’, 13.000 karakter ‘o’, 12.000 karakter ‘p’, 16.000 karakter ‘h’, 9.000 karakter ‘e’, dan 5.000 karakter ‘r’ dengan menggunakan 3 cara, yaitu dengan menggunakan kode ASCII , kode 3-bit dan kode Huffman. Setelah itu ketiga kode tersebut akan dibandingkan satu sama lainnya.

a. Kode ASCII

Karakter ASCII   Biner

g           103    1100111

o           111    1101111

p           112    1110000

h           104    1101000

e           101    1100101

r            114    1110010

Tabel 3. Kode ASCII untuk karakter “ g,o,p,h,e,r, ”

Untuk meng-encoding teks tersebut kita membutuhkan sebanyak

  • untuk karakter ‘g’ 4.5000 x 8 bit (1100111) = 360.000 bit
  • untuk karakter ‘o’ 13.000 x 8bit (1101111) = 104.000 bit
  • untuk karakter ‘p’ 12.000 x 8bit (1110000) = 96.000 bit
  • untuk karakter ‘h’ 16.000 x 8bit (1101 000 ) = 128.000 bit
  • untuk karakter ‘e’ 9.000 x 8bit (1100101) = 72.000 bit
  • untuk karakter ‘r’ 5.000 x 8bit (1110010) = 40.000 bit jumlah = 800.000 bit

b. 3-bit Kode

Karakter Kode String Biner

g                 0             000

o                 1             001

p                 2             010

h                 3             011

e                 4             100

r                  5            101

Tabel 4. 3-bit Kode untuk karakter “ g,o,p,h,e,r”

Untuk meng-encoding teks tersebut kita membutuhkan sebanyak

  • untuk karakter ‘g’ 45.000 x 3 bit (000) = 135.000 bit
  • untuk karakter ‘o’ 13.000 x 3bit (001) = 39 .000 bit
  • untuk karakter ‘p’ 12.000 x 3bit (010) = 36 .000 bit
  • untuk karakter ‘h’ 16.000 x 3bit (011) = 48 .000 bit
  • untuk karakter ‘e’ 9.000 x 3bit (100) = 27 .000 bit
  • untuk karakter ‘r’  5.000 x 3bit (101) = 15.000 bit jumlah = 300.000 bit

c. Kode Huffman

Karakter Frekuensi Peluang Kode Huffman

g           45000       3/13               0

o           13000       3/13             101

p           12000       1/13             100

h            16000       1/13            111

e             9000        1/13            1101

r             5000         1/13            1100

Tabel 5. Kode Huffman untuk Karakter “ g,o,p,h,e,r”,

Untuk meng-encoding teks tersebut kita membutuhkan sebanyak

  • untuk karakter ‘g’ 45.000 x 1 bit (0) = 45 .000 bit
  • untuk karakter ‘o’ 13.000 x 3bit (101) = 39 .000 bit
  • untuk karakter ‘p’ 12.000 x 3bit (110) = 36 .000 bit
  • untuk karakter ‘h’ 16.000 x 3bit (111) = 48.000 bit
  • untuk karakter ‘e’ 9.000 x 4bit (1101) = 36.000 bit
  • untuk karakter ‘r’ 5.000 x 4bit (1100) = 20 .000 bit jumlah = 224.000 bit

Dari data diatas kita dapat lihat bahwa dengan menggunakan kode ASCII untuk meng-encoding teks tersebut membutuhkan 800.000 bit, sedangkan dengan menggunakan 3-bit kode dibutuhkan 300.000 bit dan dengan menggunakan kode Huffman hanya membutuhkan 224.000. Dengan menggunakan data tersebut maka dapat kita lihat bahwa dengan menggunakan algoritma huffman dapat mengompres teks sebesar 70% dibandingkan kita menggunakan kode ASCII dan sebesar 25,3% dibandingkan kita menggunakan 3-bit kode.

 

4. Kesimpulan dan Saran Pengembangan

4.1 Kesimpulan

1. Algoritma Huffman adalah salah satu algoritma kompresi, yang banyak digunakan dalam kompresi teks.

2. Terdapat 3 tahapan dalam menggunakan algoritma Huffman, yaitu:

  • membentuk pohon Huffman
  • melakukan encoding dengan menggunakan pohon Huffman, dan
  • melakukan decoding

3. Algoritma Huffman mempunyai kompleksitas waktu O(n log n).

4. Algoritma Huffman adalah salah satu algoritma yang menggunakan prinsip algoritma greedy dalam penyusunan pohon Huffman

5. Dari hasil pengujian yang dilakukan, algoritma Huffman dapat mengompres teks sebesar 70% jika dibandingkan dengan menggunakan kode ASCII dan sebesar 25,3% jika dibandingkan dengan kita menggunakan 3-bit kode.

 

4.2 Saran Pengembangan

Untuk dapat lebih melihat dan membuktikan keefektifan, kelebihan dan kelemahan dari algoritma Huffman, perlu diadakannya sebuah penelitian yang bertujuan membandingkan seluruh algoritma kompresi dalam mengompres berbagai data atau file.

Selamat Menulis

Selamat Datang di Dunia Blog, dan selamat menulis…

Pengelola blog kembali mengingatkan akan peraturan pemakaian Blog Universitas Widyatama Bandung adalah sebagai berikut :

  1. Blog ini merupakan milik Universitas Widyatama termasuk didalamnya seluruh sub domain yang digunakan sehingga apa yang terdapat didalam blog ini secara umum akan mengikuti aturan dan kode etik yang ada di Universitas Widyatama Bandung.
  2. Blog ini dibuat dengan menggunakan aplikasi pihak ke tiga (WordPress), dan lisensi plugin plugin didalamnya terikat terhadap developer pembuat plugin tersebut.
  3. Blog ini dapat digunakan oleh Karyawan, Dosen dan Mahasiswa Universitas Widyatama Bandung.
  4. Dilarang melakukan registrasi username atau site/subdomain blog dengan menggunakan kata yang tidak pantas.
  5. Dilarang memasukkan konten dengan unsur SARA, pornografi, pelecehan terhadap seseorang ataupun sebuah institusi.
  6. Dilarang menggunakan blog ini untuk melakukan transaksi elektronik dan pemasangan iklan.
  7. Usahakan sebisa mungkin untuk melakukan embed video atau gambar di bandingkan dengan melakukan upload secara langsung pada server.
  8. Pelanggaran yang dilakukan akan dikenakan sanksi penutupan blog dan atau sanksi yang berlaku pada aturan Universitas Widyatama sesuai dengan jenis pelanggaran yang dilakukan.
  9. Administrator berhak melakukan pembekuan account tanpa pemberitahuan terlebih dahulu jika dianggap ada hal hal yang melanggar peraturan.
  10. Aturan yang ada dapat berubah sewaktu waktu.

Beberapa Link terkait Universitas Widyatama

  1. Fakultas Ekonomi – http://ekonomi.widyatama.ac.id
  2. Fakultas Bisnis & Manajemen – http://manajemen.widyatama.ac.id
  3. Fakultas Teknik – http://teknik.widyatama.ac.id
  4. Fakultas Desain Komunikasi Visual – http://dkv.widyatama.ac.id
  5. Fakultas Bahasa – http://bahasa.widyatama.ac.id

Layanan Digital Universitas Widyatama

  1. Biro Akademik – http://akademik.widyatama.ac.id
  2. Rooster Kuliah – http://rooster.widyatama.ac.id
  3. Portal Mahasiswa – http://mhs.widyatama.ac.id
  4. Portal Dosen – http://dosen.widyatama.ac.id
  5. Digital Library – http://dlib.widyatama.ac.id
  6. eLearning Portal – http://learn.widyatama.ac.id
  7. Dspace Repository – http://repository.widyatama.ac.id
  8. Blog Civitas UTama – http://blog.widyatama.ac.id
  9. Email – http://email.widyatama.ac.id
  10. Penerimaan Mahasiswa Baru – http://pmb.widyatama.ac.id/online

Partner UTama

  1. Putra International College – http://www.iputra.edu.my
  2. Troy University – http://www.troy.edu
  3. Aix Marsielle Universite – http://www.univ-amu.fr
  4. IAU – http://www.iau-aiu.net/content/institutions#Indonesia
  5. TUV – http://www.certipedia.com/quality_marks/9105018530?locale=en
  6. Microsoft – https://mspartner.microsoft.com/en/id/Pages/index.aspx
  7. Cisco – http://www.cisco.com/web/ID/index.html
  8. SAP – http://www.sap.com/asia/index.epx
  9. SEAAIR – http://www.seaair.au.edu

Academic Research Publication

  1. Microsoft Academic  –  http://academic.research.microsoft.com/Organization/19057/universitas-widyatama?query=universitas%20widyatama
  2. Google Scholar – http://scholar.google.com/scholar?hl=en&q=Universitas+Widyatama&btnG=

Info Web Rangking

  1. Webometric – http://www.webometrics.info/en/detalles/widyatama.ac.id
  2. 4ICU – http://www.4icu.org/reviews/10219.html