Rosetta Code

Rice coding: Difference between revisions

Page Discussion

Rice coding (view source)

Revision as of 20:04, 12 March 2024

8,100 bytes added ,  2 months ago
Added Python
(→‎{{header|raku}}: raku -> Raku)
(Added Python)
(7 intermediate revisions by 4 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#}}==
Line 38 ⟶ 166:
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}}==
<syntaxhighlight lang="julia">""" Golomb-Rice encoding of a positive number to bit vector using M of 2^k"""
Line 110 ⟶ 275:
{{Trans|Julia|Using strings to represent the bit vector}}
<syntaxhighlight lang="lua">
do -- Rice encoding - translatedtranslation fromof the Julia sample
 
-- Golomb-Rice encoding helper function
local function do_rice_encode( q, r, k )
local result = {}
for i = 1, q do result[ #result + 1 ] = "1" end
result[ #result + 1 ] = "0"
local dPos = #result + 1
local digits = 0
if r > 0 then
local v = r
while v > 0 do
digits = digits + 1
local d = v % 2
v = math.floor( v / 2 )
table.insert( result, dPos, d ~= 0 and "1" or "0" )
end
end
for pad = digits + 1, k do table.insert( result, dPos, "0" ) end
return table.concat( result, "" )
end
-- 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 )
Line 136 ⟶ 282:
k = k or 2
local m = math.floor( 2^k )
local result, q, r = {}, math.floor( n / m ), n % m
returnwhile do_rice_encode(r q, r,> k0 )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
Line 161 ⟶ 314:
 
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 )
Line 177 ⟶ 330:
end
 
end
end</syntaxhighlight>
</syntaxhighlight>
{{out}}
Same as the Julia sample,
Line 245 ⟶ 399:
=={{header|Phix}}==
{{trans|Julia}}
<!--(phixonline)-->
<syntaxhighlight lang="phix">
with javascript_semantics
Line 281 ⟶ 436:
Then again the above is using strings for demonstration purposes, so that code is hardly production-ready.
 
=={{header|RakuPython}}==
{{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 {
 
Line 312 ⟶ 503:
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 318 ⟶ 570:
{{libheader|Wren-check}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int, Math
import "./check" for Check
import "./fmt" for Fmt
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/360144...361802"