Rice coding: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: extra 0) |
|||
Line 117:
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">m</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rmdr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
Revision as of 02:13, 22 September 2023
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.
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
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
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
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 * * + *);
}
}
use Test;
constant N = 100;
plan 2*N + 1;
is $_, Rice::decode Rice::encode $_ for -N..N;
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