String Compression: Output Alphabet Restricted to Alphanumeric Characters
Question: I have a long string and I would like to compress it to a new string with the
restriction that the **output** alphabet only contains `[a-z]` `[A-Z]` and
`[0-9]` characters.

How can I do this, specifically in Python?


Answer: While many encoding algorithms _can_ take an arbitrary output range, most
implementations can't, and many algorithms are much less efficient if the
output range isn't a power of 2/16/256.

So, you want to split this into two parts: First compress one byte stream to
another. Then encode the output byte stream into alphanumeric characters. (If
you're starting with something that isn't a byte stream, like a Python 3
string or a Python 2 `unicode`, then there's a zeroth step of encoding it into
a byte stream.)

For example, if you wanted base64, you could do this:

    
    
    import base64, zlib
    compressed_bytes = zlib.compress(plain_bytes)
    compressed_text = base64.b64encode(compressed_bytes)
    

* * *

Unfortunately, you don't want base-64, because that includes a few non-
alphanumeric characters.

You can use [base32](http://en.wikipedia.org/wiki/Base32), which has just the
capital letters and 6 digits, and the only change to your code is `b32encode`
instead of `encode`. But that's a bit wasteful, because it's only using 5 out
of every 8 bits, when you could in theory use ~5.594 of each 8 bits.

If you want to do this optimally, and you can't bend the requirement for
alphanumeric characters only, base62 is very complicated, because you can't do
it byte by byte, but only in chunks of 7936 bytes at a time. That's not going
to be fun, or efficient. You can get reasonably close to optimal by chunking,
say, 32 bytes at a time and wasting the leftover bits. But you might be better
off using base64 plus an escaping mechanism to handle the two characters that
don't fit into your scheme. For example:

    
    
    def b62encode(plain):
        b64 = base64.b64encode(plain)
        return b64.replace('0', '00').replace('+', '01').replace('/', '02')
    
    def b62decode(data):
         b64 = '0'.join(part.replace('01', '+').replace('02', '/') 
                        for part in data.split('00'))
         return base64.b64decode(b64)
    

For comparison, here's how much each algorithm expands your binary data:

  * base32: 60.0%
  * fake base62: 39.2%
  * realistic base62: ~38%
  * optimal base62: 34.4%
  * base64: 33%

The point of partial-byte transfer encodings like base64 is that they're dead-
simple and run fast. While you _can_ extend it to partial-bit encodings like
base62, you lose all of the advantages… so if the fake base62 isn't good
enough, I'd suggest using something completely different instead.

* * *

To reverse this, reverse all the same steps in reverse order.

Putting it all together, using the fake base62, and using `unicode`/Python 3
strings:

    
    
    plain_bytes = plain_text.encode('utf-8')
    compressed_bytes = zlib.compress(plain_bytes)
    b62_bytes = b62encode(compressed_bytes)
    b62_text = b62_bytes.decode('ascii')
    
    b62_bytes = b62_text.encode('ascii')
    compressed_bytes = b62decode(b62_bytes)
    plain_bytes = zlib.decompress(compressed_bytes)
    plain_text = plain_bytes.decode('utf-8')
    

And that's about as complicated as it can get.

