Optimal parse with phminposuw

This problem arose when I was writing a specialized data compressor.

Say you want to encode a byte stream, and bytes can be encoded in different formats, e.g. optimized for ASCII, numbers, raw binary, etc. These formats prioritize better compression of a specific type of data. Realistic byte streams may contain all of them at different points, so we want to switch between formats on the fly optimally.

The easiest way to do so is to split data into, say, 50-byte chunks, find the best format for each chunk, and use those formats. But that doesn’t take into account that we need to store which format is used for which chunk, and choosing formats greedily may increase the size of this metadata because it itself compresses worse. Not to mention that it’s not very precise. So what should we do?