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?