Pengetahuan tentang Run Lenght Encoding

Run Lenght Encoding (RLE) adalah algoritma kompresi data yang paling mendasar. Tidak diketahui secara pasti  kapan  algoritma kompresi ini pertama kali ditemukan (Campos,1999). Algoritma Run Length Encoding termasuk ke dalalm type kompresi Lossless. Ide dasar algoritma ini adalah dengan mereduksi string-string yang berulang, disebut  run, kemudian akan disimbolkan menjadi 2 byte.Penjelasan dari 2 byte hasil reduksi  tersebut adalah sebagai berikut. Byte yang pertama merepresentasi jumlah string  yang berulang, disebut dengan run count. Run count ini bernilai antara 1 sampai 127 atau 1 sampai 255, tergantung pada jumlah yang memory disediakan , 128 ataukah 256. Byte kedua adalah  ‘karakter’ dari run itu sendiri, byte yang kedua ini disebut dengan run value dengan rentan nilai 0 samapai 255.

Cara kerja algoritma ini dapat di contohkan sebagai berikut , misal kita mempunyai  string berupa “AAAAAAAAAAAAAAAAAA”. Setelah dimampatkan string tersebut akan direpresentasikan menjadi “15A”. Kode “15A” disebut  dengan paket RLE.  Angka  “15” merepresentasikan banyaknya karakter yang berulang. Sedangkan   “A” adalah nilai dari String.Paket RLE akan dibuat setiap kali karakter dari string berubah atau ketika  banyaknya karakter yang berulang melebihi kapasitas maksimum penyimpanan. MIsalkan ada : ”AAAAAAbbXXXXt”. Setelah dimampatkan  akan disimbolkan menjadi “6A3b4X1t”.

Algoritma RLE ini menjadi tidak efektif ketika string input mempunyai karakter yang sangat  bervariasi. Misalkan string “Xtmprsqzntwlfb”. Setelah dilakukan pemampatan nilai maka hasil yang didapatkan adalah “1X1t1m1p1r1s1q1z1n1t1w1l1f1b”. dengan sususnan string seperti ini, diperoleh dari pengkodean bukan merupakan bentuk yang lebih mampat, tapi sebaliknya hasil pengkodean menjadi lebih panjang dari string asli.

          Semakin bervariasi string yang kita temui makan rasio pemampatan algoritma RLE akan menjadi semakin buruk. Algoritma Run-length encoding biasa digunakan pada kompresi image. Karena dalam file image variasiasi perubahan karakternya relatif  lebih kecil sehingga bias menghasilkan rasio kompresi yang lebih baik, Walaupun algoritma ini mempunyai waktu pemempatan yang relatif lebih singkat dari pada alagiritma kompresi yang lain, tapi mempunya kekurangan yang  lain yaitu rasio pemampatannya tergantung terhadap urutan karakter dari string yang ditemiu.

 Alur kerja algoritma RLE ditunnjukan pada gambar di bawah ini