Alternatives to traditional algorithms for encoding UUIDS (e.g. Base32, Base62)

Question

We need to convert huge numbers of UUIDS into xml-compatible strings. If we use a Base32 algorithm (which maps each 5 bits to one of 32 characters) this leads to 26 char strings, if we us a Base62 algorithm (which iteratively divides the 128 bit integer by 62 and records the modulus as one of 62 characters) this leads to 22 char strings. While base62 returns shorter strings it is much more cpu-intensive, therefore we are stuck with Base32 (Base64 is not an option because of xml).

Do you know any other types of encoding algorithms that could help us here? Are there variants of Base32-like bit pattern encoding algorithms that could be used with bases that are not powers of 2? Or are there hybrid algorithms which combine approaches of the first with approaches of the second algorithm? We would like to reduce the char strings to less than 26 if possible.

Answer 1

You mentioned 62, which suggests that you are limiting your alphabet to A-Z (capitalised and lowercase) and the digits 0-9. Why not add another couple of XML compatible characters to that list, such as +, ., ~ or ! to bring that number up to 64? You'll be be able to do bit-shifting rather than division, which should make the algorithm as fast as the Base32 one and reduce your string sizes.

Edit: Since the restriction that these characters are also available for other as yet unspecified languages, you might care to escape some of your characters to represent your 64 options. If you use, for example, _ as an escape character you could have _1 and _2 represent options 63 and 64. The statistics mention in the original question suggest that UUIDS are 128-bits, so our Base64 would give us 22 characters if there is no escaping and, where up to 4 items are escaped, keeps within your 26 characters.