COMPRESSION
Tujuan :
- Untuk memampatkan text/string
Dampak :
- Mempersingkat pengiriman data di jaringan
- Membuat text/string tidak dapat dimengerti(mirip cryptography)
Cara Kerja :
- Memanfaatkan karakter yang muncul berulang-ulang
- contoh : metode Huffman, metode LZ
Cara kerja metode Huffman
- Membentuk Huffman Tree
- Hitung jumlah pemunculan dari setiap karakter
- Buat simpul untuk setiap karakter
- Simpul diurutkan berdasarkan jumlah pemunculkan dari kiri kekanan secara descending
- Dua simpul yang terkecil (2 simpul yang paling kanan) digabungkan, sehingga membentuk simpul baru
- Simpul baru ini di posisikan sejajar dengan simpul-simpul sebelumnya yang tidak ikut digabungkan
- Lakukan proses 3-5 terus menerus sampai didapat hanya sebuah simpul saja(root)
- Akan terbentuk pohon Huffman (Huffman Tree)
- Path pada Huffman Tree diberi label, yang kekiri diberi label 0 dan yang kekanan diberi label 1
- Hasil kompresi didapat dengan menelusuri path dari root sampai kesimpul daun(simpul yang tidak punya anak).
Contoh :
String yang mau dikompress adalah :
AKUSUKASASA
1. Hitung jumlah penggunaan dari setiap karakter, didapat
- A muncul 4 buah
- K muncul 2 buah
- U muncul 2 buah
- S muncul 3 buah
5. simpul baru ini di posisikan sejajar dengan simpul-simpul sebelumnya yang tidak ikut digabungkan.
3.Simpul diurutkan berdasarkan jumlah penggunaan dari kiri kekanan secara descending
5. simpul baru ini di posisikan sejajar dengan simpul-simpul sebelumnya yang tidak ikut digabungkan.
Contoh (AKUSUKASASA)
A- 1
S- 01
K- 000
U- 001
AKUSUKASASA =
1000001010010001011011
A- 1
K- 000
U- 001
S - 01
U- 001
K- 000
A- 1
S- 01
A- 1
S- 01
A- 1
Sehingga jika di gabung menjadi : 1000001010010001011011
0 Komentar