Algoritma Rice Coding / Rice-Golomb Coding

Algoritma Rice Coding / Rice-Golomb Coding 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.
Rice Coding menggunakan sistem yang diperoleh dari teknik Golomb Coding, dimana teknik ini dapat menghasilkan kode prefix yang lebih mudah, tetapi dengan kemungkinan untuk tidak optimal. Ketika Golomb Coding memiliki parameter yang dapat diubah menjadi sebuah nilai positif apa saja, Rice Coding memiliki parameter yang dapat diubah hanya menjadi kelipatan dari angka 2 saja. Hal ini menyebabkan teknik Rice Coding mudah diimplementasikan dalam kasus aritmatika biner secara efisien.
Rice Coding biasanya digunakan pada proses encoding entropi dalam kompresi tipe gambar dan audio. Oleh sebab itu, dalam kasus kompresi data string, hasilnya tidak berbeda dengan data awal yang digunakan.

Langkah-langkah penggunaan algoritma ini adalah

* Tentukan kalimat yang digunakan sebagai data input
Diasumsikan data input adalah sebagai berikut:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

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) {}
Dim ukuranKompresiData As Integer = Compress(inputData, KompresiData, ukuranInputData)

* Gunakan fungsi ini untuk melakukan kompresi data

Public Function Compress(input As Byte(), output As Byte(), ukuranInput As UInteger) As Integer
	Dim stream As New BitStream()
	Dim i As UInteger, x As UInteger, k As UInteger, n As UInteger, ukuranString As UInteger = 8
	Dim histogram As UInteger() = New UInteger(HISTORY - 1) {}
	Dim j As Integer

	Dim incount As UInteger = ukuranInput / (ukuranString >> 3)

	If incount = 0 Then
		Return 0
	End If

	inisialisasiBitStream(stream, output, ukuranInput + 1)
	k = 0

	i = 0
	While (i < HISTORY) AndAlso (i < incount)
		n = CUInt(jumlahBits(input(i)))
		k += n
		i += 1
	End While

	k = (k + (i >> 1)) / i

	If k = 0 Then
		k = 1
	End If

	output(0) = CByte(k)
	stream.PosisiBit = 8

	i = 0
	While (i < incount) AndAlso ((stream.PosisiBit >> 3) <= ukuranInput)
		If i >= HISTORY Then
			k = 0

			For j = 0 To HISTORY - 1
				k += histogram(j)
			Next

			k = (k + (HISTORY >> 1)) / HISTORY
		End If

		x = input(i)
		encodeString(x, CInt(k), stream)
		histogram(i Mod HISTORY) = CUInt(jumlahBits(x))
		i += 1
	End While

	If i < incount Then
		output(0) = 0
		stream.PosisiBit = 8

		For i = 0 To incount - 1
			x = input(i)

			For j = CInt(ukuranString) - 1 To 0 Step -1
				tulisBit(stream, CInt((x >> j) And 1))
			Next
		Next
	End If

	Return CInt((stream.PosisiBit + 7) >> 3)
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), ukuranInputData)

* Gunakan fungsi ini untuk melakukan pengembalian data kompresi

Public Sub Decompress(input As Byte(), output As Byte(), ukuranInput As UInteger, ukuranOutput As UInteger)
	Dim stream As New BitStream()
	Dim i As UInteger, x As UInteger, k As UInteger, ukuranString As UInteger = 8
	Dim histogram As UInteger() = New UInteger(HISTORY - 1) {}
	Dim j As Integer

	Dim outputCount As UInteger = ukuranOutput / (ukuranString >> 3)

	If outputCount = 0 Then
		Return
	End If

	inisialisasiBitStream(stream, input, ukuranInput)
	k = CUInt(input(0))
	stream.PosisiBit = 8

	If k = 0 Then
		For i = 0 To outputCount - 1
			x = 0

			For j = CInt(ukuranString) - 1 To 0 Step -1
				x = CUInt(CInt(x << 1) Or bacaBit(stream))
			Next

			output(i) = CByte(x)
		Next
	Else
		For i = 0 To outputCount - 1
			If i >= HISTORY Then
				k = 0

				For j = 0 To HISTORY - 1
					k += histogram(j)
				Next

				k = (k + (HISTORY >> 1)) / HISTORY
			End If

			x = decodeString(CInt(k), stream)
			output(i) = CByte(x)
			histogram(i Mod HISTORY) = CUInt(jumlahBits(x))
		Next
	End If
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)

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.