Extremely compact UUID (using all alphanumeric characters)

user_1277576 0
Viewed 1236

I need an extremely compact UUID, the shorter the better.

To that end, I wrote:

    public String getBase36UIID() {
        // More compact version of UUID
        String strUUID = UUID.randomUUID().toString().replace("-", "");
        return new BigInteger(strUUID, 16).toString(36);
    }

By executing this code, I get, for example:

5luppaye6086d5wp4fqyz57xb

That's good, but it's not the best. Base 36 uses all numeric digits and lowercase letters, but does not use uppercase letters.

If it were possible to use uppercase letters as separate digits from lowercase letters, it would be possible to theorize a numerical base 62, composed of these digits:

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

I could theorize numerical bases also using accented characters such as "è" or "é", or special characters such as "$" or "!", further increasing the number of digits available.

The use of these accented or special characters, however, may cause me problems, so for the moment I prefer not to consider them.

After all these premises, how can I convert the BigInteger representing my UUID into the base 62 above theorized, in order to make it even more compact? Thanks

I have already verified that a code like the following is not usable, because every base over 36 is treated as base 10:

return new BigInteger(strUUID, 16).toString(62);

After all, in mathematics there is no base 62 as I imagined it, but I suppose that in Java it can be created.

math java
3 Answers

The general algorithm for converting a number to any base is based on division with remainder.

You start by dividing the number by the base. The remainder gives you the last digit of the number - you map it to a symbol. If the quotient is nonzero, you divide it by the base. The remainder gives you the second to last digit. And you repeat the process with the quotient.

In Java, with BigInteger:

String toBase62(BigInteger number) {
    String symbols = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    BigInteger base = BigInteger.valueOf(symbols.length());

    StringBuilder result = new StringBuilder();
    do {
        BigInteger[] quotientAndRemainder = number.divideAndRemainder(base);
        number = quotientAndRemainder[0];
        result.append(symbols.charAt(quotientAndRemainder[1].intValue()));
    } while (number.compareTo(BigInteger.ZERO) > 0);
    
    return result.reverse().toString();
}

Do you need the identifier to be a UUID though? Couldn't it be just any random sequence of letters and numbers? If that's acceptable, you don't have to deal with number base conversions.

String randomString(int length) {
    String symbols = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    Random rnd = new Random();
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < length; i++) {
        str.append(symbols.charAt(rnd.nextInt(symbols.length())));
    }
    return str.toString();
}
user_3187580

This should not be difficult. Converting a number to a string is a basic programming task. The fact that you're using base 62 makes no difference.

Decide how many characters you're willing to use, and then convert your large number to that base. Map each "digit" onto one of the characters.

Pseudocode:

 b = the base (say, 62)
 valid_chars = an array of 'b' characters
 u = the uuid
 while u != 0:
    digit = u % b;
    char = valid_chars[digit];
    u = u / b;

This produces the digits right-to-left but you should get the idea.

user_137841170

Main idea is the same as previous posts, but the implementation have some differences.
Also note that if wanted different occurrence probability for each chars this can be adjusted also.(mainly add a character more time on a data structure and change his probability)

Here is fair-probability for each chars (equals, 1/62)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RCode {
    String symbols = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public static void main(String[] args)
    {
        RCode r = new RCode();
        System.out.println("symbols="+r.symbols.length());
        System.out.println("code_10(+1)="+r.generate(10));
        System.out.println("code_70(+2)="+r.generate(70));
        //System.out.println("code_124(+3)="+r.generate(124));
    }
    
    
    public String generate(int length)
    {
        int num = length/symbols.length()+1;
        List<Character> list = new ArrayList<Character>();
        for(int i=0; i<symbols.length(); i++)
        {
            //if needed to change probability of char occurrence then adapt here
            for(int j=0;j<=num;j++)
            {
                list.add(symbols.charAt(i));
            }
        }
        //basically is the same as random
        Collections.shuffle(list);
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<length; i++)
        {
            sb.append(list.get(i));
        }
        return sb.toString();
    }
}

Output:

symbols=62
//each char is added once(+1)
code_10(+1)=hFW9ZFEAeU
code_70(+2)=hrHQCEdQ3F28apcJPnfjAaOu55Xso12xabkJ7MrU97U0HYkYhWwGEqVAiLOp3X3QSuq6qp

Note: Algorithm have a defect, just try to figured out why the sequence will be never generate on 10 (aaaaaaaaaa). Easy to fix ... but i was focused on the idea.
Now, as it is, basically is generating up to num each character. (random and maybe for someone will be useful the output)

user_109392040
Related