;
Prinsip
kode
Huffman:
- karakter
yang paling sering muncul
di dalam data
dengan
kode
yang lebih
pendek;
- sedangkan
karakter
yang relatif
jarang muncul
dikodekan
dengan
kode
yang lebih panjang.
Fixed-length code
Karakter
a
b c d e f
----------------------------------------------------------------
Frekuensi 45%
13% 12% 16%
9% 5%
Kode 000
001 010 011
100 111
‘bad’ dikodekan
sebagai
‘001000011’
Pengkodean
100.000 karakter
membutuhkan
300.000 bit.
Variable-length code (Huffman code)
Karakter
a
b c d e f
------------------------------------------------------------------------
Frekuensi 45% 13%
12% 16% 9%
5%
Kode 0 101 100
111 1101 1100
‘bad’ dikodekan
sebagai
‘1010111 ’
Pengkodean
100.000 karakter
membutuhkan
(0,45 ´
1 + 0,13 ´
3 + 0,12 ´
3 + 0,16 ´
3 + 0,09 ´
4 + 0,05 ´
4) ´
100.000 = 224.000 bit
Nisbah
pemampatan:
(300.000 – 224.000)/300.000 ´
100% = 25,3%
Algoritma Greedy untuk Membentuk Kode Huffman:
1.Baca semua karakter di dalam data untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun data dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut.
2.Terapkan strategi greedy sebagai berikut: gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon penyusunnya.
3.Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman.
Kompleksitas algoritma Huffman: O(n log n) untuk n karakter.
Karakter a b c d e f
Frekuensi 45 13 12 16 9 5
Langkah Langkahnya :
Maka,
Karakter a b c d e f
------------------------------------------------------------------------
Frekuensi 45% 13% 12% 16% 9% 5%
Kode 0 101 100 111 1101 1100
‘bad’ dikodekan sebagai ‘1010111 ’
Pengkodean 100.000 karakter membutuhkan
(0,45 ´ 1 + 0,13 ´ 3 + 0,12 ´ 3 + 0,16 ´ 3 + 0,09 ´ 4 + 0,05 ´ 4) ´ 100.000 = 224.000 bit
Nisbah pemampatan:
(300.000 – 224.000)/300.000 ´ 100% = 25,3%
0 komentar:
Posting Komentar