Rice coding
Rice coding is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Rice coding is a variant of Golomb coding where the parameter is a power of two. This makes it easier to encode the remainder of the euclidean division.
Implement Rice coding in your programming language and verify that you can consistently encode and decode a list of examples (for instance numbers from 0 to 10 or something).
Rice coding is initially meant to encode natural numbers, but since relative numbers are countable, it is fairly easy to modify Rice coding to encode them too. You can do that for extra credit.
ALGOL 68
BEGIN # Rice encoding - translation of the Julia sample #
# Golomb-Rice encoding of a positive number to a bit vector #
# (string of 0s and 1s) using M of 2^k #
# dyadic RICEENCODE, allows k to be specified #
PRIO RICEENCODE = 8;
OP RICEENCODE = ( INT n, INT k )STRING:
BEGIN
IF n < 0 THEN print( ( "cannot encode negative numbers", newline ) ); stop FI;
INT m = 2 ^ k;
INT q = n OVER m, r = n MOD m;
STRING result := "";
INT v := r;
WHILE v > 0 DO # set result to binary digits of n #
IF v MOD 2 = 0 THEN "0" ELSE "1" FI +=: result;
v OVERAB 2
OD;
# pad result to k digits #
FOR pad FROM ( UPB result - LWB result ) + 2 TO k DO
"0" +=: result
OD;
"0" +=: result; # add a leading 0 #
FOR leading TO q DO # and q leading 1s #
"1" +=: result
OD;
result
END # RICEENCODE # ;
# monadic RICEENCODE, encodes with k = 2 #
OP RICEENCODE = ( INT n )STRING: n RICEENCODE 2;
CO extended encoding of negative numbers
see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
CO
PRIO RICEENCODEX = 8;
OP RICEENCODEX = ( INT n, INT k )STRING:
IF INT n2 = 2 * n; n < 0 THEN -n2 - 1 ELSE n2 FI RICEENCODE k;
OP RICEENCODEX = ( INT n )STRING: n RICEENCODEX 2;
# Golomb-Rice decoding of a bit vector (string of 0s and 1s) #
# with M of 2^k #
PRIO RICEDECODE = 8;
OP RICEDECODE = ( STRING a, INT k )INT:
BEGIN
INT m = 2 ^ k;
INT zpos := 0;
IF NOT char in string( "0", zpos, a ) THEN zpos := LWB a FI;
INT r := 0;
FOR z FROM zpos TO UPB a DO
r *:= 2;
IF a[ z ] = "1" THEN r +:= 1 FI
OD;
INT q = zpos - LWB a;
q * m + r
END # RICEDECODE # ;
OP RICEDECODE = ( STRING a )INT: a RICEDECODE 2;
# extended to handle negative numbers #
PRIO RICEDECODEX = 8;
OP RICEDECODEX = ( STRING a, INT k )INT:
IF INT i = a RICEDECODE k;
ODD i
THEN - ( ( i + 1 ) OVER 2 )
ELSE i OVER 2
FI # RICEDECODEX # ;
OP RICEDECODEX = ( STRING a )INT: a RICEDECODEX 2;
# right pads s with blanks to w characters #
PRIO PAD = 8;
OP PAD = ( STRING s, INT w )STRING:
IF INT len = ( UPB s - LWB s ) + 1;
len >= w
THEN s
ELSE s + ( ( w - len ) * " " )
FI # PAD # ;
print( ( "Base Rice Coding:", newline ) );
FOR n FROM 0 TO 10 DO
STRING e = RICEENCODE n;
print( ( whole( n, -3 ), " -> ", e PAD 10, " -> ", whole( RICEDECODE e, -3 ), newline ) )
OD;
print( ( "Extended Rice Coding:", newline ) );
FOR n FROM -10 TO 10 DO
STRING e = RICEENCODEX n;
print( ( whole( n, -3 ), " -> ", e PAD 10, " -> ", whole( RICEDECODEX e, -3 ), newline ) )
OD
END- Output:
Base Rice Coding: 0 -> 000 -> 0 1 -> 001 -> 1 2 -> 010 -> 2 3 -> 011 -> 3 4 -> 1000 -> 4 5 -> 1001 -> 5 6 -> 1010 -> 6 7 -> 1011 -> 7 8 -> 11000 -> 8 9 -> 11001 -> 9 10 -> 11010 -> 10 Extended Rice Coding: -10 -> 1111011 -> -10 -9 -> 1111001 -> -9 -8 -> 111011 -> -8 -7 -> 111001 -> -7 -6 -> 11011 -> -6 -5 -> 11001 -> -5 -4 -> 1011 -> -4 -3 -> 1001 -> -3 -2 -> 011 -> -2 -1 -> 001 -> -1 0 -> 000 -> 0 1 -> 010 -> 1 2 -> 1000 -> 2 3 -> 1010 -> 3 4 -> 11000 -> 4 5 -> 11010 -> 5 6 -> 111000 -> 6 7 -> 111010 -> 7 8 -> 1111000 -> 8 9 -> 1111010 -> 9 10 -> 11111000 -> 10
F#
// Rice coding. Nigel Galloway: September 21st., 2023
let rec fN g=[match g with 0->() |_->yield 1; yield! fN(g-1)]
let fI n=let rec fI n g=match List.head g with 1->fI (n+1) (List.tail g) |_->(n,List.foldBack(fun i (n,g)->(n*2,g+n*i)) (List.tail g) (1,0)|>snd) in fI 0 n
let rec fG n g=[match n with 1->yield g%2 |_->yield g%2; yield! fG (n-1) (g/2)]
let encode n g=let q=g/pown 2 n in [yield! fN q; yield 0; yield! fG n g|>List.rev]
let decode n g=let a,b=fI g in a*pown 2 n+b
let test=let test=encode 4 in [for n in 0..17 do yield test n] //encode 0 to 17
test|>List.iter(fun n->n|>List.iter(printf "%d"); printf " -> "; printfn "%d" (decode 4 n)) //print the encoded values and the decoded values
- Output:
00000 -> 0 00001 -> 1 00010 -> 2 00011 -> 3 00100 -> 4 00101 -> 5 00110 -> 6 00111 -> 7 01000 -> 8 01001 -> 9 01010 -> 10 01011 -> 11 01100 -> 12 01101 -> 13 01110 -> 14 01111 -> 15 100000 -> 16 100001 -> 17
FreeBASIC
Function RiceEncode(n As Integer, k As Integer = 2, extended As Boolean = False) As String
If extended Then n = Iif(n < 0, -2*n-1, 2*n)
Dim As Integer m = 2 ^ k
Dim As Integer q = n \ m
Dim As Integer r = n Mod m
Return String(q, "1") & Right("00000000" & Bin(r), k + 1)
End Function
Function RiceDecode(a As String, k As Integer = 2, extended As Boolean = False) As Integer
Dim As Integer m = 2 ^ k
Dim As Integer q = Instr(a, "0") - 1
Dim As Integer r = Val("&B" & Mid(a, q + 2))
Dim As Integer i = q * m + r
If extended Then i = Iif(i Mod 2, -(i +1) \ 2, i \ 2)
Return i
End Function
Dim As Integer n
Dim As String s
Print "Base Rice Coding:"
For n = 0 To 10
s = RiceEncode(n)
Print Using "& -> & -> &"; n; s; RiceDecode(s)
Next n
Print "Extended Rice Coding:"
For n = -10 To 10
s = RiceEncode(n, 2, True)
Print Using "& -> & -> &"; n; s; RiceDecode(s, 2, True)
Next n
Sleep
- Output:
Same as Phix entry.
Julia
""" Golomb-Rice encoding of a positive number to bit vector using M of 2^k"""
function rice_encode(n::Integer, k = 2)
@assert n >= 0
m = 2^k
q, r = divrem(n, m)
return [fill(true, q); false; Bool.(reverse(digits(r, base=2, pad=k)))]
end
""" see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers """
extended_rice_encode(n, k = 2) = rice_encode(n < 0 ? -2n - 1 : 2n, k)
""" Golomb-Rice decoding of a vector of bits with M of 2^k """
function rice_decode(a::Vector{Bool}, k = 2)
m = 2^k
zpos = something(findfirst(==(0), a), 1)
r = evalpoly(2, reverse(a[zpos:end]))
q = zpos - 1
return q * m + r
end
extended_rice_decode(a, k = 2) = (i = rice_decode(a, k); isodd(i) ? -((i + 1) ÷ 2) : i ÷ 2)
println("Base Rice Coding:")
for n in 0:10
println(n, " -> ", join(map(d -> d ? "1" : "0", rice_encode(n))),
" -> ", rice_decode(rice_encode(n)))
end
println("Extended Rice Coding:")
for n in -10:10
println(n, " -> ", join(map(d -> d ? "1" : "0", extended_rice_encode(n))),
" -> ", extended_rice_decode(extended_rice_encode(n)))
end
- Output:
Base Rice Coding: 0 -> 000 -> 0 1 -> 001 -> 1 2 -> 010 -> 2 3 -> 011 -> 3 4 -> 1000 -> 4 5 -> 1001 -> 5 6 -> 1010 -> 6 7 -> 1011 -> 7 8 -> 11000 -> 8 9 -> 11001 -> 9 10 -> 11010 -> 10 Extended Rice Coding: -10 -> 1111011 -> -10 -9 -> 1111001 -> -9 -8 -> 111011 -> -8 -7 -> 111001 -> -7 -6 -> 11011 -> -6 -5 -> 11001 -> -5 -4 -> 1011 -> -4 -3 -> 1001 -> -3 -2 -> 011 -> -2 -1 -> 001 -> -1 0 -> 000 -> 0 1 -> 010 -> 1 2 -> 1000 -> 2 3 -> 1010 -> 3 4 -> 11000 -> 4 5 -> 11010 -> 5 6 -> 111000 -> 6 7 -> 111010 -> 7 8 -> 1111000 -> 8 9 -> 1111010 -> 9 10 -> 11111000 -> 10
Lua
do -- Rice encoding - translation of the Julia sample
-- Golomb-Rice encoding of a positive number to a bit vector (string of 0s and 1s) using M of 2^k
local function rice_encode( n, k )
assert( n >= 0 )
k = k or 2
local m = math.floor( 2^k )
local result, q, r = {}, math.floor( n / m ), n % m
while r > 0 do
result[ #result + 1 ] = r % 2 == 0 and "0" or "1"
r = math.floor( r / 2 )
end
while #result < k do result[ #result + 1 ] = "0" end
result[ #result + 1 ] = "0"
for i = 1, q do result[ #result + 1 ] = "1" end
return string.reverse( table.concat( result, "" ) )
end
-- see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
local function extended_rice_encode( n, k )
k = k or 2
local n2 = 2 * n
return rice_encode( n < 0 and -n2 - 1 or n2, k )
end
-- Golomb-Rice decoding of a bit vector (string of 0s and 1s) with M of 2^k
local function rice_decode( a, k )
k = k or 2
local m = math.floor( 2^k )
local zpos, _ = a:find( "0" )
local r = 0
for z = zpos, #a do
r = r * 2
if a:sub( z, z ) == "1" then r = r + 1 end
end
local q = zpos - 1
return q * m + r
end
local function extended_rice_decode( a, k )
k = k or 2
local i = rice_decode( a, k )
return math.floor( i % 2 == 1 and - ( ( i + 1 ) / 2 ) or i / 2 )
end
print( "Base Rice Coding:" )
for n = 0, 10 do
local e = rice_encode( n )
print( n.." -> "..e.." -> "..rice_decode( e ) )
end
print( "Extended Rice Coding:" )
for n = -10, 10 do
local e = extended_rice_encode( n )
print( n.." -> "..e.." -> "..extended_rice_decode( e ) )
end
end
- Output:
Same as the Julia sample,
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Rice_coding
use warnings;
sub rice # args k arrayofnumbers
{
my $k = shift;
join '', map { 1 x ($_ >> $k) . 0 . sprintf "%0*b", $k, $_ % 2**$k } @_;
}
sub derice # args k stringof0and1representingbinarydata
{
(my $k, local $_) = @_;
my @answers;
push @answers, (length($1) << $k) + oct "0b$2" while /\G(1*)0(.{$k})/g;
return @answers;
}
for my $k ( 2 .. 6)
{
print "\nk = $k\n\n";
my $rice = rice( $k, my @input = 0 .. 17 );
my @decoded = derice $k, $rice;
print " input: @input\n rice: $rice\ndecoded: @decoded\n";
"@input" eq "@decoded" or die "MISMATCH";
}
- Output:
k = 2 input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 rice: 00000101001110001001101010111100011001110101101111100011100111101011101111110001111001 decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 k = 3 input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 rice: 000000010010001101000101011001111000010001100101001110100101011011010111110000110001 decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 k = 4 input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 rice: 00000000010001000011001000010100110001110100001001010100101101100011010111001111100000100001 decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 k = 5 input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 rice: 000000000001000010000011000100000101000110000111001000001001001010001011001100001101001110001111010000010001 decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 k = 6 input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 rice: 000000000000010000010000001100001000000101000011000001110001000000100100010100001011000110000011010001110000111100100000010001 decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Phix
with javascript_semantics
-- Golomb-Rice encoding of a positive number to bit vector using M of 2^k, with
-- optional -ve as per wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
function rice_encode(integer n, k=2, bool extended=false)
if extended then n = iff(n<0 ? -2*n-1 : 2*n) end if
assert(n>=0)
integer m = power(2,k), q = floor(n/m), r = rmdr(n,m)
return repeat('1',q)&sprintf(sprintf("%%0%db",k+1),r)
end function
-- Golomb-Rice decoding of a vector of bits with M of 2^k, with optional -ves
function rice_decode(string a, integer k=2, bool extended=false)
integer m = power(2,k),
q = find('0',a),
r = to_integer(a[q+1..$],0,2),
i = (q-1) * m + r
if extended then i := iff(odd(i) ? -(i+1)/2 : i/2) end if
return i
end function
printf(1,"Base Rice Coding:\n")
for n=0 to 10 do
string s = rice_encode(n)
printf(1,"%d -> %s -> %d\n",{n,s,rice_decode(s)})
end for
printf(1,"Extended Rice Coding:\n")
for n=-10 to 10 do
string s = rice_encode(n,2,true)
printf(1,"%d -> %s -> %d\n",{n,s,rice_decode(s,2,true)})
end for
- Output:
Same as Julia. Note that rice_decode on an input stream should probably get r from a[q+1..q+k] and strip q+k bits off the head of the stream.
Then again the above is using strings for demonstration purposes, so that code is hardly production-ready.
Python
#!/usr/bin/python
import math
def rice_encode(n, k = 2, extended = False):
if extended:
n = -2 * n -1 if n < 0 else 2*n
assert n >= 0
m = 2**k
q = n//m
r = n % m
return '1' * q + format(r, '0{}b'.format(k + 1))
def rice_decode(a, k = 2, extended = False):
m = 2**k
q = a.find('0')
r = int(a[q:], 2)
i = (q) * m + r
if extended:
i = -(i+1)//2 if i%2 else i//2
return i
print("Base Rice Coding:")
for n in range(11):
s = rice_encode(n)
print(f"{n} -> {s} -> {rice_decode(s)}")
print("Extended Rice Coding:")
for n in range(-10, 11):
s = rice_encode(n, 2, True)
print(f"{n} -> {s} -> {rice_decode(s, 2, True)}")
- Output:
Same as Phix entry.
Raku
package Rice {
our sub encode(Int $n, UInt :$k = 2) {
my $d = 2**$k;
my $q = $n div $d;
my $b = sign(1 + sign($q));
my $m = abs($q) + $b;
flat
$b xx $m, 1 - $b,
($n mod $d).polymod(2 xx $k - 1).reverse
}
our sub decode(@bits is copy, UInt :$k = 2) {
my $d = 2**$k;
my $b = @bits.shift;
my $m = 1;
$m++ while @bits and @bits.shift == $b;
my $q = $b ?? $m - 1 !! -$m;
$q*$d + @bits.reduce(2 * * + *);
}
}
CHECK {
use Test;
constant N = 100;
plan 2*N + 1;
is $_, Rice::decode Rice::encode $_ for -N..N;
}
Sidef
func rice(k, arr) {
var t = 2**k
arr.map {|v|
['1' * (v >> k), '0', '%0*s' % (k, as_bin(v % t))].join
}.join
}
func derice(k, str) {
gather {
var re = Regex('\G(1*)0(.{' + Str(k) + '})', 'g')
while (str =~ re) {|m|
take((m[0].len << k) + Num(m[1], 2))
}
}
}
for k in (2 .. 6) {
say "\nk = #{k}\n"
var input = @(0..17).shuffle
var enc = rice(k, input)
var dec = derice(k, enc)
say " input: #{input}"
say " rice: #{enc}"
say "decoded: #{dec}"
assert_eq(dec, input)
}
- Output:
k = 2 input: [5, 6, 15, 17, 3, 9, 4, 10, 12, 2, 11, 0, 1, 13, 7, 16, 8, 14] rice: 10011010111011111100101111001100011010111000010110110000011110011011111100011000111010 decoded: [5, 6, 15, 17, 3, 9, 4, 10, 12, 2, 11, 0, 1, 13, 7, 16, 8, 14] k = 3 input: [11, 14, 16, 4, 0, 5, 12, 13, 17, 3, 6, 10, 15, 2, 9, 7, 8, 1] rice: 100111011011000001000000010110100101011100010011011010010101110010100010111100000001 decoded: [11, 14, 16, 4, 0, 5, 12, 13, 17, 3, 6, 10, 15, 2, 9, 7, 8, 1] k = 4 input: [6, 4, 2, 9, 0, 5, 1, 3, 17, 15, 10, 11, 16, 13, 8, 14, 7, 12] rice: 00110001000001001001000000010100001000111000010111101010010111000000110101000011100011101100 decoded: [6, 4, 2, 9, 0, 5, 1, 3, 17, 15, 10, 11, 16, 13, 8, 14, 7, 12] k = 5 input: [17, 11, 14, 15, 4, 10, 12, 8, 16, 5, 6, 13, 3, 7, 1, 9, 2, 0] rice: 010001001011001110001111000100001010001100001000010000000101000110001101000011000111000001001001000010000000 decoded: [17, 11, 14, 15, 4, 10, 12, 8, 16, 5, 6, 13, 3, 7, 1, 9, 2, 0] k = 6 input: [2, 3, 14, 1, 7, 11, 17, 9, 16, 8, 13, 15, 6, 10, 12, 5, 4, 0] rice: 000001000000110001110000000100001110001011001000100010010010000000100000011010001111000011000010100001100000010100001000000000 decoded: [2, 3, 14, 1, 7, 11, 17, 9, 16, 8, 13, 15, 6, 10, 12, 5, 4, 0]
Wren
import "./math" for Int, Math
import "./check" for Check
import "./fmt" for Fmt
class Rice {
static encode(n, k) {
Check.nonNegInt("n", n)
var m = 1 << k
var q = Int.quo(n, m)
var r = n % m
var res = List.filled(q, 1)
res.add(0)
var digits = Int.digits(r, 2)
var dc = digits.count
if (dc < k) res.addAll([0] * (k - dc))
res.addAll(digits)
return res
}
static encodeEx(n, k) { encode(n < 0 ? -2 * n - 1 : 2 * n, k) }
static decode(a, k) {
var m = 1 << k
var q = a.indexOf(0)
if (q == -1) q = 0
var r = Math.evalPoly(a[q..-1], 2)
return q * m + r
}
static decodeEx(a, k) {
var i = decode(a, k)
return i % 2 == 1 ? -Int.quo(i+1, 2) : Int.quo(i, 2)
}
}
System.print("Basic Rice coding (k = 2):")
for (i in 0..10) {
var res = Rice.encode(i, 2)
Fmt.print("$2d -> $-6s -> $d", i, res.join(""), Rice.decode(res, 2))
}
System.print("\nExtended Rice coding (k == 2):")
for (i in -10..10) {
var res = Rice.encodeEx(i, 2)
Fmt.print("$3d -> $-9s -> $ d", i, res.join(""), Rice.decodeEx(res, 2))
}
System.print("\nBasic Rice coding (k == 4):")
for (i in 0..17) {
var res = Rice.encode(i, 4)
Fmt.print("$2d -> $-6s -> $d", i, res.join(""), Rice.decode(res, 4))
}
- Output:
Basic Rice coding (k = 2): 0 -> 000 -> 0 1 -> 001 -> 1 2 -> 010 -> 2 3 -> 011 -> 3 4 -> 1000 -> 4 5 -> 1001 -> 5 6 -> 1010 -> 6 7 -> 1011 -> 7 8 -> 11000 -> 8 9 -> 11001 -> 9 10 -> 11010 -> 10 Extended Rice coding (k == 2): -10 -> 1111011 -> -10 -9 -> 1111001 -> -9 -8 -> 111011 -> -8 -7 -> 111001 -> -7 -6 -> 11011 -> -6 -5 -> 11001 -> -5 -4 -> 1011 -> -4 -3 -> 1001 -> -3 -2 -> 011 -> -2 -1 -> 001 -> -1 0 -> 000 -> 0 1 -> 010 -> 1 2 -> 1000 -> 2 3 -> 1010 -> 3 4 -> 11000 -> 4 5 -> 11010 -> 5 6 -> 111000 -> 6 7 -> 111010 -> 7 8 -> 1111000 -> 8 9 -> 1111010 -> 9 10 -> 11111000 -> 10 Basic Rice coding (k == 4): 0 -> 00000 -> 0 1 -> 00001 -> 1 2 -> 00010 -> 2 3 -> 00011 -> 3 4 -> 00100 -> 4 5 -> 00101 -> 5 6 -> 00110 -> 6 7 -> 00111 -> 7 8 -> 01000 -> 8 9 -> 01001 -> 9 10 -> 01010 -> 10 11 -> 01011 -> 11 12 -> 01100 -> 12 13 -> 01101 -> 13 14 -> 01110 -> 14 15 -> 01111 -> 15 16 -> 100000 -> 16 17 -> 100001 -> 17