Arithmetic coding/As a generalized change of radix: Difference between revisions
Arithmetic coding/As a generalized change of radix (view source)
Revision as of 05:32, 4 August 2021
, 2 years agoAdded 11l
m (→{{header|Phix}}: added syntax colouring the hard way, mpz_get_si() => mpz_get_integer().) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 13:
Verify the implementation by decoding the results back into strings and checking for equality with the given strings.
=={{header|11l}}==
{{trans|Python}}
<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 RuntimeError("\tHowever that is incorrect!")</lang>
{{out}}
<pre>
DABDDB => 251 * 10^2
DABDDBBDDBA => 167351 * 10^6
ABRACADABRA => 7954170 * 10^4
TOBEORNOTTOBEORTOBEORNOT => 1150764267498783364 * 10^15
</pre>
=={{header|C sharp|C#}}==
| |||