How to convert an integer to the shortest url-safe string in Python?

Question

I want the shortest possible way of representing an integer in a URL. For example, 11234 can be shortened to '2be2' using hexadecimal. Since base64 uses is a 64 character encoding, it should be possible to represent an integer in base64 using even less characters than hexadecimal. The problem is I can't figure out the cleanest way to convert an integer to base64 (and back again) using Python.

The base64 module has methods for dealing with bytestrings - so maybe one solution would be to convert an integer to its binary representation as a Python string... but I'm not sure how to do that either.

Answer 1

I'd go the 'encode integer as binary string, then base64 encode that' method you suggest, and I'd do it using struct:

>>> import struct, base64
>>> base64.b64encode(struct.pack('l', 47))
'LwAAAA=='
>>> struct.unpack('l', base64.b64decode(_))
(47,)

Edit again: To strip out the extra 0s on numbers that are too small to need full 32-bit precision, try this:

def pad(str, l=4):
    while len(str) < l:
        str = '\x00' + str
    return str

>>> base64.b64encode(struct.pack('!l', 47).replace('\x00', ''))
'Lw=='
>>> struct.unpack('!l', pad(base64.b64decode('Lw==')))
(47,)

Answer 2

Base64 takes 4 bytes/characters to encode 3 bytes and can only encode multiples of 3 bytes (and adds padding otherwise).

So representing 4 bytes (your average int) in Base64 would take 8 bytes. Encoding the same 4 bytes in hex would also take 8 bytes. So you wouldn't gain anything for a single int.

Answer 3

If you are looking for a way to shorten the integer representation using base64, I think you need to look elsewhere. When you encode something with base64 it doesn't get shorter, in fact it gets longer.

E.g. 11234 encoded with base64 would yield MTEyMzQ=

When using base64 you have overlooked the fact that you are not converting just the digits (0-9) to a 64 character encoding. You are converting 3 bytes into 4 bytes so you are guaranteed your base64 encoded string would be 33.33% longer.

Answer 4

You don't want base64 encoding, you want to represent a base 10 numeral in numeral base X.

If you want your base 10 numeral represented in the 26 letters available you could use: http://en.wikipedia.org/wiki/Hexavigesimal. (You can extend that example for a much larger base by using all the legal url characters)

You should atleast be able to get base 38 (26 letters, 10 numbers, +, _)

Answer 5

The easy bit is converting the byte string to web-safe base64:

import base64
output = base64.urlsafe_b64encode(s)

The tricky bit is the first step - convert the integer to a byte string.

If your integers are small you're better off hex encoding them - see saua

Otherwise (hacky recursive version):

def convertIntToByteString(i):
    if i == 0:
        return ""
    else:
        return convertIntToByteString(i >> 8) + chr(i & 255)

Answer 6

This answer is similar in spirit to Douglas Leeder's, with the following changes:

• It doesn't use actual Base64, so there's no padding characters

• Instead of converting the number first to a byte-string (base 256), it converts it directly to base 64, which has the advantage of letting you represent negative numbers using a sign character.

  import string
  ALPHABET = string.ascii_uppercase + string.ascii_lowercase + \
             string.digits + '-_'
  ALPHABET_REVERSE = dict((c, i) for (i, c) in enumerate(ALPHABET))
  BASE = len(ALPHABET)
  SIGN_CHARACTER = '$'
  
  
  def num_encode(n):
      if n < 0:
          return SIGN_CHARACTER + num_encode(-n):
      s = []
      while True:
          n, r = divmod(n, BASE)
          s.append(ALPHABET[r])
          if n == 0: break
      return ''.join(reversed(s))
  
  
  def num_decode(s):
      if s[0] == SIGN_CHARACTER:
          return -num_decode(s[1:])
      n = 0
      for c in s:
          n = n * BASE + ALPHABET_REVERSE[c]
      return n
  

---

    >>> num_encode(0)
    'A'
    >>> num_encode(64)
    'BA'
    >>> num_encode(-(64**5-1))
    '$_____'

---

A few side notes:

• You could (marginally) increase the human-readibility of the base-64 numbers by putting string.digits first in the alphabet (and making the sign character '-'); I chose the order that I did based on Python's urlsafe_b64encode.
• If you're encoding a lot of negative numbers, you could increase the efficiency by using a sign bit or one's/two's complement instead of a sign character.
• You should be able to easily adapt this code to different bases by changing the alphabet, either to restrict it to only alphanumeric characters or to add additional "URL-safe" characters.
• I would recommend against using a representation other than base 10 in URIs in most cases—it adds complexity and makes debugging harder without significant savings compared to the overhead of HTTP—unless you're going for something TinyURL-esque.

Answer 7

a little hacky, but it works:

def b64num(num_to_encode):
  h = hex(num_to_encode)[2:]     # hex(n) returns 0xhh, strip off the 0x
  h = len(h) & 1 and '0'+h or h  # if odd number of digits, prepend '0' which hex codec requires
  return h.decode('hex').encode('base64')

you could replace the call to .encode('base64') with something in the base64 module, such as urlsafe_b64encode()

Answer 8

To encode n:

data = ''
while n > 0:
    data = chr(n & 255) + data
    n = n >> 8
encoded = base64.urlsafe_b64encode(data).rstrip('=')

To decode s:

data = base64.urlsafe_b64decode(s + '===')
decoded = 0
while len(data) > 0:
    decoded = (decoded << 8) | ord(data[0])
    data = data[1:]

In the same spirit as other for some “optimal” encoding, you can use 73 characters according to RFC 1738 (actually 74 if you count “+” as usable):

alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_`\"!$'()*,-."
encoded = ''
while n > 0:
    n, r = divmod(n, len(alphabet))
    encoded = alphabet[r] + encoded

and the decoding:

decoded = 0
while len(s) > 0:
    decoded = decoded * len(alphabet) + alphabet.find(s[0])
    s = s[1:]

Answer 9

You probably do not want real base64 encoding for this - it will add padding etc, potentially even resulting in larger strings than hex would for small numbers. If there's no need to interoperate with anything else, just use your own encoding. Eg. here's a function that will encode to any base (note the digits are actually stored least-significant first to avoid extra reverse() calls:

def make_encoder(baseString):
    size = len(baseString)
    d = dict((ch, i) for (i, ch) in enumerate(baseString)) # Map from char -> value
    if len(d) != size:
        raise Exception("Duplicate characters in encoding string")

    def encode(x):
        if x==0: return baseString[0]  # Only needed if don't want '' for 0
        l=[]
        while x>0:
            l.append(baseString[x % size])
            x //= size
        return ''.join(l)

    def decode(s):
        return sum(d[ch] * size**i for (i,ch) in enumerate(s))

    return encode, decode

# Base 64 version:
encode,decode = make_encoder("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/")

assert decode(encode(435346456456)) == 435346456456

This has the advantage that you can use whatever base you want, just by adding appropriate characters to the encoder's base string.

Note that the gains for larger bases are not going to be that big however. base 64 will only reduce the size to 2/3rds of base 16 (6 bits/char instead of 4). Each doubling only adds one more bit per character. Unless you've a real need to compact things, just using hex will probably be the simplest and fastest option.