I have a set of bytes (utf-8), and need to encode them into the smallest dataset possible using a Base N encoding scheme. Is it simply the higher the Base N encoding is (ie something like Base85 encoding) the smaller the output will be, or is there a point where using a higher base encoding creates longer outputs? What base number encoding should I use for a minimum length output?

  • $\begingroup$ Ignoring compression issues, if your input has $m$ bits and you use a base-$N$ encoding, then you'll need $\left\lceil\frac{m}{\log N}\right\rceil$ symbols. If you encode symbols with a fixed length encoding, then you'll need at least $\lceil\log N\rceil$ bits per symbol. This is a convoluted way to say that, in general, there is no magic way to encode $m$ bits in less than $m$ bits. The above could be achieved, however, if the input distribution is not uniform and you are fine with a variable-length encoding (see e.g., the Huffman code). $\endgroup$ – Steven Oct 18 at 14:22
  • $\begingroup$ UTF-8 can always be compressed because it cannot contain arbitrary bytes. It is intentionally redundant to always allow finding the first byte of a code point, and to scan backwards to the previous code point. $\endgroup$ – gnasher729 Oct 19 at 23:05

Your Answer

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

Browse other questions tagged or ask your own question.