CODEWITHSUNDEEP
javascala
Wiz
Wiz

Reputation: 4865

Represent long in least amount of characters

I need to represent both very large and small numbers in the shortest string possible. The numbers are unsigned. I have tried just straight Base64 encode, but for some smaller numbers, the encoded string is longer than just storing the number as a string. What would be the best way to most optimally store a very large or short number in the shortest string possible with it being URL safe?

Upvotes: 3

Views: 2832

Answers (3)

Boann
Boann

Reputation: 50010

I have tried just straight Base64 encode, but for some smaller numbers, the encoded string is longer than just storing the number as a string

Base64 encoding of binary byte data will make it longer, by about a third. It is not supposed to make it shorter, but to allow safe transport of binary data in formats that are not binary safe.

However, base 64 is more compact than decimal representation of a number (or of byte data), even if it is less compact than base 256 (the raw byte data). Encoding your numbers in base 64 directly will make them more compact than decimal. This will do it:

private static final String base64Chars =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

static String encodeNumber(long x) {
    char[] buf = new char[11];
    int p = buf.length;
    do {
        buf[--p] = base64Chars.charAt((int)(x % 64));
        x /= 64;
    } while (x != 0);
    return new String(buf, p, buf.length - p);
}

static long decodeNumber(String s) {
    long x = 0;
    for (char c : s.toCharArray()) {
        int charValue = base64Chars.indexOf(c);
        if (charValue == -1) throw new NumberFormatException(s);
        x *= 64;
        x += charValue;
    }
    return x;
}

Using this encoding scheme, Long.MAX_VALUE will be the string H__________, which is 11 characters long, compared to its decimal representation 9223372036854775807 which is 19 characters long. Numbers up to about 16 million will fit in a mere 4 characters. That's about as short as you'll get it. (Technically there are two other characters which do not need to be encoded in URLs: . and ~. You can incorporate those to get base 66, which would be a smidgin shorter for some numbers, although that seems a bit pedantic.)

Upvotes: 4

Stephen C
Stephen C

Reputation: 718678

Assuming that you don't do any compression, and that you restrict yourself to URL safe characters, then the following procedure will give you the most compact encoding possible.

  1. Make a list of all URL safe characters
  2. Count them. Suppose you have N.
  3. Represent your number in base N, representing 0 by the first character, 1 by the 2nd and so on.

So, what about compression ...

If you assume that the numbers you are representing are uniformly distributed across their range, then there is no real opportunity for compression.

Otherwise, there is potential for compression. If you can reduce the size of the common numbers then you can typically achieve a saving by compression. This is how Huffman encoding works.

But the downside is that compression at this level is not perfect across the range of numbers. It reduces the size of some numbers, but it inevitably increases the size of others.

So what does this mean for your use-case?

I think it means that you are looking at the problem the wrong way. You should not be aiming for a minimal encoded size for every number. You should be aiming to minimize the size on average ... averaged over the actual distribution of your numbers.

Upvotes: 1

xpa1492
xpa1492

Reputation: 1973

To extend on Stephen C's answer, here is a piece of code to convert to base 62 (but you can increase this by adding more characters to the digits String (just pick what characters are valid for you):

public static String toString(long n) {
   String digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
   int base = digits.length();
   String s = "";
   while (n > 0) {
      long d = n % base;
      s = digits.charAt(d) + s;
      n = n / base;
   }
   return s;
}

This will never result in the string representation being longer than the digit one.

Upvotes: 2

Related Questions