Lesson 8
Run Length Encoding (RLE) dan BW Transform
RLE • Teknik untuk mengurangi ukuran data yang mengandung simbol berulang • Simbol yang berulang diistilahkan run • Teknik kompresi yang paling sederhana • Digunakan untuk kompresi 1. Teks 2. Image Black and White (BW)
RLE pada Teks • Simbol yang berulang, disebut run. • 1 run biasanya di-encode ke dalam 2byte data. • Byte pertama merepresentasikan jumlah simbol, disebut run count. • Byte kedua merepresentasikan simbol yang berulang, disebut run value.
Contoh-1 • Sebuah string AAAAAAAAAAAAAAA, direpresentasikan dalam 15 byte data. • Dengan RLE, di-encode menjadi 2 bytes data: 15A (ingat 1 buah paket RLE ≈ 2 bytes)
• Byte pertama: 15, run count. • Byte kedua: A, run value.
Contoh-2 • Sebuah string AAAAAAbbbXXXXXt direpresentasikan dalam 15 bytes data • Dengan RLE, diencode menjadi: 6A3b5X1t
Contoh-3 • Perhatikan string berikut. Xtmprsqzntwlfb • Tanpa kompresi, direpresentasikan dalam 14 bytes data. • Dengan RLE, diencode menjadi: 1X1t1m1p1r1s1q1z1n1t1w1l1f1b • 14 paket RLE, 28 bytes!
Kesimpulan? • RLE pada teks cocok untuk mengkompresi data teks yang mengandung banyak pengulangan simbol
Latihan • Encode menggunakan RLE string BBDAAADDDRAAB
RLE pada Image BW • Diimplementasikan pada transmisi data melalui fax • Pada image BW: – Hitam direpresentasikan oleh bit ‘1’ – Putih direpresentasikan oleh bit ‘0’ • Beberapa variasi RLE untuk image BW: 1. Standard CCITT No. 2 dan 4 2. JR (Japanesse Recommendation) Standard CCITT Group 3
Standard CCITT No. 2 dan 4 • Hasil encoding berupa rangkaian nilai integer yang menunjukkan banyaknya pixel berwarna putih (bit ‘0’) dan hitam (bit ‘1’) secara bergantian • Warna pertama yang dinyatakan di dalam encoding adalah warna putih – Putih – hitam – putih – hitam – dst..
Standard CCITT No. 2 dan 4-lanj. • Misalkan terdapat rangkaian bit pixel sebagai berikut: – 00000111100000000111111000 • Hasil encode: 5, 4, 8, 6, 3
– 11111100000110000001111110 0 • Hasil encode: 0, 6, 5, 2, 5, 6, 2
JR CCITT G.3 • Karena image yang dikompresi adalah image BW, maka hanya ada 2 transisi warna yang mungkin di dalam image yaitu: – Transisi Black-White (B/W) – Transisi White-Black (W/B)
• Yang disimpan sebagai hasil encoding adalah posisi pixel yang merupakan posisi transisi W/B atau B/W • Diasumsikan terdapat pixel putih imajiner di sebelah kiri pixel aktual
JR CCITT G.3-lanj. • Perhatikan ilustrasi berikut: •
• •
• •
• •
• •
• •
•
•
•
•
• •
•
•
• Pixel transisi ditandai oleh dot, baik transisi W/B atau pun B/W • Karena diasumsikan terdapat pixel putih imajiner di sebelah kiri pixel aktual, maka transisi pertama pasti merupakan transisi W/B
Contoh-1 • Diketahui citra BW 5 x 5 sebagai berikut. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
• Tentukan hasil RLE menurut JR CCITT G.3. • Jawaban : 3, 5, 6, 9, 12, 14, 15, 16, 18, 24,26 • Catatan : integer terakhir menunjukkan batas (pixel imajiner)
Latihan • Tentukan hasil RLE menurut CCITT 2/4 dan JR CCITT G.3 untuk gambar berikut ini.
Burrows-Wheeler Transform • Merupakan teknik transformasi teks yang terkenal • Digunakan untuk preconditioning string/teks sebelum kompresi • Ditemukan oleh Mike Burrows dan David Wheeler
Prinsip Dasar • Merotasi setiap karakter pada string • Jika string terdiri atas N buah karakter,
maka dilakukan rotasi per karakter sebanyak N-1 kali • Lalu disorting ascending • Ambil string pada kolom terakhir sebagai
hasil transformasi BW • Simpan indeks baris yang berisi string
awal (indeks mulai dari 0)
Contoh-1
Contoh-1 Lanj. • Hasil Transformasi BW di atas adalah string BNN^AA@A dan indeks key 6 • Dengan dua informasi tersebut, dapat diperoleh kembali string awal (invers tranformasi)
Invers Transformasi Misalkan hasil transformasi BW yang akan didecode adalah S yang terdiri atas N buah karakter 1. Sorting string S secara ascending, misalkan S* 2. Rangkaikan string S dengan hasil sorting tersebut 3. Lakukan sorting terhadap string hasil panggabungan 4. Rangkaikan string S dengan hasil sorting no.3 5. Ulangi langkah 3 dan 4 hingga diperoleh string dengan N buah karakter 6. String asli ada di nomor indeks key
Contoh Transformasi Invers
Contoh-2 • Cari hasil tranformasi BurrowsWheeler untuk string “adaadasaja”
Kesimpulan • Apa manfaat transformasi BW?
