MRP dan Perkembanganya

Sejarah MRP dan Perkembangannya

Disekitar tahun 1960, dunia manufaktur membuat teknik perhitungan manufaktur. Dasar perhitungan adalah menggunakan Bill of Material yang berupa daftar kebutuhan bahan baku (Raw Material) yang dibutuhkan untuk membuat suatu produk. Dengan perhitungan status persediaan inventory serta jadwal produksi, sistem tersebut dapat memberikan rekomendasi pembelian bahan baku yang dibutuhkan. Sistem ini dikenal dengan MRP, yang merupakan singkatan dari Material Requirement Planning. Di tahun 1970 proses MRP diintegrasikan dengan fungsi-fungsi bisnis manufaktur lain, yang kemudian menghasilkan sistem baru yang disebut dengan Manufacturing Resource Planning yang dikenal sebagai MRPII. MRPII merupakan sebuah sistem yang dapat dipakai untuk merencanakan semua kebutuhan manufaktur secara efisien yang meliputi business planning, sales and operation planning, dan system execution support. Pada awal tahun 1990-an dunia industry mengembagkan MRPIImenjadi sebuah sistem dengan scope yang lebih luas yang dikenal yang kemudian dikenal dengan Enterprise Resource Planning (ERP).nERP di desain untuk melakukan otomasi proses bisnis untuk perusahaan skala menengah ke atas. Hal ini juga meliputi proses manufacturing, distribution, personnel, project management, payroll, dan finance. ERP merupakan informasi yang dapat mengidentifikasi dan perencanaan kebutuhan akan sumberdaya secara luas.
Fungsi dari MRP :
• Berkaitan dengan persediaan (inventory) : memesan item barang yang tepat, jumlah yang tepat, dan waktu yang tepat.
• Berkaitan dengan prioritas penjadwalan : memesan kebutuhan item barang tepat pada saat dibutuhkan (right due date) dan menjaga agar due date tidak meleset.
• Berkaitan dengan kapasitas pabrik (plan capacity) : membuat rencana pembebanan kerja secara lengkap dan tepat.

Perkembangan MRP menjadi ERP
• Tahap 1 (Material Requirement Planning-1960)
Cikal bakal ERP adalah konsep MRP. Pada tahun 1960, dunia manufaktur membuat teknik perhitungan manufaktur. Dengan dasar perhitungannya adalah menggunakan Bill of Material yang berupa daftar kebutuhan bahan baku (Raw Material) yang dibutuhkan untuk membuat suatu produk. Dengan perhitungan status persediaan inventory serta jadwal produksi, sistem tersebut dapat memberikan rekomendasi pembelian bahan baku yang dibutuhkan. Sistem ini dikenal dengan sebutan MRP, yang merupakan singkatan dari Material Requirement Planning.
MRP dirancang agar dapat menjawab pertanyaan-pertanyaan Produk apa yang akan dibuat ? Apa yang diperlukan untuk membuat produk tersebut ? Apa yang sudah dimiliki ? Apa yang harus dibeli ? dan sebagainya.
• Tahap 2 (Close Loop MRP-1970)
Di tahun 1970 proses MRP diintegrasikan dengan fungsi-fungsi bisnis manufaktur lain, yang kemudian menghasilkan sistem baru yang disebut dengan Manufacturing Resource Planning yang mendukung perencanaan hingga ke penjualan dan produksi, penjadwalan dan perkiraan order konsumen.
• Tahap 3 (Manufacturing Resource Planning/MRPII- 1980)
Tahun 1980-an MRP berkembang menjadi MRP II (Manufacturing Resource Planning), yang memperkenalkan konsep mengenai penyatuan kebutuhan material (MRP) dan kebutuhan sumber daya untuk proses produksi.
MRP II mirip seperti Close Loop MRP ditambah dengan tiga elemen sebagai berikut :
Perencanaan penjualan dan operasi, yang digunakan untuk menyeimbangkan antara permintaan dan persediaan.
Antarmuka keuangan, kemampuan menterjemahkan rencana operasional (dalam bentuk pieces, kg, gallon, dan satuan lainya) menjadi satuan biaya.
Simulasi, kemampuan melakukan analisis untuk mendapatkan jawaban yang mungkin diterapkan dalam satuan unit maupun uang.
• Tahap 4 (Enterprise Resource Planning-1990)
Pada awal tahun 1990-an dunia industry mengembagkan MRP II menjadi sebuah sistem dengan scope yang lebih luas yang kemudian dikenal dengan Enterprise Resource Planning (ERP). Pada dasarnya ERP adalah penambahan module keuangan pada MRP II, sehingga lebih memudahkan bagi para pengambil keputusan menentukan keputusan-keputusannya. Penambahan modul lain meliputi proses manufacturing, distribution, personel, project management, payroll, dan finance.
• Tahap V (Extended ERP / ERP II-2000)
Generasi ini diluncurkan tahun 2000 yang merupakan perluasan dari sistem ERP sebelumnya. Dengan menambahkan fungsi area pada Sales Marketting dan Customer Support sehingga mampu menjembatani komunikasi dengan supplier dan konsumennya.
Menurut Daniel E. O’Leary sistem ERP memiliki karakteristik sebagai berikut [WHI-2006]:
1. Sistem ERP adalah suatu paket perangkat lunak yang didesain untuk lingkungan pelanggan pengguna server, apakah itu secara tradisional atau berbasis jaringan.
2. Sistem ERP memadukan sebagian besar dari proses bisnis.
3. Sistem ERP memproses sebagian besar dari transaksi perusahaan.
4. Sistem ERP menggunakan database perusahaan yang secara tipikal menyimpan setiap data sekali saja.
5. Sistem ERP memungkinkan mengakses data secara waktu nyata (real time).
6. Dalam beberapa hal sistem ERP memungkinkan perpaduan proses transaksi dan kegiatan perencanaan.
7. Sistem ERP menunjang sistem multi mata uang dan bahasa, yang sangat diperlukan oleh perusahaan multinasional.
8. Sistem ERP memungkinkan penyesuaian untuk kebutuhan khusus perusahaan tanpa melakukan pemrograman kembali.

Langkah–langkah dasar dalam penyusunan MRP, yaitu antara lain:
1. Netting
yaitu proses perhitungan jumlah kebutuhan bersih untuk setiap periode selama horison perencanaan yang besarnya merupakan selisih antara kebutuhan kotor dengan jadwal penerimaan persediaan dan persediaan awal yang tersedia.
2. Lotting
yaitu penentuan besarnya ukuran jumlah pesanan (lot size) yang optimal untuk sebuah item berdasarkan kebutuhan bersih yang dihasilkan.
3. Offsetting
yaitu proses yang bertujuan untuk menentukan saat yang tepat melaksanakan rencana pemesanan dalam pemenuhan kebutuhan bersih. Penentuan rencana saat pemesanan ini diperoleh dengan cara mengurangkan kebutuhan bersih yang harus tersedia dengan waktu ancang-ancang (lead time).
4. Exploding
merupakan proses perhitungan dari ketiga langkah sebelumnya yaitu netting, lotting dan offsetting yang dilakukan untuk komponen atau item yang berada pada level dibawahnya berdasarkan atas rencana pemesanan

Cerita Kuliah

Hallaaa… mbabro, masbro, bubro, pakbro,,,,,,

Perkenalken saya pria bernama Prima Utama Sudrajat,masih saudaraan sama Bisma SM*SH ,dan tapi kayanya dia ga kenal saya dan gak mengakuinya kalo kita sodaraan.hahaha

Saya biasa di panggil Pim atau primbon (gimana situasi dan kondisi haha).

Disini saya sedikit mau cerita nih kenapa saya memilih masuk ke kampus saya sekarang yang tercinta ini,kampus yang berada tidak jauh (kalo pake kendaraan) dari landmark nya kota Bandung yaitu gedung sate. Kampus saya termasuk kampus favorite loh di Bandung, bahkan terkenal kalo mahasiswa dan mahasiswinya kece kece (termasuk saya..hihi) sampe sampe hasil survey(hoax) salah satu majalah internasional yang pernah saya baca pun bilang kalo mahasiswa mahasiswinya menjadi trendsetter nya kampus kampus lainya di bandung .

Nah udah ada yang bisa nebak apa belum?? kalo belum saya kasih tau deh (jreng jreng..) namanya UNIVERSITAS WIDYATAMA. Kenapa saya memilih kampus ini? pertama karena dekat dengan rumah,biar ngirit ongkos hehe..terus kampusnya keren favorite anak muda ,kampusnya gede,cewe nya cuantik cuantik..haha (naluri cowo). Dan gak tau kenapa takdir mengarahkan saya buat masuk ke Fakultas Tekhnik Informatika (IF) nya Universitas ini , padahal kalo diliat dari passion saya lebih tertarik kedunia olahraga atau broadcasting,tapi ya karena balik lagi ketakdir mungkin ya sampe saya masuk dan bertahan di IF ini sampe semeter 5 sekarang. Lalu kesan kesanya saya masuk kesini selama ini sih agak menyesal juga sediki karena ketemu sama matakuliah matakuliah yang menurut saya sulit, dan coding coding yang membosankan susah dihapalnya..hehe.bahkan saya sempat mencoba pindah jurusan ke DKV atau Busines Management tapi di tolak oleh dekanya (HAHA). Untung juga sih setelah dipikir dikir justru jurusan ini ilmunya kedepanya tidak akan habis di telan jaman, semakin jaman berkembang IT semakin dibutuhkan. Dan mudah mudahan saya disini mampu berjuang sampe titik darah pengahabisan dan lulus cepat atau tepat pada waktunya.aamiin aamiin aamiin.

Animasi di multimedia

Jenis-jenis animasi

Diawal tahun 20-an popularitas kartun animasi berangsur menurun dan para seineas mulai cenderung mencari alternatif lain sebagai media penghibur masyarakat mulai jenuh dengan konsep animasi yang pada saat itu tidak memikirkan story line dan pengembangan si tokoh karakter perubahaan besar mulai pada pertengahan tahun 20-an setelah beberapa perusahaan animasi pengembang konsep komersialisasi dimana studio-studio besar mengambil alih studio lokal dan menentukan standar animasi sampai saat ini animasi dibagi menjadi 4 kategori besar yaitu:

 

1.Animasi stop motion 

   animasi stop motion atau sebut pula clay animation karna dalam perkembangannya jenis animasi sering mengaunakan clay(tanah liat) sebagai objek teknik stop motion di temukan pertama kali oleh Stuart blanton pada tahun 1906

contoh animasi stop motion antara lain : Chicken Run

 2.Animasi tradisional 

tradisional animsi adalah teknik animasi yang paling umum dikenal sampai saat ini dinamakan tradisional karena teknik yang dingunakan adalah teknik awal pembuatan animasi tradisional animasi juga sering di sebut  cel animation teknik pekerjaannya mengunakan teknik cel luloid tranparent yang sekilas mirip sekali dengan tranparansi OHP yang sering kita gunakan

3.Animasi 3D

sesuai dengan namanya animasi ini secara keseluruhan dikerjakan dengan komputer melalui camera movement keseluruhan objek bisa diperlihatkan secara 3D sebagai contoh adalah film final fantasy pada film ini karakter mempunyai tampilan yang bengitu real dan terlihat gerakan yang diperlihatkan hampir menyerupai manusia

contoh animasi 3D antara lain : Final Fantasy VII (Advent-Children)

4.Animasi kombinasi

animasi kombinasi adalah gabungan dari 2 teknik animasi yang berbeda dalam animasi kombinasi di bagi menjadi 3 antara lain:

1.kombinasi animasi 2D & 3D yaitu pengabungan teknik animasi 2D dengan 3D sebagai contoh adalah film the road to eldorado,titan A.E

2.2D & live shot yaitu penggabungan teknik animasi 2D dengan live shot(syuting adengan)sebagai contoh film space jam dan osmosis jones

3.3D & live shot yaitu pengabungan animasi 3D dan live shot sebagai contoh jurasic park,titanic,lord of the ring,harry potter,stuart littel,scobby doo

(http://bahrisaiful16.blogspot.com/2013/11/oke-gan-kali-ini-gue-akan-menshare.html )

12 Prinsip Dasar Animasi
Untuk memahami 12 prinsip dasar animasi dapat dilihat dari sebuah gerak dan memahaminya secara berurutan. Kedua belas prinsip tersebut adalah:

1. Pose dan gerakan antara (Pose-To-Pose and Inbetween)

Sebagai misal kita mengambil adegan orang berjalan dengan menggunakan kamera. Bentangkan film yang sudah jadi dan akan terlihat rangkaian gambar yang berkesinambungan yang apabila diputar dengan kecepatan 24 frame per detik (film) atau 25 frame per detik (PAL) akan menghasilkan gambar bergerak.
Terkadang sulit untuk langsung meng-copy semua gerakan pada tiap frame. Untuk mempermudah seorang animator akan membagi sekuens gerakan dalam 2 bagian, yaitu pose dan gerakan antara.
Pose adalah gerakan paling ekstrim dari tiap gerakan yang ada dan inbetween adalah gerakan antara suatu pose ke pose lainnya.
Pada animasi 2D key animator akan menggambar key pose. Lalu inbetween melanjutkan dengan membuat gerakan antara satu pose ke pose yang lainnya.

2. Pengaturan waktu (Timing)

Dengan mengatur durasi gerakan, suatu karakter bisa terlihat berbeda dengan karakter yang lain. Walaupun posenya sama, tetapi dengan durasi gerak yang berbeda, maka ekspresi gerakan yang dihasilkan juga berbeda. Misalnya gerak lambat (jarak antar key pose cukup jauh), bergerak biasa, atau gerak cepat (jarak antar key pose lebih dekat).

3. Gerakan sekunder (Secondary Action)

Gerakan sekunder adalah gerakan yang terjadi akibat gerakan yang lain dan merupakan satu kesatuan sistem yang tidak terpisahkan dari gerakan utama. Misalnya pada saat melangkah, tangan kita akan mengimbangi langkah kaki kita, pinggang kita akan ikut berputar dan badan kita akan ikut condong bergerak ke kiri dan ke kanan. Gerakan tersebut adalah akibat dari gerakan utama yaitu langkah kaki yang terjadi akibat reaksi alamiah tubuh untuk tetap seimbang.

Untuk menciptakan gerakan sekunder menambah gerak alami, gerakan sekunder tidak boleh melebihi gerakan utama.

4. Akselerasi (Ease In and Out)

Setiap benda diam cenderung tetap diam dan setiap benda bergerak akan tetap bergerak kecuali mengalami percepatan atau akselerasi (hukum kelembaman Newton). Dari suatu pose yang diam ke sebuah gerakan akan terjadi percepatan dan dari gerakan sebuah pose akan terjadi perlambatan.

5. Antisipasi (Anticipation)

Pada dasarnya semua gerakan akan terjadi dalam 3 bagian, bagian awal yang disebut antisipasi, gerakan itu sendiri dan gerakan akhir yang disebut gerakan penutup (follow through). Misalnya pada saat kita meloncat kita akan menekuk kedua kaki kita, membungkukkan badan dan menarik kedua tangan ke bawah, barulah kita meloncat. Gerakan pendahuluan inilah yang disebut antisipasi.
Pada film animasi 2D sering kita melihat tokoh kartun yang menghilang dari layar dengan meninggalkan segumpal asap tebal. Sebelum lari tokoh tersebut memasang pose persiapan, kaki ditarik menjauh arah lari dan tangan merentang bersiap-siap lari dan kemudian tokoh itupun melesat dan meninggalkan asap tebal.

6. Gerakan lanjutan dan perbedaan waktu gerak (Follow Through and Overlapping Action)

Setiap benda yang bergerak akan cenderung tetap bergerak, bahkan setelah mendapat gaya yang menghentikannya (hukum kelembaman Newton). Misalnya saat kita berlari dan tiba-tiba berhenti. Badan kita akan sedikit terlempar ke depan, sebelum akhirnya kembali ke titik seimbang. Perhatikan setiap gerakan yang kita lakukan, kita akan menemukan dan merasakan “gerakan berlebih” pada setiap akhir gerakan yang kita lakukan. Gerakan tersebut yang disebut sebagai gerak penutup (follow trough).
Tidak semua gerakan terjadi atau berhenti pada saat yang bersamaan. Selalu ada selang waktu antara gerakan utama dengan gerakan sekunder. Seringkali gerakan-gerakan tersebut terasa bertintihan. Prinsip inilah yang dikenal sebagai overlapping action.
Biasanya gerakan sekunder akan mengalami perbedaan waktu gerak (overlapping action). Jika seekor binatang bergerak, ekornya akan ikut bergerak, tetapi gerakan ekor tidak berhenti bersamaan dengan gerakan binatang tersebut, melainkan berhenti beberapa saat lebih panjang.

7. Gerakan melengkung (Arc)

Pada saat kita menggelengkan kepala, gerakan yang dihasilkan adalah gerakan yang sedikit melengkung ke arah atas atau bawah yang membentuk lingkaran. Gerakan inilah yang disebut gerakan melengkung (arc) yang merupakan prinsip yang diterapkan pada animasi.

8. Dramatisasi gerakan (Exaggeration)

Dramatisasi gerakan adalah tindakan mempertegas apa yang sedang dilakukan. Sering kita melihat seorang aktor theater mendramatisasi atau melebih-lebihkan aksi mereka agar terlihat jelas oleh penonton. Saat marah sang aktor akan berkacak pinggang dan menuding-nuding lawannya.
Demikian pula saat tertawa, ia berkacak pinggang, menarik bagian atas tubuhnya ke belakang, mengangkat kepalanya ke atas, membuka mulut selebar-lebarnya dan akhirnya mengeluarkan suara tawa sedemikian kerasnya.

9. Elastisitas (Squash and Stretch)

Hal penting yang harus dilakukan adalah setiap benda yang mengalami pelenturan tetap akan mempertahankan volumenya. Jika sebuah karet berubah volumenya, realitas yang ada akan hilang.
Pada animasi prinsip ini tidak diberlakukan begitu saja, melainkan pada bagian tertentu dari suatu benda. Otot bisep misalnya, mengalami pelenturan yang lebih besar pada bagian tengahnya dibanding bagian tendon atau tepinya. Meskipun benda rigid atau benda relistis (seperti manusia) tampak tidak mengalami pelenturan, prinsip ini tetap saja digunakan. Pada saat melompat ke bawah badan kita akan tertekuk sedikit, gerakan ini yang merupakan gerakan sekunder mirip dengan peristiwa “penyek” yang terjadi pada bola karet yang dilempar ke lantai.

10 prinsip animasi pertama dikenalkan pertama kali oleh Fank Thomas dan Ollie Johnston. Lebih lanjut lagi John Lasseter (sutradara Toys Story) menambahkan 2 prinsip lagi yang akan segera kita pelajari bersama-sama.

10. Penempatan di bidang gambar (Staging)

Selain animasi yang bagus, cara menempatkan karakter dihadapan kamera juga mutlak diperlukan. Dengan menempatkan kamera atau karakter secara tepat, konsep yang kita inginkan dapat terbaca dengan mudah oleh penonton. Prinsip yang paling penting adalah prinsip sinematography dan prinsip silluet.
Dengan menempatkan kamera yang rendah, sebuah karakter akan terlihat besar dan menakutkan. Demikian juga dengan penempatan kamera yang tinggi, karakter akan terlihat kecil atau terlihat bingung. Penempatan kamera dengan arah miring (rolling) akan membuat gerakan terlihat dinamis. Penempatan secara simetris akan membuat karakter terlihat formal atau berwibawa, penempatan arah gerak secara diagonal juga akan membuat adegan terlihat
dinamis.
Melihat silluet karakter (hanya pada bagian foreground vs background) juga memberikan ketegasan pose sebuah karakter. Jika silluet karakter terlihat ambigu atau tidak jelas, maka akan sulit bagi penonton untuk mencerna aksi yang dilakukan karakter.

11. Daya tarik karakter (Appeal)

Setiap karakter dalam animasi haruslah mempunyai daya tarik yang unik, yang membedakannya dengan karakter yang lain. Bisa saja suatu karakter terlihat unik dari sisi desain, atau dari caranya menunjukkan ekspresi pribadinya.

12. Penjiwaan Karakter

Kemampuan akting adalah hal yang harus dimiliki oleh setiap karakter animator. Akting memungkinkan animator menterjemahkan tingkah laku dan daya tarik karakter secara tepat, sehingga penonton merasakan apa yang dimaui oleh seorang animator, bahkan walaupun tanpa dialog sekalipun.
Cara paling mudah menghayati suatu peran adalah dengan membayangkan karakter kita sebagai seorang aktor. Bayangkan kita menjadi diri mereka dan mulailah meniru tingkah laku dan ekspresi mereka.
“Animator yang baik adalah animator yang mampu menggerakkan seluruh anggota tubuhnya dan menterjemahkannya ke dalam suatu karya animasi.”
Tanpa penjiwaan sebuah karakter akan terlihat datar, kaku dan tidak manusiawi. Penjiwaan peran adalah “roh” dari setiap karakter.

PERBEDAAN CELL ANIMATION DIGITAL ANIMATION.

Cell Animation

Kata “cell” berasal dari kata “celluloid”, yang merupakan material yang digunakan untuk membuat film gambar bergerak. Disebut Cell Animation karena teknik pembuatannya dilakukan pada celluloid transparent.

 

Gambar Konsep Kerja Cell Animation.

Digital Animation.

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 dapat juga membuat special effects dan simulasi gambar yang hampir tidak mungkin dilakukan dengan tanpa animasi, seperti memberikan penjelasan mengenai suatu hal yang sulit, contoh animasi solar flare pada matahari. Digital animation juga dapat digunakan untuk merekonstruksi ulang suatu kejadian.

KONKLUSI

Dengan kata lain Cell Animation adalah gambar animasi 2D (2 Dimensi) dan Digital Animation adalah animasi 3D (3 Dimensi), yang dimana teknik pembuatannya pun berbeda; 2D menggunakan celluloid transparent dan cenderung masih manual dalam proses penggabungan animasi-animasinya. Sedangkan digital animation menggunakan bantuan teknik komputer dalam menyempurnakan animasi dan grafisnya pun lebih baik dibandingkan cell animation.

 

Kompresi Text 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 –encoding dengan 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(n log n) untuk himpunan dengan n karakter.

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 Lossless, Run-Length, Shannon-Fano, Arithmetic, PPM (Prediction byPartial Matching), 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.image1

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 encoding. Decoding berarti menyusun kembali data dari string 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”image2

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”.

3. Kesimpulan dan Saran Pengembangan
3.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).

3.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.

Daftar Pustaka

[1]Howe, D., “Free On-line Dictionary of Computing”, http://www.foldoc.org/, 1993.

[2]Huffman Coding http://www.en.wikipedia.org/wiki/Huffman_coding

[3] Rinaldi Munir, 2005, Diktat Kuliah IF2251 Strategi Algoritmik, Penerbit ITB.

[4] Data Structures and Algorithms: Introduction http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS2 10/introduction.html 2005 pukul 11.00 WB

[5] Practical Huffman Coding http://www.compressconsult.com/huffman/

[6] Huffman algorithm, making codes from probabilities http://www.arturocampos.com