Arithmetic coding/As a generalized change of radix: Difference between revisions
Arithmetic coding/As a generalized change of radix (view source)
Revision as of 09:02, 7 April 2024
, 2 months ago→{{header|11l}}: X.throw
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
|||
(5 intermediate revisions by 4 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}}
<
using System.Collections.Generic;
using System.Linq;
Line 144 ⟶ 240:
}
}
}</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 153 ⟶ 249:
=={{header|D}}==
{{trans|Go}}
<
import std.bigint;
import std.stdio;
Line 304 ⟶ 400:
}
}
}</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 312 ⟶ 408:
=={{header|Go}}==
<
import (
Line 474 ⟶ 570:
}
}
}</
{{out}}
<pre>
Line 485 ⟶ 581:
=={{header|Groovy}}==
{{trans|Java}}
<
private static class Triple<A, B, C> {
A a
Line 620 ⟶ 716:
}
}
}</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 631 ⟶ 727:
Implementation:
<
aekDict=:verb define
d=. ~.y NB. dictionary lists unique characters
Line 682 ⟶ 778:
echo 'Decoded:'
echo ' ',":dict (#y) aekDec aekEnc y
)</
Example use:
<
Dictionary:
A 1r6
Line 737 ⟶ 833:
1150764267498783364 15
Decoded:
TOBEORNOTTOBEORTOBEORNOT</
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}}
<
import java.util.HashMap;
import java.util.Map;
Line 880 ⟶ 976:
}
}
}</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 889 ⟶ 985:
=={{header|JavaScript}}==
{{trans|C#}}
<syntaxhighlight lang="javascript">
function CumulativeFreq(freq) {
let total = 0;
Line 976 ⟶ 1,072:
}
}
</syntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 985 ⟶ 1,081:
=={{header|Julia}}==
Taken from the wikipedia example.
<
d = Dict()
for c in s
Line 1,066 ⟶ 1,162:
decode(encoded * "0"^z, dfreq))
end
</
<pre>
DABDDB 251 * 10^2 DABDDB
Line 1,076 ⟶ 1,172:
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 1,202 ⟶ 1,298:
if (str != dec) throw Exception("\tHowever that is incorrect!")
}
}</
{{out}}
Line 1,215 ⟶ 1,311:
{{trans|Kotlin}}
{{libheader|bignum}}
<
import bignum
Line 1,289 ⟶ 1,385:
let dec = arithmeticDecoding(enc, Radix, pow, freq)
echo &"{str:<25}→ {enc:>19} * {Radix}^{pow}"
doAssert str == dec, "\tHowever that is incorrect!"</
{{out}}
Line 1,298 ⟶ 1,394:
=={{header|Perl}}==
<
sub cumulative_freq {
Line 1,407 ⟶ 1,503:
die "\tHowever that is incorrect!";
}
}</
{{out}}
<pre>
Line 1,420 ⟶ 1,516:
{{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=> %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,533 ⟶ 1,632:
=={{header|Python}}==
{{works with|Python|3.1+}}
<
def cumulative_freq(freq):
Line 1,630 ⟶ 1,729:
if str != dec:
raise Exception("\tHowever that is incorrect!")</
{{out}}
<pre>
Line 1,641 ⟶ 1,740:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my %cf;
my $total = 0;
Line 1,751 ⟶ 1,850:
die "\tHowever that is incorrect!";
}
}</
{{out}}
<pre>
Line 1,761 ⟶ 1,860:
=={{header|Ruby}}==
<
cf = {}
total = 0
Line 1,869 ⟶ 1,968:
raise "\tHowever that is incorrect!"
end
end</
{{out}}
<pre>
Line 1,880 ⟶ 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)].
<
val (radix, strings) = (10, Seq("DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"))
val fmt = "%-25s=> %19s * %d^%s"
Line 1,955 ⟶ 2,054:
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!")
}
}</
=={{header|Sidef}}==
<
var cf = Hash()
var total = 0
Line 2,065 ⟶ 2,164:
die "\tHowever that is incorrect!"
}
}</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 2,074 ⟶ 2,173:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Text
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long)
Line 2,200 ⟶ 2,299:
End Sub
End Module</
{{out}}
<pre>DABDDB => 251 * 10^2
Line 2,211 ⟶ 2,310:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var cumulativeFreq = Fn.new { |freq|
Line 2,330 ⟶ 2,429:
Fmt.print(fmt, str, enc, radix, pow)
if (str != dec) Fiber.abort("\tHowever that is incorrect!")
}</
{{out}}
Line 2,342 ⟶ 2,441:
=={{header|zkl}}==
Uses libGMP (GNU MP Bignum Library)
<
fcn cumulativeFreq(freqHash){
Line 2,374 ⟶ 2,473:
return(enc,powr,freqHash);
}</
<
enc*=radix.pow(powr);
base:=freqHash.values.sum(0);
Line 2,398 ⟶ 2,497:
}
decoded.text // Return the decoded output
}</
<
testStrings:=T(
"DABDDB",
Line 2,412 ⟶ 2,511:
if(str!=dec) println("\tHowever that is incorrect!");
}</
{{out}}
<pre>
|