Algoritma RLE (Run Length Encoding)


Algoritma RLE (Run Length Encoding) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi data sehingga ukuran data yang dihasilkan menjadi lebih rendah dari ukuran sebenarnya. Contoh yang dibahas kali ini adalah mengenai kompresi dan pengembalian data dari sebuah kalimat.
RLE (Run Length Encoding) adalah bentuk paling mudah dari teknik kompresi data lossless dimana sederetan data dengan nilai yang sama secara berurutan akan disimpan menjadi sebuah nilai data dan jumlahnya. Algoritma ini sangat berguna pada data yang memiliki banyak data dengan nilai yang sama secara berurutan seperti file ikon, gambar garis, dan animasi. Algoritma ini tidak cocok diterapkan pada data normal karena akan hal tersebut akan mengakibatkan semakin bertambahnya ukuran data kompresi dibandingkan data awalnya


Langkah-langkah penggunaan algoritma ini adalah

* Tentukan kalimat yang digunakan sebagai data input
Diasumsikan data input adalah sebagai berikut:
LLLLLLoooooooooorrrrrrrrrrreeeeeeeeeeemmmmmmm IIIIIIIppppppppppsssssssuuuuuuuuuummmmmmmmm

1. Hitung ukuran data yang digunakan dalam perhitungan sebagai penanda ukuran data sebelum dilakukan kompresi

Dim inputData As Byte() = System.Text.Encoding.[Default].GetBytes(input)
Dim ukuranInputData As UInteger = CUInt(input.Length)
Console.WriteLine("Ukuran input data = " & ukuranInputData)

2. Lakukan proses kompresi data menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim KompresiData As Byte() = New Byte(ukuranInputData * (257 / 256)) {}
Dim ukuranKompresiData As Integer = Compress(inputData, KompresiData, ukuranInputData)

* Gunakan fungsi ini untuk melakukan kompresi data

Public Function Compress(input As Byte(), ByRef output As Byte(), ukuranInput As UInteger) As Integer
	Dim byte1 As Byte, byte2 As Byte, penanda As Byte
	Dim i As UInteger, posisiInput As UInteger, posisiOutput As UInteger, count As UInteger
	Dim histogram As UInteger() = New UInteger(255) {}

	If ukuranInput < 1 Then
		Return 0
	End If

	For i = 0 To 255
		histogram(i) = 0
	Next

	For i = 0 To ukuranInput - 1
		histogram(input(i)) += 1
	Next

	penanda = 0

	For i = 1 To 255
		If histogram(i) < histogram(penanda) Then
			penanda = CByte(i)
		End If
	Next

	output(0) = penanda
	posisiOutput = 1

	byte1 = input(0)
	posisiInput = 1
	count = 1

	If ukuranInput >= 2 Then
		byte2 = input(posisiInput)
		posisiInput += 1
		count = 2

		Do
			If byte1 = byte2 Then
				While (posisiInput < ukuranInput) AndAlso (byte1 = byte2) AndAlso (count < 32768)
					byte2 = input(posisiInput)
					posisiInput += 1
					count += 1
				End While

				If byte1 = byte2 Then
					encodeDenganPerulangan(output, posisiOutput, penanda, byte1, count)

					If posisiInput < ukuranInput Then
						byte1 = input(posisiInput)
						posisiInput += 1
						count = 1
					Else
						count = 0
					End If
				Else
					encodeDenganPerulangan(output, posisiOutput, penanda, byte1, count - 1)
					byte1 = byte2
					count = 1
				End If
			Else
				encodeTanpaPerulangan(output, posisiOutput, penanda, byte1)
				byte1 = byte2
				count = 1
			End If
			If posisiInput < ukuranInput Then
				byte2 = input(posisiInput)
				posisiInput += 1
				count = 2
			End If
		Loop While (posisiInput < ukuranInput) OrElse (count >= 2)
	End If

	If count = 1 Then
		encodeTanpaPerulangan(output, posisiOutput, penanda, byte1)
	End If

	Return CInt(posisiOutput)
End Function

3. Dapatkan hasil kompresi data dan ukuran data hasil kompresi yang baru

Dim teksKompresiData As String = System.Text.Encoding.[Default].GetString(KompresiData)

4. Lakukan proses pengembalian data kompresi menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim PengembalianData As Byte() = New Byte(ukuranInputData - 1) {}
Decompress(KompresiData, PengembalianData, CUInt(ukuranKompresiData))

* Gunakan fungsi ini untuk melakukan pengembalian data kompresi

Public Sub Decompress(input As Byte(), output As Byte(), ukuranInput As UInteger)
	Dim penanda As Byte, simbol As Byte
	Dim i As UInteger, posisiInput As UInteger, posisiOutput As UInteger, count As UInteger

	If ukuranInput < 1 Then
		Return
	End If

	posisiInput = 0
	penanda = input(posisiInput)
	posisiInput += 1
	posisiOutput = 0

	Do
		simbol = input(posisiInput)
		posisiInput += 1

		If simbol = penanda Then
			count = input(posisiInput)
			posisiInput += 1

			If count <= 2 Then
				For i = 0 To count
					output(posisiOutput) = penanda
					posisiOutput += 1
				Next
			Else
				If Convert.ToBoolean(count And &H80) Then
					count = ((count And &H7F) << 8) + input(posisiInput)
					posisiInput += 1
				End If

				simbol = input(posisiInput)
				posisiInput += 1

				For i = 0 To count
					output(posisiOutput) = simbol
					posisiOutput += 1
				Next
			End If
		Else
			output(posisiOutput) = simbol
			posisiOutput += 1
		End If
	Loop While posisiInput < ukuranInput
End Sub

5. Dapatkan hasil pengembalian data dan ukuran data hasil hasil pengembalian data kompresi yang baru

Dim teksPengembalianData As String = System.Text.Encoding.[Default].GetString(PengembalianData)
Dim ukuranPengembalianData As UInteger = CUInt(teksPengembalianData.Length)


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd131


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *