Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Huffman Coding

teknik kompresi data
by

M Rizki Fadhilah

on 26 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Huffman Coding

HUFFMAN CODING Apa itu Huffmann Coding ? Mengapa Huffman ? Ide Dasar Coding Huffman Thank's for Yours Huffman Coding adalah salah satu algoritma kompresi statistik yang bersifat loseless ! dalam penelitian dan beberapa sumber,

Huffman dapat menghemat antara 20% - 90% "karakter yang paling sering muncul di dalam data dikodekan dengan kode yang jumlah bitnya lebih sedikit"

dan

"karakter yang jarang muncul di dalam data dikodekan dengan kode yang jumlah bitnya lebih panjang" Outline ! Apa itu Huffman Coding ?

Siapa yang memperkenalkannya ?

mengapa Huffman Coding ?? diperkenalkan oleh Professor David A. Huffman loseless = kualitas saat dipulihkan sama saat sebelum di kompresi

loosy = kualitas cenderung berkurang saat dipulihkan apa saja yang dihemat ?

1 . Storage atau tempat penyimpanan

2. Waktu Transmisi ! “A Method for the Construction of Minimum Redudancy Codes” , 1952 Utk sumber S = {x1, …, xn};
Probabilitas P = {p1, ….., pn};
Codewords {c1, ….., cn}; dan
Panjang {l1, ….., ln}.
Terdapat optimal binary prefix code dengan karakteristik :

(a) Jika pj > pi, maka lj < li
(b) Dua codeword dari dua simbol dg probabilitas
terendah mempunyai panjang yg sama
(c) Dua codeword terpanjang identik kecuali pada digit
terakhir Huffman Coding ? STATIS ! DINAMIS !

direpresentasikan dalam pohon biner !
- nilai pada cabang nya antara 0 dan 1 !
- 0 berarti menuju anak cabang kiri
- 1 berarti menuju anak cabang kanan

- Titik Akar ?
- Titik Cabang ?
- Titik Daun ? huffman ? statis misal ada simbol
A prob 0,35
B prob 0,17
C prob 0,17
D prob 0,16
E prob 0,15 A = 0,35 B = 0,17 C = 0,17 D = 0,16 E = 0,15 ED = 0,31 CB = 0,34 EDCB = 0,65 A = 0,35 B = 0,17 C = 0,17 D = 0,16 E = 0,15 ED = 0,31 CB = 0,34 EDCB = 0,65 EDCBA = 1 EDCBA = 1 A = 0,35 B = 0,17 C = 0,17 D = 0,16 E = 0,15 ED = 0,31 CB = 0,34 EDCB = 0,65 EDCBA = 1 gambar kita perbagus
dan disesuaikan agar lebih
mirip diagram pohon untuk sisi kiri kasi 0
untuk sisi kanan kasi 1
sehingga kita mendapatkan
kode unik untuk
tiap huruf 111 110 101 100 Huffman ! standard ASCII A = 0 000 01100001
B = 111 001 01100010
C = 110 010 01100011
D = 101 011 01100100
E = 100 100 01100101 bayangkan kita punya file, yang terdiri dari 100.000 huruf,

A = 35.000 huruf
B = 17.000 huruf
C = 17.000 huruf
D = 16.000 huruf
E = 15.000 huruf ASCII ? --> 8 * 100.000 = 800.000 bit = 800k bit Standard --> 3 * 100.000 = 300.000 bit = 300k bit Huffman ! --> ( 1 * 35.000 ) + ( 3 * 65.000 ) = 230.000 bit = 230k bit Kualitas Entropi = 2,232
Total Kode = 230k bit
kode rata rata = 2,3 bit/char
FK = 800k / 230k = 3,478
RK = 230k / 800k = 0,2875
Redudansi = 2,3 - 2,232 = 0,068
Efisiensi = (2,232/2,3) *100% = 97,043% Dinamis misal, kita telah mentransmisikan suatu deretan bit, dan diterima di penerima, 110011110011101100 A = 0,35 B = 0,17 C = 0,17 D = 0,16 E = 0,15 ED = 0,31 CB = 0,34 EDCB = 0,65 EDCBA = 1 110011110011101100 Huffman Decoding ! untuk apa dilakukan kompresi data terutama yang bersifat loseless, jika kita tidak mengembalikan ke bentuk semula,

sehingga kita butuh decoder di sisi penerima syarat utama !

di sisi penerima harus memiliki pohon huffman yang sama pada sisi pengirim merupakan pengembangan dari Algoritma Huffman disebut juga
Adaptive Huffman Coding dikembangkan oleh
Newton Faller (1973) & Robert G G (1978)

diperbaiki oleh
Donald Knuth (1985) & Jeffrey S. Vitter (1987) algoritma ini cenderung dinamis meng-update dua pohon Huffman identik di sisi Encoder dan Decoder Contoh !

"banana"

akan kita kompress menggunakan Logaritma ini ! inisialisasi pohon r 0
NYT 0
NYT B 1 Karakter = b 0
NYT B 1 Karakter = b 0
NYT 1 B 1 A Karakter = a Karakter = n 0
NYT A N B B A 0
NYT N B A(2) 0
NYT N Karakter = a B A(2) 0
NYT N B A(2) 0
NYT N(2) Karakter = n B A(2) 0
NYT N(2) B A(3) 0
NYT N(2) Karakter = a output = 0 output = 101 output = 11 output = 00 'n' output = 0 'a' Output = 'b' (secara ascii) Output = 'b' (secara ascii) A = 0,35 B = 0,17 C = 0,17 D = 0,16 E = 0,15 ED = 0,31 CB = 0,34 EDCB = 0,65 EDCBA = 1 0 dari apa yang telah kita lakukan tadi, kita dapat sebuah deretan B 'b' A 0'a' N 00'n' A 11 N 101 A 0 1100010 - 01100001 - 001101110 - 11 - 101 - 0 karakter terkirim = 6 bit tanpa kompresi = 6 * 8 = 48 bit dengan kompresi = 30 Rasio Kompresi = (48-30)/48 *100% = 37,5% mrizkifadhilah
10/296548/tk/36164 simple way for compression teknologi Informasi UGM
Full transcript