Arithmetic coding/As a generalized change of radix: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 17: | Line 17: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang=11l>F cumulative_freq(freq) |
||
[Int = Int] cf |
[Int = Int] cf |
||
V total = 0 |
V total = 0 |
||
Line 100: | Line 100: | ||
I str != dec |
I str != dec |
||
X RuntimeError("\tHowever that is incorrect!")</ |
X RuntimeError("\tHowever that is incorrect!")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 112: | Line 112: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang=csharp>using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 240: | Line 240: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 249: | Line 249: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang=D>import std.array; |
||
import std.bigint; |
import std.bigint; |
||
import std.stdio; |
import std.stdio; |
||
Line 400: | Line 400: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 408: | Line 408: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang=go>package main |
||
import ( |
import ( |
||
Line 570: | Line 570: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 581: | Line 581: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang=groovy>class ArithmeticCoding { |
||
private static class Triple<A, B, C> { |
private static class Triple<A, B, C> { |
||
A a |
A a |
||
Line 716: | Line 716: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 727: | Line 727: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang=J>NB. generate a frequency dictionary from a reference string |
||
aekDict=:verb define |
aekDict=:verb define |
||
d=. ~.y NB. dictionary lists unique characters |
d=. ~.y NB. dictionary lists unique characters |
||
Line 778: | Line 778: | ||
echo 'Decoded:' |
echo 'Decoded:' |
||
echo ' ',":dict (#y) aekDec aekEnc y |
echo ' ',":dict (#y) aekDec aekEnc y |
||
)</ |
)</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang=J> aek 'DABDDB' |
||
Dictionary: |
Dictionary: |
||
A 1r6 |
A 1r6 |
||
Line 833: | Line 833: | ||
1150764267498783364 15 |
1150764267498783364 15 |
||
Decoded: |
Decoded: |
||
TOBEORNOTTOBEORTOBEORNOT</ |
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. |
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 839: | Line 839: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang=Java>import java.math.BigInteger; |
||
import java.util.HashMap; |
import java.util.HashMap; |
||
import java.util.Map; |
import java.util.Map; |
||
Line 976: | Line 976: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 985: | Line 985: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang=JavaScript> |
||
function CumulativeFreq(freq) { |
function CumulativeFreq(freq) { |
||
let total = 0; |
let total = 0; |
||
Line 1,072: | Line 1,072: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 1,081: | Line 1,081: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Taken from the wikipedia example. |
Taken from the wikipedia example. |
||
< |
<syntaxhighlight lang=julia>function charfreq(s) |
||
d = Dict() |
d = Dict() |
||
for c in s |
for c in s |
||
Line 1,162: | Line 1,162: | ||
decode(encoded * "0"^z, dfreq)) |
decode(encoded * "0"^z, dfreq)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
DABDDB 251 * 10^2 DABDDB |
DABDDB 251 * 10^2 DABDDB |
||
Line 1,172: | Line 1,172: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang=scala>// version 1.2.10 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 1,298: | Line 1,298: | ||
if (str != dec) throw Exception("\tHowever that is incorrect!") |
if (str != dec) throw Exception("\tHowever that is incorrect!") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,311: | Line 1,311: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|bignum}} |
{{libheader|bignum}} |
||
< |
<syntaxhighlight lang=Nim>import strformat, sugar, tables |
||
import bignum |
import bignum |
||
Line 1,385: | Line 1,385: | ||
let dec = arithmeticDecoding(enc, Radix, pow, freq) |
let dec = arithmeticDecoding(enc, Radix, pow, freq) |
||
echo &"{str:<25}→ {enc:>19} * {Radix}^{pow}" |
echo &"{str:<25}→ {enc:>19} * {Radix}^{pow}" |
||
doAssert str == dec, "\tHowever that is incorrect!"</ |
doAssert str == dec, "\tHowever that is incorrect!"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,394: | Line 1,394: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang=perl>use Math::BigInt (try => 'GMP'); |
||
sub cumulative_freq { |
sub cumulative_freq { |
||
Line 1,503: | Line 1,503: | ||
die "\tHowever that is incorrect!"; |
die "\tHowever that is incorrect!"; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,516: | Line 1,516: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 1,621: | Line 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=> %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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,632: | Line 1,632: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{works with|Python|3.1+}} |
{{works with|Python|3.1+}} |
||
< |
<syntaxhighlight lang=python>from collections import Counter |
||
def cumulative_freq(freq): |
def cumulative_freq(freq): |
||
Line 1,729: | Line 1,729: | ||
if str != dec: |
if str != dec: |
||
raise Exception("\tHowever that is incorrect!")</ |
raise Exception("\tHowever that is incorrect!")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,740: | Line 1,740: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
< |
<syntaxhighlight lang=perl6>sub cumulative_freq(%freq) { |
||
my %cf; |
my %cf; |
||
my $total = 0; |
my $total = 0; |
||
Line 1,850: | Line 1,850: | ||
die "\tHowever that is incorrect!"; |
die "\tHowever that is incorrect!"; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,860: | Line 1,860: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang=ruby>def cumulative_freq(freq) |
||
cf = {} |
cf = {} |
||
total = 0 |
total = 0 |
||
Line 1,968: | Line 1,968: | ||
raise "\tHowever that is incorrect!" |
raise "\tHowever that is incorrect!" |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,979: | Line 1,979: | ||
=={{header|Scala}}== |
=={{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)]. |
{{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 (radix, strings) = (10, Seq("DABDDB", "DABDDBBDDBA", "ABRACADABRA", "TOBEORNOTTOBEORTOBEORNOT")) |
||
val fmt = "%-25s=> %19s * %d^%s" |
val fmt = "%-25s=> %19s * %d^%s" |
||
Line 2,054: | Line 2,054: | ||
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!") |
if (str != dec) throw new RuntimeException("\tHowever that is incorrect!") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang=ruby>func cumulative_freq(freq) { |
||
var cf = Hash() |
var cf = Hash() |
||
var total = 0 |
var total = 0 |
||
Line 2,164: | Line 2,164: | ||
die "\tHowever that is incorrect!" |
die "\tHowever that is incorrect!" |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 2,173: | Line 2,173: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang=vbnet>Imports System.Numerics |
||
Imports System.Text |
Imports System.Text |
||
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long) |
Imports Freq = System.Collections.Generic.Dictionary(Of Char, Long) |
||
Line 2,299: | Line 2,299: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DABDDB => 251 * 10^2 |
<pre>DABDDB => 251 * 10^2 |
||
Line 2,310: | Line 2,310: | ||
{{libheader|Wren-big}} |
{{libheader|Wren-big}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang=ecmascript>import "/big" for BigInt |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 2,429: | Line 2,429: | ||
Fmt.print(fmt, str, enc, radix, pow) |
Fmt.print(fmt, str, enc, radix, pow) |
||
if (str != dec) Fiber.abort("\tHowever that is incorrect!") |
if (str != dec) Fiber.abort("\tHowever that is incorrect!") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,441: | Line 2,441: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Uses libGMP (GNU MP Bignum Library) |
Uses libGMP (GNU MP Bignum Library) |
||
< |
<syntaxhighlight lang=zkl>var [const] BN=Import("zklBigNum"); // libGMP |
||
fcn cumulativeFreq(freqHash){ |
fcn cumulativeFreq(freqHash){ |
||
Line 2,473: | Line 2,473: | ||
return(enc,powr,freqHash); |
return(enc,powr,freqHash); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang=zkl>fcn arithmethicDecoding(enc, radix, powr, freqHash){ |
||
enc*=radix.pow(powr); |
enc*=radix.pow(powr); |
||
base:=freqHash.values.sum(0); |
base:=freqHash.values.sum(0); |
||
Line 2,497: | Line 2,497: | ||
} |
} |
||
decoded.text // Return the decoded output |
decoded.text // Return the decoded output |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang=zkl>radix:=10; |
||
testStrings:=T( |
testStrings:=T( |
||
"DABDDB", |
"DABDDB", |
||
Line 2,511: | Line 2,511: | ||
if(str!=dec) println("\tHowever that is incorrect!"); |
if(str!=dec) println("\tHowever that is incorrect!"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |