0
$\begingroup$

I'm looking at Shannon's source coding theorem for symbol codes. It provides a very nice bound on the expected code length $S=|f(X)|$ of an optimal code $f$ over the sequence variable $X$:

$$ \frac{H(X)}{log_2(a)} \le \mathbb{E}[S] \lt \frac{H(X)}{log_2(a)} + 1 $$

It does not however prescribe an algorithm that can learn an optimal code $f$ with size $a$ for a data set of sequences $D=\{D_0, D_1, ...\}$, where $D \stackrel{iid}{\sim} X$

In pseudocode, I think it would look something like:

$$ f = learn(D, a) $$ $$ T_i = encode(D_i, f) $$ $$ D_i = decode(T_i, f) $$

Is there an algorithm for that?

One trivial example is, if $a \ge |D|$, we could set $f=D$ and say $T_i = (i)$, which guarantees length 1, however I'm more interested in the $a \ll |D|$ regime.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Arithmetic codes can get arbitrarily close to the Shannon limit, assuming your model of probabilities is correct. It it typically shown in the context of a binary alphabet, but there's nothing fundamental about that. It can work in any radix, as well as mixed-radix systems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.