Run length Encoding

03.27 Endicka E Prakarsa No comments

Merupakan kompresi data teks yang dilakukan jika terdapat beberapa huruf yang sama ditampilkan secara berturut-turut. Terdapat dua tipe RLE yaitu RLE tipe 1 dan RLE tipe 2.

Contoh :

Data; ABCCCCCCCCDEFGGGG = 17 karakter

Dengan RLE tipe 1 (min. 4 huruf sama) ditulis; ABC8!DEFG!4 = 11 karakter

Dalam RLE tipe 1 ini terdapat suatu karakter yang tidak digunakan dalam teks seperti tanda ‘!’ yang digunakan untuk menandai. Teknik kompresi RLE tipe 1 ini memiliki kelemahan yaitu jika terdapat karakter angka, mana tanda mulai dan tanda akhir? Maka dalam RLE tipe 2 digunakanlah flag bilangan negatif untuk menandai batas sebanyak jumlah karakter tersebut.

Contoh:

Data; ABCCCCCCCCDEFGGGG = 17 Karakter

Dengan RLE tipe 2; -2AB8CDEF4G = 12 Karakter

Contoh:

Data; AB12CCCCDEEEF = 13 Karakter

Dengan RLE tipe 2; -4AB124CD3EF = 12 Karakter

Teknik kompresi dengan RLE ini berguna untuk data yang banyak memiliki kesamaan, misal teks ataupun grafik seperti icon atau gambar garis-garis yang banyak memilki kesamaan pola.

4. Shanon Fano Algoritma

Pada prinsipnya algoritma ini menggunakan pendekatan top down dalam penyusunan binary tree. Metode ini sangat efisien untuk mengompresi file text yang berukuran besar.

Langkah langkah kompresinya adalah :

- Mengurutkan karakter berdasarkan probabilitasnya yang terbesar.

- Membagi menjadi 2 berdasarkan selisih paling sedikit dari nilai dua kelompok karakter yang terurut tadi.

- Secara rekursif dibagi menjadi 2 bagian, setiap bagian memiliki nilai yang sama atau dengan selisih paling sedikit.

- Mengasign nilai 1 kekanan dan 0 ke kiri pada pohon biner.

Contoh :

Source = {A, B, C, D, E }

Peluang={0.35, 0.17, 0.17, 0.16, 0.15}

Membagi menjadi 2 kelompok besar:

- kelompok 1 = A dengan total peluang 0.35 kelompok 2 = B, C, D, E dengan total peluang 0.65 selisih kel 1 dan 2 = 0.30

- kelompok 1 = A, B dengan total peluang 0.52 kelompok 2 = C, D, E dengan total peluang 0.48 selisih kel 1 dan 2 = 0.04 –> paling sedikit

- kelompok 1 = A , B, C dengan total peluang 0.69 kelompok 2 = D, E dengan total peluang 0.31 selisih kel 1 dan 2 = 0.38

Jadi yang digunakan AB dan CDE, dengan tree awalnya yaitu :

Kemudian dari 2 leaf yang terbentuk dilakukan proses pembagian lagi seperti diatas sampai tidak bisa dibagi lagi. Sehingga menghasilkan tree yang lengkap seperti berikut :

Setelah Tree lengkap telah terbentuk maka dilakukan pembacaan dari root sampai ke karakter pada leaf. Dari pembacaan dihasilkan codeword sebagai berikut :

• A = 00 –> 2 bit
• B = 01
• C = 10
• D = 110 –>3bit
• E = 111

Dari code word diatas diperoleh panjang rata-ratanya :

Lavg = 0.35*2 + 0.17*2 + 0.17*2 + 0.16*3 + 0.15 * 3 = 2,31 bit/char

Nilai entropinya yaitu :

H( S ) = H( P1, P2, P3, P4, P5)

=-P1 log P1 -P2 log P2 – P3 log P3 – P4 log P4 – P5 log P5 –> log basis 2

= 2,23 bit/char

Jadi Efisiensinya = H(s)/Lavg = 2,232/2,31=96,67%

Jadi dengan metode ini akan terasa sangat efektif jika banyak terjadi perulangan karakter pada text.

Posted in: MULTIMEDIA