5 ms·

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)

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.

DenisM 15y 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 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.
- waterhouse 15y 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.
  - DenisM 15y ago
    That's a great idea, and it will probably speed up possible native implementations (though likely at the expense of scripting languages). To deal with large runs of identical numbers (e.g. all zeroes) someone suggested in my blog comments to XOR the input array with a result of a chosen pseudo-random function. This will bring any dataset into the realm of average (5.9375) except for the dataset that is specifically targeting the chosen pseudo-random function. :)

DenisM 15y 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 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.

waterhouse 15y 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.
- DenisM 15y ago
  That's a great idea, and it will probably speed up possible native implementations (though likely at the expense of scripting languages). To deal with large runs of identical numbers (e.g. all zeroes) someone suggested in my blog comments to XOR the input array with a result of a chosen pseudo-random function. This will bring any dataset into the realm of average (5.9375) except for the dataset that is specifically targeting the chosen pseudo-random function. :)