Maze62: a dense and speedy alphanumeric encoding for binary data

http://blog.altudov.com/2011/05/16/maze62-a-dense-and-speedy-alphanumeric-encoding-for-binary-data/

by DenisM • 15 years ago

29 28 15 years ago

blog.altudov.com

jtchang• 15 years ago

Cool stuff. Can you post a few examples of the encoding?

andfarm• 15 years ago

I'm having trouble thinking of any situations where you're free to use any alphanumerics, but you absolutely can't use anything else. The closest thing that comes to mind is DNS, and that's a 36-character set, not 62.

Ascii85 (http://en.wikipedia.org/wiki/Base85) uses a similar concept, but using the majority of the printable ASCII characters. It gets a hard-to-beat 20% expansion on binary data (4 bytes in 5 chars) without requiring bigint math.

deweller• 15 years ago

I'm pretty sure the canonical use case for this would be for including complex binary data in a URL. A URL shortener might be a good example.

hc• 15 years ago

DenisM9• 15 years ago

Another thing people don't talk much about is copy-paste. Double click on an alphanumeric will select the entire thing, whereas other characters might cause selection to end prematurely, and differently so in different text editors.

dsl• 15 years ago

http://en.wikipedia.org/wiki/Base64#Implementations_and_hist...

DenisM9• 15 years ago

You're right on DNS, I was not thinking clearly when I wrote that part. I will fix up the article.

The prime scenario that caused me to think about this problem is indeed URL components, and in particular object identifies for RESTful protocols.

The other thing I was thinking about were cookies values, which I have had problems with in the past.

EDIT: The most annoying part about base64 is that different systems have different restrictions. With Maze62 I won't have to think about which system my data will end up in.

nkurz• 15 years ago

My first impression is that this algorithm is going to be much slower than Base64 due to all the branching. This probably won't be visible in Python, but I don't think there's any way to make it really fly when optimized.

There are probably cases where this is acceptable, but I'm inclined to think that Base32 is a better choice if larger size is acceptable, and that Base64 with domain appropriate characters is better where performance counts.

colomon• 15 years ago

Really depends on what you want to do with it, doesn't it? He mentions character limits in URLs as a motivation, and at reasonable lengths for that I imagine Maze62 in Python will be plenty fast....

andrewcooke3• 15 years ago

why is base62 quadratic?

dfox• 15 years ago

Naive implementation certainly is, as it involves one multiplication (of number whose size depends linearly depends on number of previously processed bytes) for each input byte and one division for each output byte. But on the other hand I have this feeling, that more effective implementation is possible (and actually used by modern compression algorithms like RAR and LZMA).

andrewcooke3• 15 years ago

but couldn't you have a stream algorithm with modular arithmetic?

[edit: i thought i had a good demonstration of this. actually, two. but both were wrong. so it does seem to be non-trivial...]

[edit 2: open stack overflow question: http://stackoverflow.com/questions/3545931/efficient-algorit... ]

DenisM9• 15 years ago

I'm pretty sure it's impossible to do in anything less than square time, but I don't have the prof with me.

Acorn2• 15 years ago

If you don't mind using - and _ then the implementation is very simple. I posted an example in Python and CoffeeScript to SO recently for doing this exact thing.

http://stackoverflow.com/questions/5940416/compress-a-series...

  >>> bin_string = '000111000010101010101000101001110'
  >>> encode(bin_string)
  'hcQOPgd'


  >>> decode(encode(bin_string))
  '000111000010101010101000101001110'

DenisM9• 15 years ago

FYI, it seems to be known as this: http://en.wikipedia.org/wiki/Base64#URL_applications

Acorn2• 15 years ago

Hmm, looking at python's base64.urlsafe_b64encode(s), padding is still used. So it sounds like it doesn't fully implement the "modified Base64 for URL" spec.

Base64 encoding also seems to result in quite long ascii strings compared to what I threw together.

Or is there a way to use Base64 which would give results of a comparable length?

jerf2• 15 years ago

Claiming this is dense, OK. That's just math. But how can you claim this is "speedy" when you have an unpolished Python implementation in hand? You need to bench against best-of-breed Base64 implementations, not some pure-Python comparison you may write up in the future, and for that you're going to need to go at least C, and I wouldn't be surprised down to the assembler. Just stick with "dense" and claim "speedy" when you've got some numbers.

(I suspect you won't beat or even tie Base64, but I'm prepared to accept that you only got within X% of base64 but that X% is worth it in some scenario. And maybe if you get clever enough you can prove me wrong.)

DenisM9• 15 years ago

It's speedy compared to base62.

See, the problem is that Base64 is linear is speed, but has large (non-alphanumeric) charset, while base62 has small (alphanumeric) charset but is quadratic in speed (at least in its straightforward implementation, the only one I was able to find).

Maze62 is the encoding that is both constrained in charset and liner in speed. Hence, the title.

Does it make sense?

jerf2• 15 years ago

OK, that's fair. Thanks.

waterhouse3• 15 years ago

I think this has the drawback that if you want to look up, say, bits n through m, you'd need to process the whole string up to that point. Lookup would be O(n) rather than O(1). Is that a problem? (I don't know, maybe people only use base64-like encoding in places where they'd just read the data in once at the beginning, convert it to a better internal representation, and never touch the base64 version again.)

On the other hand, if it is a problem, how's this idea: Use strings of 129 base-62 digits to represent strings of 128 base-64 digits. I pick 128 because it might be convenient, and 129/128 is close to optimal:

  arc> (* 129 (log 62 64))
  128.01522067331783

Or if decoding 128 digits at a time when you just want a couple is excessive, you could use 17 base-62 digits for 16 base-64 digits (which has a space inefficiency of 1/16th, or 6.25%), or 9 for 8 (inefficiency 12.5%), or whatever.

DenisM9• 15 years ago

Random access was not a priority, yes. In fact it didn't even occur to me, not even for a moment :)

As to your proposed algorithm, yes, it could work. It's discussed in passing a bit earlier in this thread, here's direct link: http://news.ycombinator.com/item?id=2554726

Not sure about comparative space efficiency of this vs Maze64, but we're likely splitting hairs at this point :), it should be very close. Yes it could work. Converting 128 characters from base64 to base62 would cost N^2 time, where N is 128. Not sure if it's a big deal. Just another approach.

waterhouse3• 15 years ago

Hmm, and one could extend this chunking approach to Maze62. Consume 12 bits (aka two base64 integers), but if the resulting number is in the range [62^2=3844 to 64^2-1=4095] or [0 to 64^2-62^2-1=251], then add that extra quotient bit to the next input (from which you'll consume only 11 bits). That would make the worst case only take 12/11ths as long, or 109%, instead of 6/5ths as long, or 120%, as the best case (which would be the same as before).

One could extend it upwards as far as desired (probably approaching log_64(62) worst-case and average-case space compared to base64[1]), though the integer arithmetic would become a pain eventually. 12/11 or maybe 18/17 (105.8%) or 24/23 (104.3%) is probably good enough for most purposes. The relatively hardcore might use 60/59 (101.7%), which x86_64 machines can still do with CPU arithmetic (an integer multiply of two 64-bit integers stores the results in two 64-bit registers, and you can then do an integer divide on that, which stores the quotient and remainder in those registers).

[1] Average case: I analyze it like this. If you encode n base64 integers at a time, then you'll encode 6n bits at a time, but 6n-1 bits if you're unlucky and get a number in the ranges [62^n, 64^n - 1] or [0, 64^n - 62^n - 1]. These two ranges, taken together, make 2 * (64^n - 62^n) numbers out of 64^n possible n-digit base64 numbers. Thus, on average, you encode

  6n - 1 * [2 * (64^n - 62^n)]/64^n
  = 6n - 2 * (1 - (62/64)^n)

bits for every group of n characters, or

  6 - 2/n * (1 - (62/64)^n)

bits per character. (Note that this analysis only applies while 62^n < 64^n < 2 * 62^n, so taking n -> ∞ gives misleading results.) The original Maze62 proposal has n = 1, and this yields 5.9375 bits per character on average, which is pretty good. (Check this: 5 * 4/64 + 6 * 60/64 = 5.9375.) The next few values are:

  1 5.9375
  2 5.9384765625
  3 5.939432779947917
  4 5.940369129180908
  ...
  10 5.945595231334425

  Theoretical limit:
  6 * log_64(62) = 5.954196310386876

So I guess there's really not much to be gained for the average case by increasing n. But someone pointed out that all-0 and all-1 sequences happen frequently in real situations, so it may be worth it anyway.

peterbotond• 15 years ago

recently, i needed to encode/decode similar data, and base64 with a variable 64 chars seemed to work just as good. say, - or / are problem chars, then make another set of 64 chars which would have a comma and a dot or alike and there you go. keep the sets in a table or somehting and use the first 2 chars as indicator which set of 64 to use for that data.

Maze62: a dense and speedy alphanumeric encoding for binary data

Related Stories