Selecting base-32 alphabet
For a project of mine I needed a base 32 encoding. Why base-32? Well, I wanted my encoding to have a few nice properties.
Firstly, I wanted my encoding to be case insensitive. If I stick to the letters and numbers, that gives me a maximum of 36 characters to use. Nearest power of 2 value is thus 25. This would allow me to use simple bit shifting to encode value, instead of dealing with big integers.
The first alphabet that fits this requirement is one described in RFC4648.
| 00000 | A | 01000 | I | 10000 | Q | 11000 | Y | |||
| 00001 | B | 01001 | J | 10001 | R | 11001 | Z | |||
| 00010 | C | 01010 | K | 10010 | S | 11010 | 2 | |||
| 00011 | D | 01011 | L | 10011 | T | 11011 | 3 | |||
| 00100 | E | 01100 | M | 10100 | U | 11100 | 4 | |||
| 00101 | F | 01101 | N | 10101 | V | 11101 | 5 | |||
| 00110 | G | 01110 | O | 10110 | W | 11110 | 6 | |||
| 00111 | H | 01111 | P | 10111 | X | 11111 | 7 |
And here my second desired property comes in play. I wanted my encoded value to retain lexicographic order of underlying data. I short, base-32 encoding of data should sort the same as underlying binary data would. And this is not what the default base-32 alphabet does. However, the same RFC4648 does specify alternative extended hex alphabet.
| 00000 | 0 | 01000 | 8 | 10000 | G | 11000 | O | |||
| 00001 | 1 | 01001 | 9 | 10001 | H | 11001 | P | |||
| 00010 | 2 | 01010 | A | 10010 | I | 11010 | Q | |||
| 00011 | 3 | 01011 | B | 10011 | J | 11011 | R | |||
| 00100 | 4 | 01100 | C | 10100 | K | 11100 | S | |||
| 00101 | 5 | 01101 | D | 10101 | L | 11101 | T | |||
| 00110 | 6 | 01110 | E | 10110 | M | 11110 | U | |||
| 00111 | 7 | 01111 | F | 10111 | N | 11111 | V |
And this encoding was probably good enough. But, this alphabet has one subtle issue when printed out. Depending on the font, 1, I, and l can be easily mistaken for one another. Same as 0 and O.
Thus, I needed to kick some of those characters out. And the probably best implementation for such requirement already exists. And GPS lovers might already know it - Geohash.
| 00000 | 0 | 01000 | 8 | 10000 | H | 11000 | S | |||
| 00001 | 1 | 01001 | 9 | 10001 | J | 11001 | T | |||
| 00010 | 2 | 01010 | B | 10010 | K | 11010 | U | |||
| 00011 | 3 | 01011 | C | 10011 | M | 11011 | V | |||
| 00100 | 4 | 01100 | D | 10100 | N | 11100 | W | |||
| 00101 | 5 | 01101 | E | 10101 | P | 11101 | X | |||
| 00110 | 6 | 01110 | F | 10110 | Q | 11110 | Y | |||
| 00111 | 7 | 01111 | G | 10111 | R | 11111 | Z |
Here we kick out I, l, O and A. This is actually the system I decided to use for Id26 output in my Uuid7 project. It was the best “standard” alphabet that fit my requirements.
However, I think I missed a good chance to bring my own alphabet to the game. Out of 5 problematic characters, I can remove 4. After giving it some thought and going over multiple fonts, I’ve settled on removing I, l, 0, and O. These characters looked the most similar to my eyes and thus had to go. The resulting alphabet is in table below.
| 00000 | 1 | 01000 | 9 | 10000 | H | 11000 | S | |||
| 00001 | 2 | 01001 | A | 10001 | J | 11001 | T | |||
| 00010 | 3 | 01010 | B | 10010 | K | 11010 | U | |||
| 00011 | 4 | 01011 | C | 10011 | M | 11011 | V | |||
| 00100 | 5 | 01100 | D | 10100 | N | 11100 | W | |||
| 00101 | 6 | 01101 | E | 10101 | P | 11101 | X | |||
| 00110 | 7 | 01110 | F | 10110 | Q | 11110 | Y | |||
| 00111 | 8 | 01111 | G | 10111 | R | 11111 | Z |
Now, am I overthinking it? Probably. But there is a reason why there are so many base-32 alphabets around - everybody got their itch to scratch.
PS: For curious, here are the most common base-32 alphabets.
| Base32 | ABCDEFGHIJKLMNOPQRSTUVWXYZ234567 |
| Base32E | 0123456789ABCDEFGHIJKLMNOPQRSTUV |
| Crockford | 0123456789ABCDEFGHJKMNPQRSTVWXYZ |
| Geohash | 0123456789BCDEFGHJKMNPQRSTUVWXYZ |
| Nintendo | 0123456789BCDFGHJKLMNPQRSTVWXYZ* |
| Turing | /E@A:SIU¼DRJNFCKTZLWHYPQOBG"MXV£ |
| Word-safe | 23456789CFGHJMPQRVWXCFGHJMPQRVWX |
| Z-base-32 | YBNDRFG8EJKMCPQXOT1UWISZA345H769 |
