Je vous avais parlé des bases dans l’article sur le binaire. En informatique, on utilise essentiellement la base 10, évidement, mais aussi 2, 8, 16 et 64. Des puissances de 2, quoi.

Cependant, il arrive parfois qu’on ait besoin d’une base personalisée. En effet, une base n’étant qu’une notation, on peut en créer une de toutes pièces. C’est parfois très utile :

• Besoin de limiter au maximum le nombre de caractères pour représenter une donnée. Si la base 64 ne suffit pas, on créera des bases 70, voire plus si on a accès à un charset large.
• On est limité dans les caractères qu’on peut utiliser. Typiquement dans certains formulaires de mots de passe, on a le droit qu’à -_, des lettres et des chiffres.
• On souhaite limiter les caractères à utiliser. Ça m’est arrivé en travaillant sur un système à base de SMS. Les ID devaient éviter de contenir tous les caractères comme 1, l, 0, O, S, 5, Z, 2 car trop faciles à confondre sur un nokia 3310.

Mais la plupart des outils ne permettent pas de choisir la base de représentation des données qu’ils génèrent. Pour cette raison, il peut être pratique d’implémenter une petit convertisseur d’une base à l’autre.

Voici un objet Python qui permet de convertir une string d’une base custom en entier en base 10, et inversement.

# Il est possible de passer de n'importe quelle base à
# une autre directement, mais utiliser la base 10,
# comme pivot, est ce qu'il y a de plus facile 
# à coder
class BaseConverter:
 
   def __init__(self, symboles):
      self.symboles = symboles
      self.sym2val = {l: i for i, l in enumerate(symboles)}
      self.val2sym = dict(enumerate(symboles))
 
   def to_base_10(self, string):
       i = 0
       base = len(self.sym2val)
       # On part de la gauche vers la droite,
       # donc on commence avec les valeurs les plus
       # grosses.
       # Pour chaque symbole, on ajoute la valeur
       # de celui-ci (donnée par la table) et
       # avec facteur lié à sa position.
       for c in string:
           i *= base
           i += self.sym2val[c]
       return i
 
   def from_base_10(self, number):
       """ Convert from a base 10 to the custom base"""
       array = []
       base = len(self.val2sym)
       # Division euclidienne en boucle jusqu'à ce que le
       # reste soit égal à zero.
       while number:
           number, value = divmod(number, base)
           # Le résultat est l'index du symbole.
           # On le place le plus à gauche, chaque
           # symbole ayant une valeur plus grande
           # que le précédent.
           array.insert(0, self.val2sym[value])
 
       # Ne pas oublier le zéro
       return ''.join(array) or self.symboles[0]

Maintenant imaginez la génération d’un UUID qui doit seulement contenir certains caractères ou avoir une certaine taille. Par exemple, votre client vous demande des ID en base 32 de Crockford.

uuid = uuid.uuid4()
print(uid)
## 50ab7fa9-9643-4aad-be84-548405abea08
CROCKFORD_B32 = BaseConverter("0123456789abcdefghjkmnpqrstvwxyz")
print(CROCKFORD_B32.from_base_10(uid.int))
## 2gndztk5j39apvx12mgg2tqtg8

Bon, évidément, pour toutes les bases ordinaires, int(string, base) fait ça très bien.

On peut aller plus loin et faire une seule partie de l’ID dans une base, et l’autre dans une autre base, pour des raisons de lisibilité. Le cas d’école étant les plaques d’immatriculation ou les numéros de vol.

Une fois, on m’a demandé de faire une URL de type :

/ressource/id/

Mais l’id devait être facile à recopier à la main. Le client a opté pour une notation de type “AAA111″, 3 lettres, puis 3 chiffres.

Vu qu’il fallait l’implémenter en Lua embed dans nginx, la solution la plus simple a été adoptée :

location ~ "^/([0-9A-Fa-f]{3}[0-9]{3})$" {
   set $short_id $1;
   content_by_lua '
       local redirect_url = "http://site.com/ressource/" .. string.sub(ngx.var.short_id, -3) + tonumber(string.sub(ngx.var.short_id,0,3), 16 ) * 1000
       return ngx.redirect(redirect_url.."/")
   ';
}

En gros, on prend les 3 premiers caractères, on les traite comme de l’hexa, puis on multiplie par 999, et on additionne les 3 derniers chiffres. Cela convertit le truc en base 10.

L’URL est très lisible, et facile à dicter ou recopier à la main :

http://site.com/ressource/FAC101

Bien entendu, on peut se retrouver avec des chiffres au début puisque c’est de l’hexa, et avoir une URL de type 345823, mais ça a été accepté.

Au maximum on ne peut gérer que 4 millions d’ID. Or le site n’en avait pas accumulé plus de 350 000 en 7 ans, et à moins que le trafic explose soudainement (auquel cas il aura le budget pour me payer pour changer l’algo:)), ça devrait tenir 80 ans.

Je vais sans doute ajouter ce code à Batbelt du coup.

Télécharger le code de l’article