1
$\begingroup$

By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like in LZ).

(Please feel free to correct me on this term, if I use it incorrectly.)

I'm thinking: what if we first find optimal set of tokens, and only then compress our data as a stream of these tokens? Will it improve compression of text or of xml or of some other kind of data? LZ sort of does this, but it is limited to letters. I'm asking about truly general approach when a token can have any bit-length. For example, it can be interesting to do it for compression of x86 executable files. Or in other cases, when sub-byte (and sup-byte) bit-strings behave as individual tokens.

How to find this set of tokens optimally? In a way that maximize average entropy of a stream of such tokens under 0-order Markov model?

Are there existing algorithms for it? Are there any algorithms related to the problem?

How to find approximation of this set? What is complexity of optimal and approximation solution?

And what if we want to maximize entropy for higher order Markov model? How harder the problem will be in this case?

$\endgroup$
  • $\begingroup$ LZ provably optimally compresses any Markovian source. $\endgroup$ – Yuval Filmus May 9 at 20:52
  • $\begingroup$ @YuvalFilmus only asymptomatically, i.e. it's not applicable to any real data or algorithm. Just try to convince anyone that lz4 and paq has the same compression ratio ))) $\endgroup$ – Bulat May 9 at 21:02
  • $\begingroup$ Of course the big catch is that real sources (like XML or text) usually aren't Markovian (not in any useful way); and those proofs hold only in the limit, but the limit might not be achieved for real data (given the amount of short-range dependence between characters). $\endgroup$ – D.W. May 9 at 22:20
1
$\begingroup$

Are there existing algorithms for it? Are there any algorithms related to the problem?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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