Rosetta Code

Arithmetic coding/As a generalized change of radix: Difference between revisions

Page Discussion

Arithmetic coding/As a generalized change of radix (view source)

Revision as of 09:02, 7 April 2024

35,189 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
 
(10 intermediate revisions by 6 users not shown)
Line 14:
Verify the implementation by decoding the results back into strings and checking for equality with the given strings.
 
=={{header|C#|C sharp11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F cumulative_freq(freq)
[Int = Int] cf
V total = 0
L(b) 256
I b C freq
cf[b] = total
total += freq[b]
R cf
 
F arithmethic_coding(bytes, radix)
 
DefaultDict[Int, Int] freq
L(b) bytes
freq[b.code]++
 
V cf = cumulative_freq(freq)
 
BigInt base = bytes.len
 
BigInt lower = 0
 
BigInt pf = 1
 
L(b) bytes
lower = lower * base + cf[b.code] * pf
pf *= freq[b.code]
 
V upper = lower + pf
 
BigInt power = 0
L
pf I/= radix
I pf == 0
L.break
power++
 
V enc = (upper - 1) I/ BigInt(radix) ^ power
R (enc, power, freq)
 
F arithmethic_decoding(=enc, radix, =power, freq)
 
enc *= radix ^ power
 
V base = sum(freq.values())
 
V cf = cumulative_freq(freq)
 
[Int = Int] dict
L(k, v) cf
dict[v] = k
 
Int? lchar
L(i) 0 .< base
I i C dict
lchar = dict[i]
E I lchar != N
dict[i] = lchar
 
V decoded = ‘’
L(i) (base - 1 .< -1).step(-1)
power = BigInt(base) ^ i
V div = enc I/ power
 
V c = dict[Int(div)]
V fv = freq[c]
V cv = cf[c]
 
V rem = (enc - power * cv) I/ fv
 
enc = rem
decoded ‘’= Char(code' c)
 
R decoded
 
V radix = 10
 
L(str) ‘DABDDB DABDDBBDDBA ABRACADABRA TOBEORNOTTOBEORTOBEORNOT’.split(‘ ’)
V (enc, power, freq) = arithmethic_coding(str, radix)
V dec = arithmethic_decoding(enc, radix, power, freq)
 
print(‘#<25=> #19 * #.^#.’.format(str, enc, radix, power))
 
I str != dec
X.throw RuntimeError("\tHowever that is incorrect!")</syntaxhighlight>
 
{{out}}
<pre>
DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 144 ⟶ 240:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 153 ⟶ 249:
=={{header|D}}==
{{trans|Go}}
<langsyntaxhighlight Dlang="d">import std.array;
import std.bigint;
import std.stdio;
Line 304 ⟶ 400:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 312 ⟶ 408:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 474 ⟶ 570:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 485 ⟶ 581:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">class ArithmeticCoding {
private static class Triple<A, B, C> {
A a
Line 620 ⟶ 716:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 631 ⟶ 727:
Implementation:
 
<langsyntaxhighlight Jlang="j">NB. generate a frequency dictionary from a reference string
aekDict=:verb define
d=. ~.y NB. dictionary lists unique characters
Line 682 ⟶ 778:
echo 'Decoded:'
echo ' ',":dict (#y) aekDec aekEnc y
)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> aek 'DABDDB'
Dictionary:
A 1r6
Line 737 ⟶ 833:
1150764267498783364 15
Decoded:
TOBEORNOTTOBEORTOBEORNOT</langsyntaxhighlight>
 
Note that for this task we use our plaintext to generate our dictionary for decoding. Also note that we use rational numbers, rather than floating point, for our dictionary, because floating point tends to be inexact.
Line 743 ⟶ 839:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
Line 880 ⟶ 976:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 887 ⟶ 983:
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15</pre>
 
=={{header|JavaScript}}==
{{trans|C#}}
<syntaxhighlight lang="javascript">
function CumulativeFreq(freq) {
let total = 0;
const cf = new Map();
for (let i = 0; i < 256; i++) {
const c = String.fromCharCode(i);
if (freq.has(c)) {
const v = freq.get(c);
cf.set(c, total);
total += v;
}
}
return cf;
}
 
function ArithmeticCoding(str, radix) {
const freq = new Map();
for (let i = 0; i < str.length; i++) {
const c = str[i].toString();
if (freq.has(c)) freq.set(c, freq.get(c) + 1);
else freq.set(c, 1);
}
const cf = CumulativeFreq(freq);
const base = BigInt(str.length);
let lower = BigInt(0);
let pf = BigInt(1);
for (let i = 0; i < str.length; i++) {
const c = str[i].toString();
const x = BigInt(cf.get(c));
lower = lower * base + x * pf;
pf = pf * BigInt(freq.get(c));
}
let upper = lower + pf;
let powr = 0n;
const bigRadix = BigInt(radix);
while (true) {
pf = pf / bigRadix;
if (pf === 0n) break;
powr++;
}
const diff = (upper - 1n) / (bigRadix ** powr)
return { Item1: diff, Item2: powr, Item3: freq };
}
 
function ArithmeticDecoding(num, radix, pwr, freq) {
const powr = BigInt(radix);
let enc = BigInt(num) * powr ** BigInt(pwr);
let sum = 0;
freq.forEach(value => sum += value);
const base = sum;
 
const cf = CumulativeFreq(freq);
const dict = new Map();
cf.forEach((value, key) => dict.set(value, key));
 
let lchar = -1;
for (let i = 0; i < base; i++) {
if (dict.has(i)) lchar = dict.get(i).charCodeAt(0);
else if (lchar !== -1) dict.set(i, String.fromCharCode(lchar));
}
const decoded = new Array(base);
const bigBase = BigInt(base);
for (let i = base - 1; i >= 0; --i) {
const pow = bigBase ** BigInt(i);
const div = enc / pow;
const c = dict.get(Number(div));
const fv = BigInt(freq.get(c));
const cv = BigInt(cf.get(c));
const diff = BigInt(enc - pow * cv);
enc = diff / fv;
decoded[base - 1 - i] = c;
}
return decoded.join("");
}
 
function Main() {
const radix = 10;
const strings = ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"];
for (const str of strings) {
const encoded = ArithmeticCoding(str, radix);
const dec = ArithmeticDecoding(encoded.Item1, radix, encoded.Item2, encoded.Item3);
console.log(`${str.padEnd(25, " ")}=> ${encoded.Item1.toString(10).padStart(19, " ")} * ${radix}^${encoded.Item2}`);
if (str !== dec) {
throw new Error("\tHowever that is incorrect!");
}
}
}
</syntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15</pre>
 
=={{header|Julia}}==
Taken from the wikipedia example.
<langsyntaxhighlight lang="julia">function charfreq(s)
d = Dict()
for c in s
Line 971 ⟶ 1,162:
decode(encoded * "0"^z, dfreq))
end
</langsyntaxhighlight>{{out}}
<pre>
DABDDB 251 * 10^2 DABDDB
Line 981 ⟶ 1,172:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.2.10
 
import java.math.BigInteger
Line 1,107 ⟶ 1,298:
if (str != dec) throw Exception("\tHowever that is incorrect!")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,116 ⟶ 1,307:
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<syntaxhighlight lang="nim">import strformat, sugar, tables
import bignum
 
type Freq = CountTable[char]
 
 
proc cumulativeFreq(freq: Freq): Freq =
var total = 0
for c in '\0'..'\255':
result.inc c, total
inc total, freq[c]
 
 
func arithmeticCoding(str: string; radix: int): (Int, int, Freq) =
 
let freq = str.toCountTable() # The frequency characters.
let cf = cumulativeFreq(freq) # The cumulative frequency.
let base = newInt(str.len) # Base.
var lower = newInt(0) # Lower bound.
var pf = newInt(1) # Product of all frequencies.
 
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols.
for c in str:
lower = lower * base + cf[c] * pf
pf *= freq[c]
 
let upper = lower + pf # Upper bound.
var powr = 0
 
while true:
pf = pf div radix
if pf.isZero: break
inc powr
 
let diff = (upper - 1) div radix.pow(powr.culong)
result = (diff, powr, freq)
 
 
func arithmeticDecoding(num: Int; radix, pwr: int; freq: Freq): string =
var enc = num * radix.pow(pwr.culong)
var base = 0
for v in freq.values: base += v
 
# Create the cumulative frequency table.
let cf = cumulativeFreq(freq)
 
# Create the dictionary.
let dict = collect(newTable, for k in '\0'..'\255': {cf[k]: k})
 
# Fill the gaps in the dictionary.
var lchar = -1
for i in 0..<base:
if i in dict:
lchar = ord(dict[i])
elif lchar >= 0:
dict[i] = chr(lchar)
 
# Decode the input number.
for i in countdown(base - 1, 0):
let p = base.pow(i.culong)
let d = enc div p
let c = dict[d.toInt]
let diff = enc - p * cf[c]
enc = diff div freq[c]
result.add c
 
 
const Radix = 10
const Strings = ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"]
for str in Strings:
let (enc, pow, freq) = arithmeticCoding(str, Radix)
let dec = arithmeticDecoding(enc, Radix, pow, freq)
echo &"{str:<25}→ {enc:>19} * {Radix}^{pow}"
doAssert str == dec, "\tHowever that is incorrect!"</syntaxhighlight>
 
{{out}}
<pre>DABDDB → 251 * 10^2
DABDDBBDDBA → 167351 * 10^6
ABRACADABRA → 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT → 1150764267498783364 * 10^15</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use Math::BigInt (try => 'GMP');
 
sub cumulative_freq {
Line 1,227 ⟶ 1,503:
die "\tHowever that is incorrect!";
}
}</langsyntaxhighlight>
{{out}}
<pre>
DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{header|Perl 6}}==
<lang perl6>sub cumulative_freq(%freq) {
my %cf;
my $total = 0;
for %freq.keys.sort -> $c {
%cf{$c} = $total;
$total += %freq{$c};
}
return %cf;
}
 
sub arithmethic_coding($str, $radix) {
my @chars = $str.comb;
 
# The frequency characters
my %freq;
%freq{$_}++ for @chars;
 
# The cumulative frequency table
my %cf = cumulative_freq(%freq);
 
# Base
my $base = @chars.elems;
 
# Lower bound
my $L = 0;
 
# Product of all frequencies
my $pf = 1;
 
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
for @chars -> $c {
$L = $L*$base + %cf{$c}*$pf;
$pf *= %freq{$c};
}
 
# Upper bound
my $U = $L + $pf;
 
my $pow = 0;
loop {
$pf div= $radix;
last if $pf == 0;
++$pow;
}
 
my $enc = ($U - 1) div ($radix ** $pow);
($enc, $pow, %freq);
}
 
sub arithmethic_decoding($encoding, $radix, $pow, %freq) {
 
# Multiply encoding by radix^pow
my $enc = $encoding * $radix**$pow;
 
# Base
my $base = [+] %freq.values;
 
# Create the cumulative frequency table
my %cf = cumulative_freq(%freq);
 
# Create the dictionary
my %dict;
for %cf.kv -> $k,$v {
%dict{$v} = $k;
}
 
# Fill the gaps in the dictionary
my $lchar;
for ^$base -> $i {
if (%dict{$i}:exists) {
$lchar = %dict{$i};
}
elsif (defined $lchar) {
%dict{$i} = $lchar;
}
}
 
# Decode the input number
my $decoded = '';
for reverse(^$base) -> $i {
 
my $pow = $base**$i;
my $div = $enc div $pow;
 
my $c = %dict{$div};
my $fv = %freq{$c};
my $cv = %cf{$c};
 
my $rem = ($enc - $pow*$cv) div $fv;
 
$enc = $rem;
$decoded ~= $c;
}
 
# Return the decoded output
return $decoded;
}
 
my $radix = 10; # can be any integer greater or equal with 2
 
for <DABDDB DABDDBBDDBA ABRACADABRA TOBEORNOTTOBEORTOBEORNOT> -> $str {
my ($enc, $pow, %freq) = arithmethic_coding($str, $radix);
my $dec = arithmethic_decoding($enc, $radix, $pow, %freq);
 
printf("%-25s=> %19s * %d^%s\n", $str, $enc, $radix, $pow);
 
if ($str ne $dec) {
die "\tHowever that is incorrect!";
}
}</lang>
{{out}}
<pre>
Line 1,359 ⟶ 1,515:
{{trans|Go}}
{{trans|Kotlin}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>include mpfr.e
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
function cumulative_freq(sequence freq)
integer total = 0,
<span style="color: #008080;">function</span> <span style="color: #000000;">cumulative_freq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
l = length(freq)
<span style="color: #004080;">integer</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
sequence cf = repeat(-1,l)
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
for c=1 to l do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cf</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
integer v = freq[c]
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
if v!=0 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
cf[c] = total
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
total += v
<span style="color: #000000;">cf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">total</span>
end if
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">v</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return cf
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">cf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function arithmethic_coding(string str, integer radix)
sequence freq = repeat(0,256)
<span style="color: #008080;">function</span> <span style="color: #000000;">arithmethic_coding</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">str</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">radix</span><span style="color: #0000FF;">)</span>
for i=1 to length(str) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">freq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">)</span>
freq[str[i]+1] += 1
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">freq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">str</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
sequence cf = cumulative_freq(freq)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer base = length(str)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cumulative_freq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
mpz lo = mpz_init(0), -- lower bound
<span style="color: #004080;">integer</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str</span><span style="color: #0000FF;">)</span>
pf = mpz_init(1), -- product of all frequencies
<span style="color: #004080;">mpz</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- lower bound</span>
t1 = mpz_init(), -- temp
<span style="color: #000000;">pf</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- product of all frequencies</span>
t2 = mpz_init(), -- temp
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> <span style="color: #000080;font-style:italic;">-- temp</span>
hi = mpz_init(), -- upper bound
<span style="color: #000000;">t2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> <span style="color: #000080;font-style:italic;">-- temp</span>
diff = mpz_init()
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> <span style="color: #000080;font-style:italic;">-- upper bound</span>
-- Each term is multiplied by the product of the
<span style="color: #000000;">diff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
-- frequencies of all previously occurring symbols
<span style="color: #000080;font-style:italic;">-- Each term is multiplied by the product of the
for i=1 to length(str) do
-- frequencies of all previously occurring symbols</span>
integer c = str[i]+1
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer x = cf[c]
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">str</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
mpz_mul_si(t1,lo,base)
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
mpz_mul_si(t2,pf,x)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
mpz_add(lo,t1,t2)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
mpz_mul_si(pf,pf,freq[c])
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])</span>
mpz_add(hi,lo,pf)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer powr = 0
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">)</span>
while true do
<span style="color: #004080;">integer</span> <span style="color: #000000;">powr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
{} = mpz_fdiv_q_ui(pf,pf,radix)
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if mpz_cmp_si(pf,0)=0 then exit end if
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">radix</span><span style="color: #0000FF;">)</span>
powr += 1
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #000000;">powr</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
mpz_sub_ui(hi,hi,1)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_ui_pow_ui(t1,radix,powr)
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpz_fdiv_q(diff,hi,t1)
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">radix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">powr</span><span style="color: #0000FF;">)</span>
return {diff, powr, freq}
<span style="color: #7060A8;">mpz_fdiv_q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">powr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function arithmethic_decoding(mpz num, integer radix, pwr, sequence freq)
mpz enc = mpz_init(),
<span style="color: #008080;">function</span> <span style="color: #000000;">arithmethic_decoding</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">radix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pwr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
pow = mpz_init(),
<span style="color: #004080;">mpz</span> <span style="color: #000000;">enc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
tmp = mpz_init()
<span style="color: #000000;">pow</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
mpz_ui_pow_ui(enc,radix,pwr)
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
mpz_mul(enc,num,enc)
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">radix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pwr</span><span style="color: #0000FF;">)</span>
integer base = sum(freq)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">)</span>
sequence cf = cumulative_freq(freq)
<span style="color: #004080;">integer</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
sequence dict = repeat(0,base+1)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cumulative_freq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
for i=1 to length(cf) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dict</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
integer v = cf[i]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cf</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if v!=-1 then dict[v+1] = i-1 end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">dict</span><span style="color: #0000FF;">[</span><span style="color: #000000;">v</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- Fill the gaps in the dictionary
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer lchar = -1
<span style="color: #000080;font-style:italic;">-- Fill the gaps in the dictionary</span>
for i=0 to base do
<span style="color: #004080;">integer</span> <span style="color: #000000;">lchar</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
integer v = dict[i+1]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">base</span> <span style="color: #008080;">do</span>
if v!=0 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dict</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
lchar = v
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
elsif lchar!=-1 then
<span style="color: #000000;">lchar</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
dict[i+1] = lchar
<span style="color: #008080;">elsif</span> <span style="color: #000000;">lchar</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">dict</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lchar</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- Decode the input number
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
string decoded = ""
<span style="color: #000080;font-style:italic;">-- Decode the input number</span>
for i=base-1 to 0 by -1 do
<span style="color: #004080;">string</span> <span style="color: #000000;">decoded</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
mpz_ui_pow_ui(pow,base,i)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">base</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">0</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
mpz_fdiv_q(tmp,enc,pow)
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
integer div = mpz_get_si(tmp),
<span style="color: #7060A8;">mpz_fdiv_q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">)</span>
c = dict[div+1],
<span style="color: #004080;">integer</span> <span style="color: #000000;">div</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">),</span>
fv = freq[c+1],
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dict</span><span style="color: #0000FF;">[</span><span style="color: #000000;">div</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
cv = cf[c+1]
<span style="color: #000000;">fv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
mpz_mul_si(tmp,pow,cv)
<span style="color: #000000;">cv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
mpz_sub(tmp,enc,tmp)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cv</span><span style="color: #0000FF;">)</span>
{} = mpz_fdiv_q_ui(enc,tmp,fv)
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
decoded &= c
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fv</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #000000;">decoded</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">c</span>
return decoded
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">decoded</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
constant tests = {"DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"},
radix = 10
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"DABDDB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DABDDBBDDBA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ABRACADABRA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TOBEORNOTTOBEORTOBEORNOT"</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">radix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
for i=1 to length(tests) do
string str = tests[i]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
{mpz enc, integer pow, sequence freq} = arithmethic_coding(str, radix)
<span style="color: #004080;">string</span> <span style="color: #000000;">str</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
string dec = arithmethic_decoding(enc, radix, pow, freq),
<span style="color: #0000FF;">{</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arithmethic_coding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">radix</span><span style="color: #0000FF;">)</span>
ok = iff(str=dec?"(ok)":"***ERROR***"),
<span style="color: #004080;">string</span> <span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arithmethic_decoding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">radix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">),</span>
encs = mpz_get_str(enc)
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str</span><span style="color: #0000FF;">=</span><span style="color: #000000;">dec</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"(ok)"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"***ERROR***"</span><span style="color: #0000FF;">),</span>
printf(1,"%-25s=> %19s * %d^%d %s\n",{str, encs, radix, pow, ok})
<span style="color: #000000;">encs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">)</span>
end for</lang>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%-25s=&gt; %19s * %d^%d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">str</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">encs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">radix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ok</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,473 ⟶ 1,632:
=={{header|Python}}==
{{works with|Python|3.1+}}
<langsyntaxhighlight lang="python">from collections import Counter
 
def cumulative_freq(freq):
Line 1,570 ⟶ 1,729:
 
if str != dec:
raise Exception("\tHowever that is incorrect!")</langsyntaxhighlight>
{{out}}
<pre>
DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub cumulative_freq(%freq) {
my %cf;
my $total = 0;
for %freq.keys.sort -> $c {
%cf{$c} = $total;
$total += %freq{$c};
}
return %cf;
}
 
sub arithmethic_coding($str, $radix) {
my @chars = $str.comb;
 
# The frequency characters
my %freq;
%freq{$_}++ for @chars;
 
# The cumulative frequency table
my %cf = cumulative_freq(%freq);
 
# Base
my $base = @chars.elems;
 
# Lower bound
my $L = 0;
 
# Product of all frequencies
my $pf = 1;
 
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
for @chars -> $c {
$L = $L*$base + %cf{$c}*$pf;
$pf *= %freq{$c};
}
 
# Upper bound
my $U = $L + $pf;
 
my $pow = 0;
loop {
$pf div= $radix;
last if $pf == 0;
++$pow;
}
 
my $enc = ($U - 1) div ($radix ** $pow);
($enc, $pow, %freq);
}
 
sub arithmethic_decoding($encoding, $radix, $pow, %freq) {
 
# Multiply encoding by radix^pow
my $enc = $encoding * $radix**$pow;
 
# Base
my $base = [+] %freq.values;
 
# Create the cumulative frequency table
my %cf = cumulative_freq(%freq);
 
# Create the dictionary
my %dict;
for %cf.kv -> $k,$v {
%dict{$v} = $k;
}
 
# Fill the gaps in the dictionary
my $lchar;
for ^$base -> $i {
if (%dict{$i}:exists) {
$lchar = %dict{$i};
}
elsif (defined $lchar) {
%dict{$i} = $lchar;
}
}
 
# Decode the input number
my $decoded = '';
for reverse(^$base) -> $i {
 
my $pow = $base**$i;
my $div = $enc div $pow;
 
my $c = %dict{$div};
my $fv = %freq{$c};
my $cv = %cf{$c};
 
my $rem = ($enc - $pow*$cv) div $fv;
 
$enc = $rem;
$decoded ~= $c;
}
 
# Return the decoded output
return $decoded;
}
 
my $radix = 10; # can be any integer greater or equal with 2
 
for <DABDDB DABDDBBDDBA ABRACADABRA TOBEORNOTTOBEORTOBEORNOT> -> $str {
my ($enc, $pow, %freq) = arithmethic_coding($str, $radix);
my $dec = arithmethic_decoding($enc, $radix, $pow, %freq);
 
printf("%-25s=> %19s * %d^%s\n", $str, $enc, $radix, $pow);
 
if ($str ne $dec) {
die "\tHowever that is incorrect!";
}
}</syntaxhighlight>
{{out}}
<pre>
Line 1,580 ⟶ 1,860:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">def cumulative_freq(freq)
cf = {}
total = 0
Line 1,688 ⟶ 1,968:
raise "\tHowever that is incorrect!"
end
end</langsyntaxhighlight>
{{out}}
<pre>
Line 1,699 ⟶ 1,979:
=={{header|Scala}}==
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/EUNJ0zp/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/DVl840oDS2mFvFQ560fxJAScastie (remote JVM)].
<langsyntaxhighlight Scalalang="scala">object ArithmeticCoding extends App {
val (radix, strings) = (10, Seq("DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"))
val fmt = "%-25s=> %19s * %d^%s"
Line 1,774 ⟶ 2,054:
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!")
}
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func cumulative_freq(freq) {
var cf = Hash()
var total = 0
Line 1,883 ⟶ 2,164:
die "\tHowever that is incorrect!"
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 1,892 ⟶ 2,173:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Text
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long)
Line 2,018 ⟶ 2,299:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 2,024 ⟶ 2,305:
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./big" for BigInt
import "./fmt" for Fmt
 
var cumulativeFreq = Fn.new { |freq|
var total = 0
var cf = {}
for (i in 0..255) {
var c = i
var v = freq[c]
if (v) {
cf[c] = total
total = total + v
}
}
return cf
}
 
var arithmeticCoding = Fn.new { |str, radix|
// Convert the string into a character list
var chars = str.bytes.toList
 
// The frequency characters
var freq = {}
for (c in chars) {
if (!freq[c]) {
freq[c] = 1
} else {
freq[c] = freq[c] + 1
}
}
 
// The cumulative frequency
var cf = cumulativeFreq.call(freq)
 
// Base
var base = BigInt.new(chars.count)
 
// LowerBound
var lower = BigInt.zero
 
// Product of all frequencies
var pf = BigInt.one
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
for (c in chars) {
var x = BigInt.new(cf[c])
lower = lower * base + x * pf
pf = pf * BigInt.new(freq[c])
}
 
// Upper bound
var upper = lower + pf
 
var powr = 0
var bigRadix = BigInt.new(radix)
 
while (true) {
pf = pf / bigRadix
if (pf == BigInt.zero) break
powr = powr + 1
}
 
var diff = (upper - BigInt.one) / bigRadix.pow(powr)
return [diff, powr, freq]
}
 
var arithmeticDecoding = Fn.new { |num, radix, pwr, freq|
var powr = BigInt.new(radix)
var enc = num * powr.pow(pwr)
var base = 0
for (v in freq.values) base = base + v
 
// Create the cumulative frequency table
var cf = cumulativeFreq.call(freq)
 
// Create the dictionary
var dict = {}
for (me in cf) dict[me.value] = me.key
 
// Fill the gaps in the dictionary
var lchar = -1
for (i in 0...base) {
var v = dict[i]
if (v) {
lchar = v
} else if (lchar != -1) {
dict[i] = lchar
}
}
 
// Decode the input number
var decoded = ""
var bigBase = BigInt.new(base)
for (i in base-1..0) {
var pow = bigBase.pow(i)
var div = enc / pow
var c = dict[div.toSmall]
var fv = BigInt.new(freq[c])
var cv = BigInt.new(cf[c])
var diff = enc - pow * cv
enc = diff / fv
decoded = decoded + String.fromByte(c)
}
// Return the decoded output
return decoded
}
 
var radix = 10
var strings = ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"]
var fmt = "$-25s=> $19s * $d^$s"
for (str in strings) {
var res = arithmeticCoding.call(str, radix)
var enc = res[0]
var pow = res[1]
var freq = res[2]
var dec = arithmeticDecoding.call(enc, radix, pow, freq)
Fmt.print(fmt, str, enc, radix, pow)
if (str != dec) Fiber.abort("\tHowever that is incorrect!")
}</syntaxhighlight>
 
{{out}}
<pre>
DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{header|zkl}}==
Uses libGMP (GNU MP Bignum Library)
<langsyntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); // libGMP
 
fcn cumulativeFreq(freqHash){
Line 2,059 ⟶ 2,473:
 
return(enc,powr,freqHash);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn arithmethicDecoding(enc, radix, powr, freqHash){
enc*=radix.pow(powr);
base:=freqHash.values.sum(0);
Line 2,083 ⟶ 2,497:
}
decoded.text // Return the decoded output
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">radix:=10;
testStrings:=T(
"DABDDB",
Line 2,097 ⟶ 2,511:
if(str!=dec) println("\tHowever that is incorrect!");
}</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/263404...363361"