Pada suatu saat lewat pada jalan tersebut serombongan tentara yang berjumlah 40 orang, semuanya memakai seragam berwarna hijau. Mahasiswa pertama menulis pada buku pencatat “hijau, hijau, hijau …. “ sampai 40 kali, tapi mahasiswa kedua ternyata lebih cerdik, dia hanya menulis pada buku pencatat “hijau 40 x”.
Setelah selesai melaksanakan tugas mereka, ternyata mahasiswa pertama menghabiskan 10 lembar catatan, sedangkan mahasiswa kedua hanya menghabiskan 5 lembar catatan, sedangkan hasil mereka tidak ada bedanya.
Cara yang digunakan oleh mahasiswa kedua tersebut dapat digunakan pada pemampatan file, dan dikenal dengan algoritma Run-Length.
Algoritma Run-length digunakan untuk memampatkan data yang berisi karakter-karakter berulang. Saat karakter yang sama diterima secara berderet empat kali atau lebih (lebih dari tiga), algoritma ini mengkompres data dalam suatu tiga karakter berderetan. Algoritma Run-Length paling efektif pada file-file grafis, dimana biasanya berisi deretan panjang karakter yang sama.
Metode yang digunakan pada algoritma ini adalah dengan mencari karakter yang berulang lebih dari 3 kali pada suatu file untuk kemudian diubah menjadi sebuah bit penanda (marker bit) diikuti oleh sebuah bit yang memberikan informasi jumlah karakter yang berulang dan kemudian ditutup dengan karakter yang dikompres, yang dimaksud dengan bit penanda disini adalah deretan 8 bit yang membentuk suatu karakter ASCII. Jadi jika suatu file mengandung karakter yang berulang, misalnya AAAAAAAA atau dalam biner 01000001 sebanyak 8 kali, maka data tersebut dikompres menjadi 11111110 00001000 01000001. Dengan demikian kita dapat menghemat sebanyak 5 bytes. Agar lebih jelas algoritma Run-Length dapat digambarkan sebagai berikut :
Deretan data sebelah kiri merupakan deretan data pada file asli, sedangkan deretan data sebelah kanan merupakan deretan data hasil pemampatan dengan algoritma Run-Length. Langkah-langkah yang dilakukan adalah :- Lihat apakah terdapat deretan karakter yang sama secara berurutan lebih dari tiga karakter, jika memenuhi lakukan pemampatan. Pada contoh di atas deretan karakter yang sama secara berurutan sebanyak 8 karakter, jadi lebih dari tiga dan dapat dilakukan pemampatan.
- Berikan bit penanda pada file pemampatan, bit penanda disini berupa 8 deretan bit yang boleh dipilih sembarang asalkan digunakan secara konsisten pada seluruh bit penanda pemampatan. Bit penanda ini berfungsi untuk menandai bahwa karakter selanjutnya adalah karakter pemampatan sehingga tidak membingungkan pada saat mengembalikan file yang sudah dimampatkan ke file aslinya. Pada contoh di atas bit penanda ini dipilih 11111110.
- Tambahkan deretan bit untuk menyatakan jumlah karakter yang sama berurutan, pada contoh diatas karakter yang sama berturutan sebanyak delapan kali, jadi diberikan deretan bit 00001000 (8 desimal).
- Tambahkan deretan bit yang menyatakan karakter yang berulang, pada contoh diatas karakter yang berulang adalah 01000001 atau karakter A pada karakter ASCII.
- Lihat karakter pada hasil pemampatan satu-persatu dari awal sampai akhir, jika ditemukan bit penanda, lakukan proses pengembalian.
- Lihat karakter setelah bit penanda, konversikan ke bilangan desimal untuk menentukan jumlah karakter yang berurutan.
- Lihat karakter berikutnya, kemudian lakukan penulisan karakter tersebut sebanyak bilangan yang telah diperoleh pada karakter sebelumnya (point 2).
00001111
11110000
11110000
11110000
11110000
11110000
11110000
10101010
10101010
10101010
Jika dimampatkan dengan metoda Run-Length, hasilnya akan menjadi
00001111
11111110
00000110
10101010
10101010
10101010
Dengan langkah-langkah pengembalian yang telah dijelaskan di atas, akan didapatkan hasil yang sama seperti file aslinya.
