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

2,575 bytes added ,  2 months ago
m
→‎{{header|11l}}: X.throw
m (→‎{{header|Phix}}: added syntax colouring the hard way, mpz_get_si() => mpz_get_integer().)
 
(4 intermediate revisions by 3 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
</langpre>▼
 
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 144 ⟶ 240:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 153 ⟶ 249:
=={{header|D}}==
{{trans|Go}}
<langsyntaxhighlight Dlang="d">import std.array;
import std.bigint;
import std.stdio;
Line 304 ⟶ 400:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 312 ⟶ 408:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 474 ⟶ 570:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 485 ⟶ 581:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">class ArithmeticCoding {
private static class Triple<A, B, C> {
A a
Line 620 ⟶ 716:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 631 ⟶ 727:
Implementation:
 
<langsyntaxhighlight Jlang="j">NB. generate a frequency dictionary from a reference string
aekDict=:verb define
d=. ~.y NB. dictionary lists unique characters
Line 682 ⟶ 778:
echo 'Decoded:'
echo ' ',":dict (#y) aekDec aekEnc y
)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> aek 'DABDDB'
Dictionary:
A 1r6
Line 737 ⟶ 833:
1150764267498783364 15
Decoded:
TOBEORNOTTOBEORTOBEORNOT</langsyntaxhighlight>
 
Note that for this task we use our plaintext to generate our dictionary for decoding. Also note that we use rational numbers, rather than floating point, for our dictionary, because floating point tends to be inexact.
Line 743 ⟶ 839:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
Line 880 ⟶ 976:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 889 ⟶ 985:
=={{header|JavaScript}}==
{{trans|C#}}
<syntaxhighlight lang="javascript">
<lang JavaScript>
function CumulativeFreq(freq) {
let total = 0;
Line 976 ⟶ 1,072:
}
}
</syntaxhighlight>
▲</lang>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 985 ⟶ 1,081:
=={{header|Julia}}==
Taken from the wikipedia example.
<langsyntaxhighlight lang="julia">function charfreq(s)
d = Dict()
for c in s
Line 1,066 ⟶ 1,162:
decode(encoded * "0"^z, dfreq))
end
</langsyntaxhighlight>{{out}}
<pre>
DABDDB 251 * 10^2 DABDDB
Line 1,076 ⟶ 1,172:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.2.10
 
import java.math.BigInteger
Line 1,202 ⟶ 1,298:
if (str != dec) throw Exception("\tHowever that is incorrect!")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,215 ⟶ 1,311:
{{trans|Kotlin}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import strformat, sugar, tables
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!"</langsyntaxhighlight>
 
{{out}}
Line 1,298 ⟶ 1,394:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use Math::BigInt (try => 'GMP');
 
sub cumulative_freq {
Line 1,407 ⟶ 1,503:
die "\tHowever that is incorrect!";
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,420 ⟶ 1,516:
{{trans|Kotlin}}
{{libheader|Phix/mpfr}}
<!--<langsyntaxhighlight Phixlang="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>
Line 1,525 ⟶ 1,621:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,536 ⟶ 1,632:
=={{header|Python}}==
{{works with|Python|3.1+}}
<langsyntaxhighlight lang="python">from collections import Counter
 
def cumulative_freq(freq):
Line 1,633 ⟶ 1,729:
 
if str != dec:
raise Exception("\tHowever that is incorrect!")</langsyntaxhighlight>
{{out}}
<pre>
Line 1,644 ⟶ 1,740:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>sub cumulative_freq(%freq) {
my %cf;
my $total = 0;
Line 1,754 ⟶ 1,850:
die "\tHowever that is incorrect!";
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,764 ⟶ 1,860:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">def cumulative_freq(freq)
cf = {}
total = 0
Line 1,872 ⟶ 1,968:
raise "\tHowever that is incorrect!"
end
end</langsyntaxhighlight>
{{out}}
<pre>
Line 1,883 ⟶ 1,979:
=={{header|Scala}}==
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/EUNJ0zp/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/DVl840oDS2mFvFQ560fxJAScastie (remote JVM)].
<langsyntaxhighlight Scalalang="scala">object ArithmeticCoding extends App {
val (radix, strings) = (10, Seq("DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT"))
val fmt = "%-25s=> %19s * %d^%s"
Line 1,958 ⟶ 2,054:
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!")
}
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func cumulative_freq(freq) {
var cf = Hash()
var total = 0
Line 2,068 ⟶ 2,164:
die "\tHowever that is incorrect!"
}
}</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 2,077 ⟶ 2,173:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Text
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long)
Line 2,203 ⟶ 2,299:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>DABDDB => 251 * 10^2
Line 2,214 ⟶ 2,310:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
import "./fmt" for Fmt
 
var cumulativeFreq = Fn.new { |freq|
Line 2,333 ⟶ 2,429:
Fmt.print(fmt, str, enc, radix, pow)
if (str != dec) Fiber.abort("\tHowever that is incorrect!")
}</langsyntaxhighlight>
 
{{out}}
Line 2,345 ⟶ 2,441:
=={{header|zkl}}==
Uses libGMP (GNU MP Bignum Library)
<langsyntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); // libGMP
 
fcn cumulativeFreq(freqHash){
Line 2,377 ⟶ 2,473:
 
return(enc,powr,freqHash);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn arithmethicDecoding(enc, radix, powr, freqHash){
enc*=radix.pow(powr);
base:=freqHash.values.sum(0);
Line 2,401 ⟶ 2,497:
}
decoded.text // Return the decoded output
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">radix:=10;
testStrings:=T(
"DABDDB",
Line 2,415 ⟶ 2,511:
if(str!=dec) println("\tHowever that is incorrect!");
}</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,481

edits

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