Arithmetic coding/As a generalized change of radix: Difference between revisions
Content added Content deleted
m (→{{header|J}}) |
(→{{header|Sidef}}: added zkl) |
||
Line 873: | Line 873: | ||
die "\tHowever that is incorrect!" |
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> |
}</lang> |
||
{{out}} |
{{out}} |