Algoritma Run Length Encoding Compression

Kompresi adalah suatu teknik atau cara pemampatan data sehingga hanya diperlukan penyimpanan data kecil dan merampingkan data untuk mempersingkat waktu pengiriman data.

Ada dua jenis data kompresi:

  1. Lossless, artinya tidak ada informasi yang hilang selama proses kompresi. Oleh karena itu, arsip terkompresi dapat sepenuhnya dikembalikan ke versi asli ketika didekompresi.
    Metode: Run-length Encoding, Huffman, delta, dan LZW
  2. Lossy, itu berarti ada data yang hilang selama proses kompresi. Metode: CS&Q (coarser sampling and/or quantization)
Analogi Jenis Compression

Catatan: untuk kompresi data penting (catatan bank, artikel teks dll.) sebaiknya menggunakan teknik lossless supaya tidak ada data yang hilang karena proses kompresi.

Kompresi dan dekompresi data menggunakan run-length encoding (RLE) ini merupakan suatu bentuk teknik yang digunakan untuk mengkompresi data yang berisi karakter-karakter berulang.

Berikut contoh algoritma Run-length Encoding

Example Run-length Coding

Pada gambar atau media citra proses compresi dengan metode RLE ini, dapat di analogikan seperti pada gambar berikut ini.

RLE Gambar/Icons

Tambahan, pada suatu gambar pasti terdiri dari pixel warna, jadi proses compresing pada metode RLF dilakukan dengan mengurangi bit pada pola warna yang sama atau setidaknya memiliki kemiripan yang sangat dekat.

Kesimpulan:

  • Run-length encoding (RLE) merupakan metode kompresi data yang sangat sederhana
  • Teknik kompresi dengan RLE ini berguna untuk data yang banyak memiliki kesamaan dan data tersebut berdekatan, misal teks ataupun grafik seperti icon atau gambar garis-garis yang banyak memilki kesamaan pola.

Ada kasus seperti berikut:

Kita akan mengkompress
teks: X Y Z = 3 bit
Jika kita coba gunakan RLE maka akan jadi seperti ini:
teks: 1X1Y1Z = 6 bit

Loh, gimana justru malah makin banyak ya? bukannya kompresi malah jadi ekspansi..
Nah jadi, algoritma ini memang digunakan khusus untuk data yang memiliki tingkat ke homogen-an tinggi ya, yang matching datanya banyak, dan tidak cocok untuk data yang tidak memiliki tingkat maching yang tinggi.

Worst Case: Tingkat Homogen Sedikit cendrung tidak ada
Best Case: Banyak data matching/homogen

Code JAVA algoritma RLF

import java.util.*;
public class RLF{
    public static void main(String[] args) {
      RunLength();
    }
}
public class RunLength {
  private final static int R = 256;
  private final static int lgR = 8;
  public static void compress(){
    
  }
  public static void expand(){
    boolean bit = false;
    while (!BinaryStdIn.isEmpty()) {
      int run = BinaryStdIn.readInt(lgR);
      for (int i = 0; i < run; i++) {
        BinaryStdOut.write(bit);
      bit = !bit;
      }
      BinaryStdOut.close();
      
    }
  }
  
}

Output:

Output Binary Icons

Tutorial Video:

Video Explaining

Leave a Reply

Your email address will not be published. Required fields are marked *