Anonymous user
Arithmetic coding/As a generalized change of radix: Difference between revisions
Arithmetic coding/As a generalized change of radix (view source)
Revision as of 06:22, 23 September 2016
, 7 years ago→{{header|Sidef}}: added zkl
m (→{{header|J}}) |
(→{{header|Sidef}}: added zkl) |
||
Line 873:
die "\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|zkl}}==
Uses libGMP (GNU MP Bignum Library)
<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);
}</lang>
<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(D(), // 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
}</lang>
<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!");
}</lang>
{{out}}
| |||