Metode Dasar Kompresi - Huffman Tree

METODE DASAR KOMPRESI

HUFFMAN TREE

Kompresi merupakan cara memperkecil ukuran citra dengan cara pemampatan data. Dalam artikel ini akan dibahas teknik kompresi menggunakan Metode Huffman yaitu dengan cara memanfaatkan karakter yang muncul secara berulang-ulang.

Algoritma Huffman adalah algoritma pemampatan citra yang menggunakan pendekatan statistic.

Adapun contoh proses encode algoritma ini adalah sebagai berikut:

Kode ASCII string “ABBABABACAACDDD”

1.    Hitung jumlah kemunculan setiap karakter.

2.    Urutkan nilai-nilai grayscale berdasarkan frekuensi kemunculannya.

3.    Gabungkan dua buah pohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.

4.    Ulangi langkah (3) sampai membentuk sebuah pohon biner.

5.    Berikan label pada pohon biner tersebut dengan cara sisi kiri pohon diberi label 0 dan sisi kanan pohon diberi label 1.

6.    Telusuri pohon biner dari akar ke daun. Barisan label-label sisi dari akar ke daun adalah kode Huffman.

A = 1               (1 bit)
B = 01             (2 bit)
C = 001          (3 bit)
D = 000          (3 bit)

Jadi untuk Kode ASCII string “ABBABABACAACDDD” menjadi 10101101101100111001000000000

Rasio sebelum pemampatan = 15 x 8 bit = 120 bit
Rasio setelah pemampatan = (6 x 1 bit) + (4 x 2 bit) + (2 x 3 bit) + (3 x 3 bit) = 29 bit
Jadi persentase rasionya adalah 100% - (29/120 x 100%) = 75.8 %