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

72,283 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
(simplified the encoding loop a little bit)
 
(46 intermediate revisions by 13 users not shown)
Line 13:
 
Verify the implementation by decoding the results back into strings and checking for equality with the given strings.
 
=={{header|11l}}==
{{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}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
 
namespace AruthmeticCoding {
using Freq = Dictionary<char, long>;
using Triple = Tuple<BigInteger, int, Dictionary<char, long>>;
 
class Program {
static Freq CumulativeFreq(Freq freq) {
long total = 0;
Freq cf = new Freq();
for (int i = 0; i < 256; i++) {
char c = (char)i;
if (freq.ContainsKey(c)) {
long v = freq[c];
cf[c] = total;
total += v;
}
}
return cf;
}
 
static Triple ArithmeticCoding(string str, long radix) {
// The frequency of characters
Freq freq = new Freq();
foreach (char c in str) {
if (freq.ContainsKey(c)) {
freq[c] += 1;
} else {
freq[c] = 1;
}
}
 
// The cumulative frequency
Freq cf = CumulativeFreq(freq);
 
// Base
BigInteger @base = str.Length;
 
// Lower bound
BigInteger lower = 0;
 
// Product of all frequencies
BigInteger pf = 1;
 
// Each term is multiplied by the product of the
// frequencies of all previously occuring symbols
foreach (char c in str) {
BigInteger x = cf[c];
lower = lower * @base + x * pf;
pf = pf * freq[c];
}
 
// Upper bound
BigInteger upper = lower + pf;
 
int powr = 0;
BigInteger bigRadix = radix;
 
while (true) {
pf = pf / bigRadix;
if (pf == 0) break;
powr++;
}
 
BigInteger diff = (upper - 1) / (BigInteger.Pow(bigRadix, powr));
return new Triple(diff, powr, freq);
}
 
static string ArithmeticDecoding(BigInteger num, long radix, int pwr, Freq freq) {
BigInteger powr = radix;
BigInteger enc = num * BigInteger.Pow(powr, pwr);
long @base = freq.Values.Sum();
 
// Create the cumulative frequency table
Freq cf = CumulativeFreq(freq);
 
// Create the dictionary
Dictionary<long, char> dict = new Dictionary<long, char>();
foreach (char key in cf.Keys) {
long value = cf[key];
dict[value] = key;
}
 
// Fill the gaps in the dictionary
long lchar = -1;
for (long i = 0; i < @base; i++) {
if (dict.ContainsKey(i)) {
lchar = dict[i];
} else if (lchar != -1) {
dict[i] = (char)lchar;
}
}
 
// Decode the input number
StringBuilder decoded = new StringBuilder((int)@base);
BigInteger bigBase = @base;
for (long i = @base - 1; i >= 0; --i) {
BigInteger pow = BigInteger.Pow(bigBase, (int)i);
BigInteger div = enc / pow;
char c = dict[(long)div];
BigInteger fv = freq[c];
BigInteger cv = cf[c];
BigInteger diff = enc - pow * cv;
enc = diff / fv;
decoded.Append(c);
}
 
// Return the decoded output
return decoded.ToString();
}
 
static void Main(string[] args) {
long radix = 10;
string[] strings = { "DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT" };
foreach (string str in strings) {
Triple encoded = ArithmeticCoding(str, radix);
string dec = ArithmeticDecoding(encoded.Item1, radix, encoded.Item2, encoded.Item3);
Console.WriteLine("{0,-25}=> {1,19} * {2}^{3}", str, encoded.Item1, radix, encoded.Item2);
if (str != dec) {
throw new Exception("\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|D}}==
{{trans|Go}}
<syntaxhighlight lang="d">import std.array;
import std.bigint;
import std.stdio;
import std.typecons;
 
BigInt bigPow(BigInt b, BigInt e) {
if (e == 0) {
return BigInt(1);
}
 
BigInt result = 1;
while (e > 1) {
if (e % 2 == 0) {
b *= b;
e /= 2;
} else {
result *= b;
b *= b;
e = (e - 1) / 2;
}
}
 
return b * result;
}
 
long[byte] cumulative_freq(long[byte] freq) {
long[byte] cf;
long total;
foreach (i; 0..256) {
byte b = cast(byte) i;
if (b in freq) {
cf[b] = total;
total += freq[b];
}
}
return cf;
}
 
Tuple!(BigInt, BigInt, long[byte]) arithmethic_coding(string str, long radix) {
// Convert the string into a slice of bytes
auto chars = cast(byte[]) str;
 
// The frequency characters
long[byte] freq;
foreach (c; chars) {
freq[c]++;
}
 
// The cumulative frequency
auto cf = cumulative_freq(freq);
 
// Base
BigInt base = chars.length;
 
// Lower bound
BigInt lower = 0;
 
// Product of all frequencies
BigInt pf = 1;
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
foreach (c; chars) {
BigInt x = cf[c];
 
lower = lower*base + x*pf;
pf = pf*freq[c];
}
 
// Upper bound
auto upper = lower + pf;
 
BigInt tmp = pf;
auto powr = BigInt("0");
 
while (true) {
tmp = tmp / radix;
if (tmp == 0) {
break;
}
powr++;
}
 
auto diff = (upper-1) / bigPow(BigInt(radix), powr);
 
return tuple(diff, powr, freq);
}
 
string arithmethic_decoding(BigInt num, long radix, BigInt pow, long[byte] freq) {
BigInt powr = radix;
 
BigInt enc = num * bigPow(powr, pow);
 
BigInt base = 0;
foreach (v; freq) {
base += v;
}
 
// Create the cumulative frequency table
auto cf = cumulative_freq(freq);
 
// Create the dictionary
byte[long] dict;
foreach (k,v; cf) {
dict[v] = k;
}
 
// Fill the gaps in the dictionary
long lchar = -1;
for (long i=0; i<base; i++) {
if (i in dict) {
lchar = dict[i];
} else if (lchar != -1) {
dict[i] = cast(byte) lchar;
}
}
 
// Decode the input number
auto decoded = appender!string;
for (BigInt i=base-1; i>=0; i--) {
pow = bigPow(base, i);
 
auto div = enc / pow;
 
auto c = dict[div.toLong];
auto fv = freq[c];
auto cv = cf[c];
 
auto prod = pow * cv;
auto diff = enc - prod;
enc = diff / fv;
 
decoded.put(c);
}
 
// Return the decoded output
return decoded.data;
}
 
void main() {
long radix = 10;
 
foreach (str; ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"]) {
auto output = arithmethic_coding(str, radix);
auto dec = arithmethic_decoding(output[0], radix, output[1], output[2]);
writefln("%-25s=> %19s * %s^%s", str, output[0], radix, output[1]);
 
if (str != dec) {
throw new Exception("\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|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 177 ⟶ 570:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 186 ⟶ 579:
</pre>
 
=={{header|JGroovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class ArithmeticCoding {
private static class Triple<A, B, C> {
A a
B b
C c
 
Triple(A a, B b, C c) {
Note that decoding assumes we know the length of the string (and also that strings are assumed to contain only upper case alphanumeric letters) - but that's not a part of this task.
this.a = a
this.b = b
this.c = c
}
}
 
private static class Freq extends HashMap<Character, Long> {
// type alias
}
 
private static Freq cumulativeFreq(Freq freq) {
long total = 0
Freq cf = new Freq()
for (int i = 0; i < 256; ++i) {
char c = i
Long v = freq.get(c)
if (null != v) {
cf.put(c, total)
total += v
}
}
return cf
}
 
private static Triple<BigInteger, Integer, Freq> arithmeticCoding(String str, Long radix) {
// Convert the string into a char array
char[] chars = str.toCharArray()
 
// The frequency characters
Freq freq = new Freq()
for (char c : chars) {
if (freq.containsKey(c)) {
freq.put(c, freq[c] + 1)
} else {
freq.put(c, 1)
}
}
 
// The cumulative frequency
Freq cf = cumulativeFreq(freq)
 
// Base
BigInteger base = chars.length
 
// LowerBound
BigInteger lower = BigInteger.ZERO
 
// Product of all frequencies
BigInteger pf = BigInteger.ONE
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
for (char c : chars) {
BigInteger x = cf[c]
lower = lower * base + x * pf
pf = pf * freq[c]
}
 
// Upper bound
BigInteger upper = lower + pf
 
int powr = 0
BigInteger bigRadix = radix
 
while (true) {
pf = pf.divide(bigRadix)
if (BigInteger.ZERO == pf) {
break
}
powr++
}
 
BigInteger diff = (upper - BigInteger.ONE).divide(bigRadix.pow(powr))
return new Triple<BigInteger, Integer, Freq>(diff, powr, freq)
}
 
private static String arithmeticDecoding(BigInteger num, long radix, int pwr, Freq freq) {
BigInteger powr = radix
BigInteger enc = num * powr.pow(pwr)
long base = 0
for (Long v : freq.values()) base += v
 
// Create the cumulative frequency table
Freq cf = cumulativeFreq(freq)
 
// Create the dictionary
Map<Long, Character> dict = new HashMap<>()
for (Map.Entry<Character, Long> entry : cf.entrySet()) dict[entry.value] = entry.key
 
// Fill the gaps in the dictionary
long lchar = -1
for (long i = 0; i < base; ++i) {
Character v = dict[i]
if (null != v) {
lchar = v
} else if (lchar != -1) {
dict[i] = lchar as Character
}
}
 
// Decode the input number
StringBuilder decoded = new StringBuilder((int) base)
BigInteger bigBase = base
for (long i = base - 1; i >= 0; --i) {
BigInteger pow = bigBase.pow((int) i)
BigInteger div = enc.divide(pow)
Character c = dict[div.longValue()]
BigInteger fv = freq[c]
BigInteger cv = cf[c]
BigInteger diff = enc - pow * cv
enc = diff.divide(fv)
decoded.append(c)
}
// Return the decoded output
return decoded.toString()
}
 
static void main(String[] args) {
long radix = 10
String[] strings = ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"]
String fmt = "%-25s=> %19s * %d^%s\n"
for (String str : strings) {
Triple<BigInteger, Integer, Freq> encoded = arithmeticCoding(str, radix)
String dec = arithmeticDecoding(encoded.a, radix, encoded.b, encoded.c)
System.out.printf(fmt, str, encoded.a, radix, encoded.b)
if (!Objects.equals(str, dec)) throw new RuntimeException("\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|J}}==
 
Implementation:
 
<syntaxhighlight lang="j">NB. generate a frequency dictionary from a reference string
<lang J>aek=:3 :0
aekDict=:verb define
b=. x:#y
d=. ~.y NB. dictionary lists unique characters
f=. (#/.~{~~.i.]) y
o=. /:d NB. in canonical order
c=. _65+a.i.y
f=. (#/.~%&x:#)y NB. and their relative frequencies
L=. b #. c**/\1,}:f
p=. */(o{d);o{f
)
e=. x:<.10^.p
 
NB. encode a string against a reference dict
aekEnc=:verb define
NB. use string to generate a dict if none provided
(aekDict y) aekEnc y
:
'u F'=.x NB. unpack dictionary
b=. x:#y NB. numeric base
f=. b*F NB. absolute frequencies
i=. u i.y NB. character indices
c=. +/\0,}:f NB. cumulative frequencies
L=. b #. (i{c)**/\1,}:i{f NB. lower bound
p=. */i{f NB. product of character frequencies
e=. x:<.10^.p NB. number of decimal positions to drop
e,~<.(L+p)%10^e
)
)</lang>
 
aekDec=:adverb define
Results are number pairs where the second number is the number of zeros to append to the first.
:
'u F'=. x NB. unpack dictionary
f=. m*F NB. frequencies of characters
c=.+/\0,}:f NB. cumulative frequencies
C=.<:}.c,m NB. id lookup table
N=. (* 10&^)/y NB. remainder being decoded
r=. '' NB. result of decode
for_d. m^x:i.-m do. NB. positional values
id=. <.N%d NB. character id
i=.C I.id NB. character index
N=.<.(N -(i{c)*d)%i{f NB. corrected remainder
r=.r,u{~i NB. accumulated result
end.
)
 
NB. task demo utility:
aek=:verb define
dict=. aekDict y
echo 'Dictionary:'
echo ' ',.(0{::dict),.' ',.":,.1{::dict
echo 'Length:'
echo ' ',":#y
echo 'Encoded:'
echo ' ',":dict aekEnc y
echo 'Decoded:'
echo ' ',":dict (#y) aekDec aekEnc y
)</syntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> aek 'DABDDB'
Dictionary:
251 2
A 1r6
B 1r3
D 1r2
Length:
6
Encoded:
251 2
Decoded:
DABDDB
 
aek 'DABDDBBDDBA'
Dictionary:
83677 6
A 2r11
B 4r11
D 5r11
Length:
11
Encoded:
167351 6
Decoded:
DABDDBBDDBA
 
aek 'ABRACADABRA'
Dictionary:
4860830 4
A 5r11
B 2r11
C 1r11
D 1r11
R 2r11
Length:
11
Encoded:
7954170 4
Decoded:
ABRACADABRA
 
aek 'TOBEORNOTTOBEORTOBEORNOT'
Dictionary:
1224972022395235072 15</lang>
B 1r8
E 1r8
N 1r12
O 1r3
R 1r8
T 5r24
Length:
24
Encoded:
1150764267498783364 15
Decoded:
TOBEORNOTTOBEORTOBEORNOT</syntaxhighlight>
 
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.
Draft note: these results are different from those of some other implementations currently visible here. I expect that that difference occurs from those other implementations using cumulative frequency instead of frequency at the wrong place in the calculation. (If I am incorrect about this, I'd appreciate a detailed exposition.)
 
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
 
public class ArithmeticCoding {
private static class Triple<A, B, C> {
A a;
B b;
C c;
 
Triple(A a, B b, C c) {
this.a = a;
this.b = b;
this.c = c;
}
}
 
private static class Freq extends HashMap<Character, Long> {
//"type alias"
}
 
private static Freq cumulativeFreq(Freq freq) {
long total = 0;
Freq cf = new Freq();
for (int i = 0; i < 256; ++i) {
char c = (char) i;
Long v = freq.get(c);
if (v != null) {
cf.put(c, total);
total += v;
}
}
return cf;
}
 
private static Triple<BigInteger, Integer, Freq> arithmeticCoding(String str, Long radix) {
// Convert the string into a char array
char[] chars = str.toCharArray();
 
// The frequency characters
Freq freq = new Freq();
for (char c : chars) {
if (!freq.containsKey(c))
freq.put(c, 1L);
else
freq.put(c, freq.get(c) + 1);
}
 
// The cumulative frequency
Freq cf = cumulativeFreq(freq);
 
// Base
BigInteger base = BigInteger.valueOf(chars.length);
 
// LowerBound
BigInteger lower = BigInteger.ZERO;
 
// Product of all frequencies
BigInteger pf = BigInteger.ONE;
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
for (char c : chars) {
BigInteger x = BigInteger.valueOf(cf.get(c));
lower = lower.multiply(base).add(x.multiply(pf));
pf = pf.multiply(BigInteger.valueOf(freq.get(c)));
}
 
// Upper bound
BigInteger upper = lower.add(pf);
 
int powr = 0;
BigInteger bigRadix = BigInteger.valueOf(radix);
 
while (true) {
pf = pf.divide(bigRadix);
if (pf.equals(BigInteger.ZERO)) break;
powr++;
}
 
BigInteger diff = upper.subtract(BigInteger.ONE).divide(bigRadix.pow(powr));
return new Triple<>(diff, powr, freq);
}
 
private static String arithmeticDecoding(BigInteger num, long radix, int pwr, Freq freq) {
BigInteger powr = BigInteger.valueOf(radix);
BigInteger enc = num.multiply(powr.pow(pwr));
long base = 0;
for (Long v : freq.values()) base += v;
 
// Create the cumulative frequency table
Freq cf = cumulativeFreq(freq);
 
// Create the dictionary
Map<Long, Character> dict = new HashMap<>();
for (Map.Entry<Character, Long> entry : cf.entrySet()) dict.put(entry.getValue(), entry.getKey());
 
// Fill the gaps in the dictionary
long lchar = -1;
for (long i = 0; i < base; ++i) {
Character v = dict.get(i);
if (v != null) {
lchar = v;
} else if (lchar != -1) {
dict.put(i, (char) lchar);
}
}
 
// Decode the input number
StringBuilder decoded = new StringBuilder((int) base);
BigInteger bigBase = BigInteger.valueOf(base);
for (long i = base - 1; i >= 0; --i) {
BigInteger pow = bigBase.pow((int) i);
BigInteger div = enc.divide(pow);
Character c = dict.get(div.longValue());
BigInteger fv = BigInteger.valueOf(freq.get(c));
BigInteger cv = BigInteger.valueOf(cf.get(c));
BigInteger diff = enc.subtract(pow.multiply(cv));
enc = diff.divide(fv);
decoded.append(c);
}
// Return the decoded output
return decoded.toString();
}
 
public static void main(String[] args) {
long radix = 10;
String[] strings = {"DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"};
String fmt = "%-25s=> %19s * %d^%s\n";
for (String str : strings) {
Triple<BigInteger, Integer, Freq> encoded = arithmeticCoding(str, radix);
String dec = arithmeticDecoding(encoded.a, radix, encoded.b, encoded.c);
System.out.printf(fmt, str, encoded.a, radix, encoded.b);
if (!Objects.equals(str, dec)) throw new RuntimeException("\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|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.
<syntaxhighlight lang="julia">function charfreq(s)
d = Dict()
for c in s
if haskey(d, c)
d[c] += 1
else
d[c] = 1
end
end
d
end
 
function charcumfreq(dfreq)
lastval = 0
d = Dict()
for c in sort!(collect(keys(dfreq)))
d[c] = lastval
lastval += dfreq[c]
end
d
end
 
function L(s, dfreq, dcumfreq)
nbase = BigInt(length(s))
lsum, cumprod = BigInt(0), 1
for (i, c) in enumerate(s)
lsum += nbase^(nbase - i) * dcumfreq[c] * cumprod
cumprod *= dfreq[c]
end
lsum
end
 
U(l, s, dfreq) = l + prod(c -> dfreq[c], s)
 
function mostzeros(low, high)
z = Int(floor(log10(high - low)))
if z == 0
return string(low), 0
end
if low <= parse(BigInt, string(high)[1:end- z - 1] * "0"^(z + 1)) <= high
z += 1
end
return string(high)[1:end-z], z
end
 
function msgnum(s)
dfreq = charfreq(s)
dcumfreq = charcumfreq(dfreq)
low = L(s, dfreq, dcumfreq)
high = U(low, s, dfreq)
return mostzeros(low, high), dfreq
end
 
function decode(encoded, fdict)
cdict, bas = charcumfreq(fdict), sum(values(fdict))
kys = sort!(collect(keys(cdict)))
revdict = Dict([(cdict[k], k) for k in kys])
lastkey = revdict[0]
for i in 0:bas
if !haskey(revdict, i)
revdict[i] = lastkey
else
lastkey = revdict[i]
end
end
rem = parse(BigInt, encoded)
s = ""
for i in 1:bas
basepow = BigInt(bas)^(bas -i)
c = revdict[div(rem, basepow)]
s *= c
rem = div(rem - basepow * cdict[c], fdict[c])
end
s
end
 
for s in ["DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"]
(encoded, z), dfreq = msgnum(s)
println(lpad(s, 30), " ", rpad(encoded, 19), " * 10^", rpad(z, 4), " ",
decode(encoded * "0"^z, dfreq))
end
</syntaxhighlight>{{out}}
<pre>
DABDDB 251 * 10^2 DABDDB
DABDDBBDDBA 16735 * 10^7 DABDDBBDDBA
ABRACADABRA 795417 * 10^5 ABRACADABRA
TOBEORNOTTOBEORTOBEORNOT 1150764267498783364 * 10^15 TOBEORNOTTOBEORTOBEORNOT
</pre>
 
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">// version 1.2.10
 
import java.math.BigInteger
 
typealias Freq = Map<Char, Long>
 
val bigZero = BigInteger.ZERO
val bigOne = BigInteger.ONE
 
fun cumulativeFreq(freq: Freq): Freq {
var total = 0L
val cf = mutableMapOf<Char, Long>()
for (i in 0..255) {
val c = i.toChar()
val v = freq[c]
if (v != null) {
cf[c] = total
total += v
}
}
return cf
}
 
fun arithmeticCoding(str: String, radix: Long): Triple<BigInteger, Int, Freq> {
// Convert the string into a char array
val chars = str.toCharArray()
 
// The frequency characters
val freq = mutableMapOf<Char, Long>()
for (c in chars) {
if (c !in freq)
freq[c] = 1L
else
freq[c] = freq[c]!! + 1
}
 
// The cumulative frequency
val cf = cumulativeFreq(freq)
 
// Base
val base = chars.size.toBigInteger()
 
// LowerBound
var lower = bigZero
 
// Product of all frequencies
var pf = BigInteger.ONE
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
for (c in chars) {
val x = cf[c]!!.toBigInteger()
lower = lower * base + x * pf
pf *= freq[c]!!.toBigInteger()
}
 
// Upper bound
val upper = lower + pf
 
var powr = 0
val bigRadix = radix.toBigInteger()
 
while (true) {
pf /= bigRadix
if (pf == bigZero) break
powr++
}
 
val diff = (upper - bigOne) / bigRadix.pow(powr)
return Triple(diff, powr, freq)
}
 
fun arithmeticDecoding(num: BigInteger, radix: Long, pwr: Int, freq: Freq): String {
val powr = radix.toBigInteger()
var enc = num * powr.pow(pwr)
var base = 0L
for ((_, v) in freq) base += v
 
// Create the cumulative frequency table
val cf = cumulativeFreq(freq)
 
// Create the dictionary
val dict = mutableMapOf<Long, Char>()
for ((k, v) in cf) dict[v] = k
 
// Fill the gaps in the dictionary
var lchar = -1
for (i in 0L until base) {
val v = dict[i]
if (v != null) {
lchar = v.toInt()
}
else if(lchar != -1) {
dict[i] = lchar.toChar()
}
}
 
// Decode the input number
val decoded = StringBuilder(base.toInt())
val bigBase = base.toBigInteger()
for (i in base - 1L downTo 0L) {
val pow = bigBase.pow(i.toInt())
val div = enc / pow
val c = dict[div.toLong()]
val fv = freq[c]!!.toBigInteger()
val cv = cf[c]!!.toBigInteger()
val diff = enc - pow * cv
enc = diff / fv
decoded.append(c)
}
// Return the decoded output
return decoded.toString()
}
 
fun main(args: Array<String>) {
val radix = 10L
val strings = listOf(
"DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"
)
val fmt = "%-25s=> %19s * %d^%s"
for (str in strings) {
val (enc, pow, freq) = arithmeticCoding(str, radix)
val dec = arithmeticDecoding(enc, radix, pow, freq)
println(fmt.format(str, enc, radix, pow))
if (str != dec) throw Exception("\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|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 225 ⟶ 1,401:
my %cf;
my $total = Math::BigInt->new(0);
foreach my $c (mapsort {keys chr } 0 .. 255%$freq) {
if (exists $freq->cf{$c}) {= $total;
$total += $cffreq->{$c} = $total;
$total += $freq->{$c};
}
}
 
Line 258 ⟶ 1,432:
# frequencies of all previously occurring symbols
foreach my $c (@chars) {
my $x =L->bmuladd($base, $cf{$c} * $pf);
$L->bmuladd($base, $x * $pf);
$pf->bmul($freq{$c});
}
Line 278 ⟶ 1,451:
$enc *= $radix**$pow;
 
# Base
my $base = Math::BigInt->new(0);
$base += $_ for values %{$freq};
Line 303 ⟶ 1,477:
# Decode the input number
my $decoded = '';
for (my $ipow = $base**($base - 1) ; $ipow >= 0 ; $i--pow /= $base) {
my $div = $enc / $pow;
 
my $pow = $base**$i;
my $div = ($enc / $pow);
 
my $c = $dict{$div};
Line 312 ⟶ 1,484:
my $cv = $cf{$c};
 
my $remenc = ($enc - $pow * $cv) / $fv;
 
$enc = $rem;
$decoded .= $c;
}
Line 333 ⟶ 1,503:
die "\tHowever that is incorrect!";
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 342 ⟶ 1,512:
</pre>
 
=={{header|Perl 6Phix}}==
{{trans|Go}}
<lang perl6>sub cumulative_freq(%freq) {
{{trans|Kotlin}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">diff</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;">-- Each term is multiplied by the product of the
-- frequencies of all previously occurring symbols</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">powr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<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>
<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>
<span style="color: #000000;">powr</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">pow</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Fill the gaps in the dictionary</span>
<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>
<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>
<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>
<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>
<span style="color: #000000;">lchar</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Decode the input number</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">decoded</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">decoded</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">decoded</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
DABDDB => 251 * 10^2 (ok)
DABDDBBDDBA => 167351 * 10^6 (ok)
ABRACADABRA => 7954170 * 10^4 (ok)
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15 (ok)
</pre>
 
=={{header|Python}}==
{{works with|Python|3.1+}}
<syntaxhighlight lang="python">from collections import Counter
 
def cumulative_freq(freq):
cf = {}
total = 0
for b in range(256):
if b in freq:
cf[b] = total
total += freq[b]
return cf
 
def arithmethic_coding(bytes, radix):
 
# The frequency characters
freq = Counter(bytes)
 
# The cumulative frequency table
cf = cumulative_freq(freq)
 
# Base
base = len(bytes)
 
# Lower bound
lower = 0
 
# Product of all frequencies
pf = 1
 
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
for b in bytes:
lower = lower*base + cf[b]*pf
pf *= freq[b]
 
# Upper bound
upper = lower+pf
 
pow = 0
while True:
pf //= radix
if pf==0: break
pow += 1
 
enc = (upper-1) // radix**pow
return enc, pow, freq
 
def arithmethic_decoding(enc, radix, pow, freq):
 
# Multiply enc by radix^pow
enc *= radix**pow;
 
# Base
base = sum(freq.values())
 
# Create the cumulative frequency table
cf = cumulative_freq(freq)
 
# Create the dictionary
dict = {}
for k,v in cf.items():
dict[v] = k
 
# Fill the gaps in the dictionary
lchar = None
for i in range(base):
if i in dict:
lchar = dict[i]
elif lchar is not None:
dict[i] = lchar
 
# Decode the input number
decoded = bytearray()
for i in range(base-1, -1, -1):
pow = base**i
div = enc//pow
 
c = dict[div]
fv = freq[c]
cv = cf[c]
 
rem = (enc - pow*cv) // fv
 
enc = rem
decoded.append(c)
 
# Return the decoded output
return bytes(decoded)
 
radix = 10 # can be any integer greater or equal with 2
 
for str in b'DABDDB DABDDBBDDBA ABRACADABRA TOBEORNOTTOBEORTOBEORNOT'.split():
enc, pow, freq = arithmethic_coding(str, radix)
dec = arithmethic_decoding(enc, radix, pow, freq)
 
print("%-25s=> %19s * %d^%s" % (str, enc, radix, pow))
 
if str != dec:
raise Exception("\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|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub cumulative_freq(%freq) {
my %cf;
my $total = 0;
for (0%freq.keys.255).map({.chr})sort -> $c {
if (%freqcf{$c}:exists) {= $total;
$total += %cffreq{$c} = $total;
$total += %freq{$c};
}
}
return %cf;
Line 377 ⟶ 1,772:
# frequencies of all previously occurring symbols
for @chars -> $c {
my $xL = $L*$base + %cf{$c}*$pf;
$L = $L * $base + $x * $pf;
$pf *= %freq{$c};
}
Line 401 ⟶ 1,795:
my $enc = $encoding * $radix**$pow;
 
my# $base = 0;Base
my $base += $_ for[+] %freq.values;
 
# Create the cumulative frequency table
Line 456 ⟶ 1,850:
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|Python}}==
{{works with|Python|3.1+}}
<lang python>from collections import Counter
 
def cumulative_freq(freq):
cf = {}
total = 0
for b in range(256):
if b in freq:
cf[b] = total
total += freq[b]
return cf
 
def arithmethic_coding(bytes, radix):
 
# The frequency characters
freq = Counter(bytes)
 
# The cumulative frequency table
cf = cumulative_freq(freq)
 
# Base
base = len(bytes)
 
# Lower bound
lower = 0
 
# Product of all frequencies
pf = 1
 
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
for b in bytes:
x = cf[b]
lower = lower * base + x*pf
pf *= freq[b]
 
# Upper bound
upper = lower+pf
 
pow = 0
while True:
pf //= radix
if pf==0: break
pow += 1
 
enc = (upper-1) // radix**pow
return enc, pow, freq
 
def arithmethic_decoding(enc, radix, pow, freq):
 
# Multiply enc by radix^pow
enc *= radix**pow;
 
base = 0
for v in freq.values():
base += v
 
# Create the cumulative frequency table
cf = cumulative_freq(freq)
 
# Create the dictionary
dict = {}
for k,v in cf.items():
dict[v] = k
 
# Fill the gaps in the dictionary
lchar = None
for i in range(base):
if i in dict:
lchar = dict[i]
elif lchar is not None:
dict[i] = lchar
 
# Decode the input number
decoded = bytearray()
for i in range(base-1, -1, -1):
pow = base**i
div = enc//pow
 
c = dict[div]
fv = freq[c]
cv = cf[c]
 
rem = (enc - pow*cv) // fv
 
enc = rem
decoded.append(c)
 
# Return the decoded output
return bytes(decoded)
 
radix = 10 # can be any integer greater or equal with 2
 
for str in b'DABDDB DABDDBBDDBA ABRACADABRA TOBEORNOTTOBEORTOBEORNOT'.split():
enc, pow, freq = arithmethic_coding(str, radix)
dec = arithmethic_decoding(enc, radix, pow, freq)
 
print("%-25s=> %19s * %d^%s" % (str, enc, radix, pow))
 
if str != dec:
raise Exception("\tHowever that is incorrect!")</lang>
{{out}}
<pre>
Line 576 ⟶ 1,860:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">def cumulative_freq(freq)
cf = {}
total = 0
(0freq.keys.255)sort.each do |b|
cf[b] = total
if freq.has_key?(b)
total += cffreq[b] = total
total += freq[b]
end
end
return cf
Line 609 ⟶ 1,891:
# frequencies of all previously occurring symbols
bytes.each do |b|
xlower = lower*base + cf[b]*pf
lower = lower * base + x*pf
pf *= freq[b]
end
Line 633 ⟶ 1,914:
enc *= radix**pow;
 
base# = 0Base
base = freq.values.reduce(:+)
freq.each_value { |v| base += v }
 
# Create the cumulative frequency table
Line 687 ⟶ 1,968:
raise "\tHowever that is incorrect!"
end
end</langsyntaxhighlight>
{{out}}
<pre>
Line 695 ⟶ 1,976:
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
 
=={{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)].
<syntaxhighlight lang="scala">object ArithmeticCoding extends App {
val (radix, strings) = (10, Seq("DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"))
val fmt = "%-25s=> %19s * %d^%s"
 
def arithmeticDecoding( num: BigInt, radix: Int, pwr: Int, freq: Map[Char, Long]): String = {
var enc = num * BigInt(radix).pow(pwr)
val base: Long = freq.map { case (_: Char, v: Long) => v }.sum
 
// Create the cumulative frequency table
val cf = cumulativeFreq(freq)
// Create the dictionary
val dict0: Map[Long, Char] = cf.map { el: (Char, Long) => (el._2, el._1) }
 
var lchar = -1
val dict: Map[Long, Char] = (0L until base)
.map { i =>
val v: Option[Char] = dict0.get(i)
if (v.isDefined) {
lchar = v.get.toInt
(i, v.get)
} else if (lchar != -1) (i, lchar.toChar)
else (-1L, ' ')
}.filter(_ != (-1, ' ')).toMap
 
// Decode the input number
val (bigBase, decoded) = (BigInt(base), new StringBuilder(base.toInt))
for (i <- base - 1 to 0L by -1) {
val pow = bigBase.pow(i.toInt)
val div = enc / pow
val c = dict(div.longValue)
val diff = enc - (pow * cf(c))
enc = diff / freq(c)
decoded.append(c)
}
decoded.mkString
}
 
def cumulativeFreq(freq: Map[Char, Long]): Map[Char, Long] = {
var total = 0L
 
// freq.toSeq.scanLeft(('_', 0L)){ case ((_, acc), (x, y)) => (x, (acc + y))}.filter(_ !=('_', 0L) ).toMap
freq.toSeq.sortBy(_._1).map { case (k, v) => val temp = total; total += v; (k, temp) }.toMap
}
 
private def arithmeticCoding( str: String, radix: Int): (BigInt, Int, Map[Char, Long]) = {
val freq = str.toSeq.groupBy(c => c).map { el: (Char, Seq[Char]) =>
(el._1, el._2.length.toLong)
}
val cf = cumulativeFreq(freq)
var (lower, pf) = (BigInt(0), BigInt(1))
 
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
for (c <- str) {
lower = (lower * str.length) + cf(c) * pf
pf = pf * freq(c)
}
// Upper bound
var powr = 0
val (bigRadix, upper) = (BigInt(radix.toLong), lower + pf)
do { pf = pf / bigRadix
if (pf != 0) powr += 1
} while (pf != 0)
((upper - 1) / bigRadix.pow(powr), powr, freq)
}
 
for (str <- strings) {
val encoded = arithmeticCoding(str, radix)
 
def dec =
arithmeticDecoding(num = encoded._1, radix = radix, pwr = encoded._2, freq = encoded._3)
 
println(fmt.format(str, encoded._1, radix, encoded._2))
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!")
}
}</syntaxhighlight>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func cumulative_freq(freq) {
var cf = Hash()
var total = 0
Line 730 ⟶ 2,090:
# frequencies of all previously occurring symbols
bytes.each { |b|
var xL = (L*base + cf{b}*pf)
L = L * base + x*pf
pf *= freq{b}
}
Line 749 ⟶ 2,108:
enc *= radix**pow;
 
var# base = 0Base
freq.each_value { |v|var base += v }freq.values.sum
 
# Create the cumulative frequency table
Line 805 ⟶ 2,164:
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|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Text
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long)
Imports Triple = System.Tuple(Of System.Numerics.BigInteger, Integer, System.Collections.Generic.Dictionary(Of Char, Long))
 
Module Module1
 
Function CumulativeFreq(freq As Freq) As Freq
Dim total As Long = 0
Dim cf As New Freq
For i = 0 To 255
Dim c = Chr(i)
If freq.ContainsKey(c) Then
Dim v = freq(c)
cf(c) = total
total += v
End If
Next
Return cf
End Function
 
Function ArithmeticCoding(str As String, radix As Long) As Triple
'The frequency of characters
Dim freq As New Freq
For Each c In str
If freq.ContainsKey(c) Then
freq(c) += 1
Else
freq(c) = 1
End If
Next
 
'The cumulative frequency
Dim cf = CumulativeFreq(freq)
 
' Base
Dim base As BigInteger = str.Length
 
' Lower bound
Dim lower As BigInteger = 0
 
' Product of all frequencies
Dim pf As BigInteger = 1
 
' Each term is multiplied by the product of the
' frequencies of all previously occuring symbols
For Each c In str
Dim x = cf(c)
lower = lower * base + x * pf
pf = pf * freq(c)
Next
 
' Upper bound
Dim upper = lower + pf
 
Dim powr = 0
Dim bigRadix As BigInteger = radix
 
While True
pf = pf / bigRadix
If pf = 0 Then
Exit While
End If
powr = powr + 1
End While
 
Dim diff = (upper - 1) / (BigInteger.Pow(bigRadix, powr))
Return New Triple(diff, powr, freq)
End Function
 
Function ArithmeticDecoding(num As BigInteger, radix As Long, pwr As Integer, freq As Freq) As String
Dim powr As BigInteger = radix
Dim enc = num * BigInteger.Pow(powr, pwr)
Dim base = freq.Values.Sum()
 
' Create the cumulative frequency table
Dim cf = CumulativeFreq(freq)
 
' Create the dictionary
Dim dict As New Dictionary(Of Long, Char)
For Each key In cf.Keys
Dim value = cf(key)
dict(value) = key
Next
 
' Fill the gaps in the dictionary
Dim lchar As Long = -1
For i As Long = 0 To base - 1
If dict.ContainsKey(i) Then
lchar = AscW(dict(i))
Else
dict(i) = ChrW(lchar)
End If
Next
 
' Decode the input number
Dim decoded As New StringBuilder
Dim bigBase As BigInteger = base
For i As Long = base - 1 To 0 Step -1
Dim pow = BigInteger.Pow(bigBase, i)
Dim div = enc / pow
Dim c = dict(div)
Dim fv = freq(c)
Dim cv = cf(c)
Dim diff = enc - pow * cv
enc = diff / fv
decoded.Append(c)
Next
 
' Return the decoded ouput
Return decoded.ToString()
End Function
 
Sub Main()
Dim radix As Long = 10
Dim strings = {"DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"}
For Each St In strings
Dim encoded = ArithmeticCoding(St, radix)
Dim dec = ArithmeticDecoding(encoded.Item1, radix, encoded.Item2, encoded.Item3)
Console.WriteLine("{0,-25}=> {1,19} * {2}^{3}", St, encoded.Item1, radix, encoded.Item2)
If St <> dec Then
Throw New Exception(vbTab + "However that is incorrect!")
End If
Next
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
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)
<syntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); // libGMP
 
fcn cumulativeFreq(freqHash){
total,cf := 0,Dictionary();
foreach b in (256){ if(v:=freqHash.find(b)){ cf[b]=total; total+=v; } }
cf
}
fcn arithmethicCoding(str, radix){
bytes :=str.split("").apply("toAsc"); // string to bytes: "0"-->0x31
freqHash:=Dictionary(); bytes.pump(Void,freqHash.incV); // frequency chars
cf :=cumulativeFreq(freqHash); // The cumulative frequency
base,lower:=bytes.len(), BN(0); // Lower bound
pf:=BN(1); // Product of all frequencies
// Each term is multiplied by the product of the
// frequencies of all previously occurring symbols
foreach b in (bytes){
lower.mul(base).add(pf*cf[b]); // gets quite large
pf.mul(freqHash[b]); // gets big
}
 
upper,powr := lower + pf, 0;
while(1){
pf.div(radix); // in place BigInt math, no garbage
if(pf==0) break;
powr+=1;
}
enc:=(upper - 1)/BN(radix).pow(powr);
 
return(enc,powr,freqHash);
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn arithmethicDecoding(enc, radix, powr, freqHash){
enc*=radix.pow(powr);
base:=freqHash.values.sum(0);
cf :=cumulativeFreq(freqHash); // Create the cumulative frequency table
dict:=cf.pump(Dictionary(), // Invert/transpose cumulative table, keys are strings
fcn(kv){ kv.reverse().apply("toInt") });
// Fill the gaps in the dictionary
lchar:=Void;
foreach b in (base){
if(v:=dict.find(b)) lchar=v;
else if(lchar) dict[b]=lchar;
}
// Decode the input number
decoded:=Data(); // byte bucket
foreach n in ([base-1..0, -1]){
pow:=BN(base).pow(n); // a big number
div:=(enc/pow).toInt(); // a small number, convert from BigInt
c,fv,cv := dict[div],freqHash[c],cf[c];
decoded.append(c.toChar());
enc.sub(pow*cv).div(fv); // in place BigInt math, no garbage
}
decoded.text // Return the decoded output
}</syntaxhighlight>
<syntaxhighlight lang="zkl">radix:=10;
testStrings:=T(
"DABDDB",
"DABDDBBDDBA",
"ABRACADABRA",
"TOBEORNOTTOBEORTOBEORNOT",);
foreach str in (testStrings){
enc,pow,freq := arithmethicCoding(str,radix);
dec:=arithmethicDecoding(enc, radix, pow, freq);
print("%-25s=> %19s * %d^%s\n".fmt(str,enc,radix,pow));
if(str!=dec) println("\tHowever that is incorrect!");
}</syntaxhighlight>
{{out}}
<pre>
Alextretyak
1,480

edits

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