Rice coding: Difference between revisions
added RPL
(→{{header|Lua}}: Simplify) |
(added RPL) |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 7:
=={{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 #
Line 165:
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|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
The program presented here is written to advantage of of gojq's
support for unbounded-precision integer arithmetic. With small
modifications, it will also work with jaq, the Rust implementation of jq.
Note that in this entry, the polynomial SIGMA( c[$i] * x*$i ) is
represented by the JSON array [c0, c1, c2, ...].
<syntaxhighlight lang="jq">
# idivide/1 is written to take advantage of gojq's support for
# unbounded-precision integer arithmetic;
# the last last line (invoking `round`) is for the sake of jaq.
def idivide($j):
(. % $j) as $mod
| (. - $mod) / $j
| round # solely for jaq
;
def leftshift($n):
reduce range(0;$n) as $i (.; . * 2);
def divmod($j):
(. % $j) as $mod
| [((. - $mod) | idivide($j)), $mod] ;
# Emit a stream of the digits in the given non-negative integer
def digits: explode[] | . - 48;
# Bit arrays and polynomials
# Convert the input integer to a stream of 0s and 1s, least significant bit first
def bitwise:
recurse( if . >= 2 then idivide(2) else empty end) | . % 2;
# Evaluate the input polynomial at $x
def eval($x):
. as $p
| reduce range(0; length) as $i ({power: 1, ans: 0};
.ans += $p[$i] * .power
| .power *= $x )
| .ans;
### Rice Encoding
# Input should be a non-negative integer
def encode($k):
(1 | leftshift($k)) as $m
| divmod($m) as [$q, $r]
| ([range(0;$q) | 1] + [0])
| ([ $r | bitwise ] | reverse) as $digits
| ($digits|length) as $dc
| if $dc < $k then . + [range(0; $k - $dc) | 0] end
| . + $digits ;
def encodeEx($k):
if . < 0 then -2 * . - 1 else 2 * . end
| encode($k);
def decode($k):
(1 | leftshift($k)) as $m
| (index(0) | if . == -1 then 0 else . end) as $q
| ( .[$q:] | reverse| eval(2)) as $r
| $q * $m + $r;
def decodeEx($k):
decode($k) as $i
| if $i % 2 == 1 then - ($i+1 | idivide(2)) else ($i | idivide(2)) end;
"Basic Rice coding (k = 2):",
(range(0;11)
| encode(2) as $res
| "\(.) -> \($res|join("")) => \($res|decode(2))" ),
"\nExtended Rice coding (k == 2):",
(range (-10; 11)
| encodeEx(2) as $res
| "\(.) -> \($res|join("")) => \($res|decodeEx(2))" ),
"\nBasic Rice coding (k == 4):",
( range (0; 18)
| encode(4) as $res
| "\(.) -> \($res|join("")) => \($res|decode(4))" )
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
Line 363 ⟶ 547:
=={{header|Phix}}==
{{trans|Julia}}
<!--(phixonline)-->
<syntaxhighlight lang="phix">
with javascript_semantics
Line 399 ⟶ 584:
Then again the above is using strings for demonstration purposes, so that code is hardly production-ready.
=={{header|
{{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 430 ⟶ 651:
is $_, Rice::decode Rice::encode $_ for -N..N;
}</syntaxhighlight>
=={{header|RPL}}==
« BIN → k
« 2 k ^ MOD "0" LASTARG / IP
'''WHILE''' DUP '''REPEAT'''
1 -
"1" ROT + SWAP
'''END'''
DROP
R→B →STR 3 OVER SIZE 1 - SUB
'''WHILE''' DUP SIZE k < '''REPEAT''' "0" SWAP + '''END'''
+
» » '<span style="color:blue">→RICE</span>' STO
« BIN → n k
« "#" n DUP SIZE DUP k - 1 + SWAP SUB "b" + + STR→ B→R
0
1 k '''FOR''' j
n j DUP SUB "1" == +
'''NEXT'''
2 k ^ * +
» » '<span style="color:blue">RICE→</span>' STO
« { }
0 10 '''FOR''' j j 2 <span style="color:blue">→RICE</span> + '''NEXT'''
DUP { }
0 3 PICK SIZE '''FOR''' j OVER j GET 2 <span style="color:blue">RICE→</span> + '''NEXT'''
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
2: { "000" "001" "010" "011" "1000" "1001" "1010" "1011" "11000" "11001" "11010" }
1: { 0 1 2 3 4 5 6 7 8 9 10 }
</pre>
=={{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 436 ⟶ 751:
{{libheader|Wren-check}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./check" for Check
import "./fmt" for Fmt
| |||