Arithmetic coding/As a generalized change of radix: Difference between revisions

Content added Content deleted
(added python)
(simplified the encoding loop a little bit)
Line 62: Line 62:
// frequencies of all previously occurring symbols
// frequencies of all previously occurring symbols
bigBase := big.NewInt(int64(base))
bigBase := big.NewInt(int64(base))
⚫
bigLim := big.NewInt(int64(base - 1))


for i := 0; i < base; i++ {
for _, c := range chars {
⚫
x := big.NewInt(cf[c])

bigI := big.NewInt(int64(i))

diff := big.NewInt(0)
diff.Sub(bigLim, bigI)

pow := big.NewInt(0)
pow.Exp(bigBase, diff, nil)

x := big.NewInt(1)
x.Mul(big.NewInt(cf[chars[i]]), pow)


L.Mul(L, bigBase)
L.Add(L, x.Mul(x, pf))
L.Add(L, x.Mul(x, pf))
pf.Mul(pf, big.NewInt(freq[chars[i]]))
pf.Mul(pf, big.NewInt(freq[c]))
}
}


Line 256: Line 246:
my %cf = cumulative_freq(\%freq);
my %cf = cumulative_freq(\%freq);


# Limit and base
# Base
my $lim = Math::BigInt->new($#chars);
my $base = Math::BigInt->new(scalar @chars);
my $base = $lim + 1;


# Lower bound
# Lower bound
Line 268: Line 257:
# Each term is multiplied by the product of the
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
# frequencies of all previously occurring symbols
for (my $i = 0 ; $i < $base ; $i++) {
foreach my $c (@chars) {
my $x = $cf{$chars[$i]} * $base**($lim - $i);
my $x = $cf{$c};
$L->badd($x * $pf);
$L->bmuladd($base, $x * $pf);
$pf->bmul($freq{$chars[$i]});
$pf->bmul($freq{$c});
}
}


Line 376: Line 365:
my %cf = cumulative_freq(%freq);
my %cf = cumulative_freq(%freq);


# Limit and base
# Base
my $lim = @chars.end;
my $base = @chars.elems;
my $base = $lim + 1;


# Lower bound
# Lower bound
Line 388: Line 376:
# Each term is multiplied by the product of the
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
# frequencies of all previously occurring symbols
for ^$base -> $i {
for @chars -> $c {
my $x = %cf{@chars[$i]} * $base**($lim - $i);
my $x = %cf{$c};
$L += $x * $pf;
$L = $L * $base + $x * $pf;
$pf *= %freq{@chars[$i]};
$pf *= %freq{$c};
}
}


Line 498: Line 486:
cf = cumulative_freq(freq)
cf = cumulative_freq(freq)


# Limit and base
# Base
lim = len(bytes)-1
base = len(bytes)
base = lim+1


# Lower bound
# Lower bound
Line 510: Line 497:
# Each term is multiplied by the product of the
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
# frequencies of all previously occurring symbols
for i in range(base):
for b in bytes:
x = cf[bytes[i]] * base**(lim-i)
x = cf[b]
lower += x*pf
lower = lower * base + x*pf
pf *= freq[bytes[i]]
pf *= freq[b]


# Upper bound
# Upper bound
Line 610: Line 597:
cf = cumulative_freq(freq)
cf = cumulative_freq(freq)


# Limit and base
# Base
lim = bytes.size-1
base = bytes.size
base = lim+1


# Lower bound
# Lower bound
Line 622: Line 608:
# Each term is multiplied by the product of the
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
# frequencies of all previously occurring symbols
(0...base).each do |i|
bytes.each do |b|
x = cf[bytes[i]] * base**(lim-i)
x = cf[b]
lower += x*pf
lower = lower * base + x*pf
pf *= freq[bytes[i]]
pf *= freq[b]
end
end


Line 732: Line 718:
var cf = cumulative_freq(freq)
var cf = cumulative_freq(freq)


# Limit and base
# Base
var lim = bytes.end
var base = bytes.len
var base = lim+1


# Lower bound
# Lower bound
Line 744: Line 729:
# Each term is multiplied by the product of the
# Each term is multiplied by the product of the
# frequencies of all previously occurring symbols
# frequencies of all previously occurring symbols
base.range.each { |i|
bytes.each { |b|
var x = (cf{bytes[i]} * base**(lim - i))
var x = cf{b}
L += x*pf
L = L * base + x*pf
pf *= freq{bytes[i]}
pf *= freq{b}
}
}


Retrieved from "https://rosettacode.org/wiki/Arithmetic_coding/As_a_generalized_change_of_radix"