Rice coding: Difference between revisions
Added Python
(Made this into a draft task and added a Wren example.) |
(Added Python) |
||
| (22 intermediate revisions by 9 users not shown) | |||
Line 5:
Rice coding is initially meant to encode [[w:natural numbers|natural numbers]], but since [[w:relative numbers|relative numbers]] are [[w:countable|countable]], it is fairly easy to modify Rice coding to encode them too. You can do that for extra credit.
=={{header|ALGOL 68}}==
{{Trans|Julia|with output formatting similar to the Wren sample and using STRINGs to represent the bit vector}}
<syntaxhighlight lang="algol68">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// 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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|FreeBASIC}}==
{{trans|Phix}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>Same as Phix entry.</pre>
=={{header|Julia}}==
Line 12 ⟶ 209:
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 """
Line 40 ⟶ 237:
<pre>
Base Rice Coding:
0 ->
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 ->
10 ->
Extended Rice Coding:
-10 ->
-9 ->
-8 ->
-7 ->
-6 ->
-5 ->
-4 ->
-3 ->
-2 ->
-1 ->
0 ->
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 ->
10 ->
</pre>
=={{header|Lua}}==
{{Trans|Julia|Using strings to represent the bit vector}}
<syntaxhighlight lang="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 )
local i = rice_decode( a, k )
return math.floor( i % 2 == 1 and - ( ( i + 1 ) / 2 ) or i / 2 )
end
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
</syntaxhighlight>
{{out}}
Same as the Julia sample,
=={{header|Perl}}==
<syntaxhighlight lang="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";
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Phix}}==
{{trans|Julia}}
<!--(phixonline)-->
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
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.<br>
Then again the above is using strings for demonstration purposes, so that code is hardly production-ready.
=={{header|Python}}==
{{works with|Python|3.x}}
{{trans|Phix}}
<syntaxhighlight lang="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)}")</syntaxhighlight>
{{out}}
<pre>Same as Phix entry.</pre>
=={{header|Raku}}==
<syntaxhighlight lang="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 * * + *);
}
}
Line 103 ⟶ 501:
constant N = 100;
plan 2*N + 1;
is $_, Rice::decode Rice::encode $_ for -N..N;
}</syntaxhighlight>
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">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)
}</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
=={{header|Wren}}==
Line 111 ⟶ 570:
{{libheader|Wren-check}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./check" for Check
import "./fmt" for Fmt
Line 125 ⟶ 584:
var digits = Int.digits(r, 2)
var dc = digits.count
if (dc < k
res.addAll(digits)
return res
Line 146 ⟶ 605:
}
System.print("Basic Rice coding (k = 2):")
for (i in 0..10) {
var res = Rice.encode(i, 2)
Line 152 ⟶ 611:
}
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))
}</syntaxhighlight>
{{out}}
<pre>
Basic Rice coding (k = 2):
0 ->
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 ->
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
</pre>
| |||