Kompresi Run length Encodin(RLE)

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.

Implementasi RLE Compression tipe 1 di PHP:

<?php
//input kata
$kata = "AABCCCCCCCCDEFGGGGD77777FFF";
//pecah $kata menjadi huruf
$huruf = str_split($kata);
//hitung jumlah huruf
$N = count($huruf);
//simpan hasil kompresi di $output
$output = "";
$count=1;
$s = $huruf[0];
//proses kompresi
for($i=1;$i<=$N;$i++){

 $b = $huruf[$i];
 //jika huruf[i] = huruf[i+1]
 if($b == $s){
 $count++;
 }elseif($count==1){//jika huruf yg sama 1x cetak $s 1x
 $output .= $s;
 $s = $b;
 $count = 1;
 }elseif($count==2){//jika huruf yg sama 2x cetak $s 2x
 $output .= $s . $s;
 $s = $b;
 $count = 1;
 }elseif($count==3){//jika huruf yg sama 3x cetak $s 3x
 $output .= $s . $s . $s;
 $s = $b;
 $count = 1;
 }elseif($count >= 4){//jika huruf yg sama dengan atau lebih dari 4 cetak $s N kali
 $output .= $s . "!" .$count;
 $s = $b;
 $count =1;
 }
}
//tampilkan input kata
echo "INPUT = ".$kata;
echo "<p></p>";
//tampilkan output
echo "OUTPUT = ".$output;

?> 


 

Implementasi RLE decompression tipe 1 di PHP:
 
<?php
//input kata
$kata = "AAABC!8DEFG!4D7!5FFF";
echo "INPUT = ".$kata;
$huruf = str_split($kata);
$N = count($huruf);
$output = "";

for($i=0;$i<$N;$i++){
 $a = $huruf[$i];
 //apakah huruf[i] = '!'?
 if($a == "!"){
 $x = $huruf[$i+1];//ambill huruf setelah tanda !
 //cetak karakter sebayak $x
 for($j=0;$j<$x-1;$j++){
 $output .= $s;
 }
 //ganti angka dengn ""
 $kata = str_replace($x, "", $kata);
 $huruf = str_split($kata);
 }else{
 $output .= $a;
 $s = $a;
 }
}

echo "<p></p>";
echo "OUTPUT = ".$output;
?>

 

source kompresi bisa di download disini
Sumber : http://blog.unila.ac.id/muh47ir/2008/12/26/teori-informasi/
					

			

				Advertisements