Raccourciceurs d’URL et nombre de combinaisons possibles

Aujourd’hui un collègue m’a demandé comment fonctionnaient les raccourciceurs d’url tels que bit.ly ou tinyurl et dont une liste quasi-exhaustive est disponible ICI

Effectivement les URL retournées par bit.ly sont du type http://bit.ly/Ux7eFJ soit seulement 6 caractères alphanumériques. On est dès lors en droit de se demander pendant combien de temps il est possible de stocker une URL dans ces conditions car visuellement parlant 6 caractères ça fait peu.

Le principe de fonctionnement d’un raccourciceur d’URL est simple, une base de donnée bien indexée contient les liens URL courtes -> URL longues, puis une page PHP se charge de récupérer la valeur courte passée par l’URL et génère en retour une redirection HTTP HTML ou Javascript vers la page ciblée.

Pour dimensionner le système et générer les URL les plus courtes possibles il faut donc faire un compromis entre le nombre de caractères et le nombre d’URL maximum que l’on souhaite pouvoir gérer. On cherche donc à trouver le nombre de combinaisons possible à partir d’un jeu de caractères donné et du nombre de caractères choisi — Pour le cas de bit.ly nous avons 6 caractères à choisir dans un jeu de 62 caractères ( 26 minuscules + 26 majuscules + 10 chiffres ). Le concept mathématique correspondant à ce problème de logique combinatoire est l’arrangement avec répétition soit comment trouver le nombre de combinaisons possibles où les caractères peuvent être répétés ( tirages avec remise ) et où l’ordre des tirages est significatif ( Ux7eFJ != xUe7JF ). La formule qui permet de résoudre ce problème est extrêmement simple, il s’agit simplement de calculer n^k avec n le nombre de caractères et k le nombre d’éléments du jeu de caractère.

Dans le cas de bit.ly nous obtenons 62^6 = 56 800 235 584 possibilités. On comprend ainsi qu’un faible nombre de caractères suffit à générer un nombre suffisant d’url. Ajoutons à cela les possibilité d’augmenter encore la taille du jeu de caractère en ajoutant les caractères spéciaux — attention ici aux risque d’incompatibilité — en gérant le dédoublonnage — on ne génère pas une nouvelle URL courte si l’URL longue existe déjà en base — en limitant la validité des URL dans le temps ou encore la suppression des plus vielles / moins utilisées des URL lorsque la limite est atteinte.

Exemples pour le jeu alphanumérique ( 62 caractères ) :

62 ^ 2 = 3844 possibilités
62 ^ 3 = 238 328 possibilités
62 ^ 4 = 14 776 336 possibilités
62 ^ 5 = 916 132 832 possibilités
62 ^ 6 = 56 800 235 584 possibilités
62 ^ 7 = 3 521 614 606 208 (3.52 x 10^12) possibilités
62 ^ 8 = 218 340 105 584 896 (2.18 x 10^14) possibilités

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *