Créer votre propre uid de style Tinyurl

J’écris un petit article sur des alternatives aux Guids / UID lisibles par l’homme, par exemple celles utilisées sur TinyURL pour les hachages d’URL (qui sont souvent imprimées dans des magazines, elles doivent donc être courtes).

Le simple uid que je génère est – 6 caractères: une lettre minuscule (az) ou 0-9.

“Selon mes calculs, capitaine”, il s’agit de 6 événements qui s’excluent mutuellement, bien que le calcul de la probabilité d’une collision devienne un peu plus difficile que P (A ou B) = P (A) + P (B). le code ci-dessous, vous pouvez voir que cela fonctionne s’il faut utiliser un chiffre ou une lettre en utilisant 50/50.

Je m’intéresse au taux de collision et si le code ci-dessous est une simulation réaliste du taux de collision anticipé, vous obtiendrez de la génération d’un hachage. En moyenne, je reçois entre 40 et 50 affrontements par million, même si l’on se rend bien compte que l’instrument de contrôle ne serait pas généré un million de fois à la fois, mais probablement seulement 10 à 1000 fois par minute.

Quelle est la probabilité d’un affrontement à chaque fois, et quelqu’un peut-il suggérer une meilleure façon de le faire?

static Random _random = new Random(); public static void main() { // Size of the key, 6 HashSet set = new HashSet(); int clashes = 0; for (int n=0;n < 1000000;n++) { StringBuilder builder = new StringBuilder(); for (int i =0;i  0.5) { builder.Append((char)_random.Next(97,123)); } else { builder.Append(_random.Next(0,9).ToSsortingng()); } } if (set.Contains(builder.ToSsortingng())) { clashes++; Console.WriteLine("clash: (" +n+ ")" +builder.ToSsortingng()); } set.Add(builder.ToSsortingng()); _random.Next(); //Console.Write(builder.ToSsortingng()); } Console.WriteLine("Clashes: " +clashes); Console.ReadLine(); } 

UPDATE: Voici l’article résultant de cette question

J’ai vraiment posé deux questions ici, donc je sortingchais. La réponse que je recherchais était celle de rcar, mais celle de Sklivvz est également celle de la deuxième partie (une alternative). Est-il possible de créer un générateur d’identifiant unique et personnalisé dans une firebase database, ou s’agirait-il du côté client (2 lectures possibles en premier)?

L’idée générale que je cherchais était d’utiliser des identifiants dans des bases de données ou d’autres magasins pouvant être utilisés par téléphone ou sur des supports imprimés, et non par un guide géant de 16 octets.

UPDATE 2: J’ai mis la formule de deux événements mutuellement exclusifs ci-dessus au lieu de 2 événements indépendants (car obtenir un «a» la première fois ne signifie pas que vous ne pouvez pas obtenir un «a» la seconde fois). Aurait dû être P (A et B) = P (A) x P (B)

La probabilité d’une collision avec un ID spécifique est:

 p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6 

qui est autour de 1,7 × 10 ^ -9.

La probabilité d’une collision après la génération de n identifiants est de 1-p ^ n, vous aurez donc environ 0,17% de chances d’une collision pour chaque nouvelle insertion après l’insertion d’un million d’identifiants, environ 1,7% après 10 millions d’identifiants. environ 16% après 100 millions.

1000 ID / minute équivaut à environ 43 millions / mois, ainsi, comme l’a souligné Sklivvz, l’utilisation d’un ID incrémenté constituera probablement une meilleure solution dans ce cas.

MODIFIER:

Pour expliquer le calcul, il lance essentiellement une pièce de monnaie et choisit ensuite un chiffre ou une lettre six fois. Il y a une probabilité de 0,5 que le jeton de la pièce corresponde, puis dans 50% des cas, il y a une chance sur dix d’égaler et 50% sur une chance d’égaliser. Cela se produit 6 fois indépendamment, vous multipliez donc ces probabilités.

Pourquoi voulez-vous utiliser une fonction aléatoire? J’ai toujours supposé que tinyurl utilisait une représentation en base 62 (0-9A-Za-z) d’un Id séquentiel. Pas de conflits et les URL sont toujours aussi courtes que possible.

Vous auriez une table DB comme

 Id URL 1 http://google.com 2 ... ... ... 156 ... ... ... 

et les URL correspondantes seraient:

 http://example.com/1 http://example.com/2 ... http://example.com/2W ... 

Recherchez le paradoxe d’anniversaire , c’est le problème exact que vous rencontrez.

La question qui se pose est la suivante: combien de personnes faut-il réunir dans une pièce pour que vous ayez 50% de chances que deux personnes aient la même date de naissance? La réponse pourrait te surprendre.

Il y a quelque temps, j’ai fait exactement cela et j’ai suivi la façon dont Sklivvz a mentionné. Toute la logique a été développée avec une procédure stockée sur le serveur SQL et quelques UDF (fonctions définies par l’utilisateur). Les étapes étaient les suivantes:

  • dites que vous voulez raccourcir cette URL: Créer votre propre style UID Tinyurl
  • Insérer l’URL dans un tableau
  • Obtenir la valeur @@ identity de la dernière insertion (un identifiant numérique)
  • Transformez l’identifiant en une valeur alphanumérique correspondante, basée sur un “domaine” de lettres et de chiffres (j’ai utilisé cet ensemble: “0123456789abcdefghijklmnopqrstuvwxyz”)
  • Renvoie cette valeur, quelque chose comme ‘cc0’

La conversion a été réalisée à travers quelques UDF très courts.

Deux conversions appelées l’une après l’autre renverraient des valeurs “séquentielles” comme celles-ci:

 select dbo.FX_CONV (123456) -- returns "1f5n" select dbo.FX_CONV (123457) -- returns "1f5o" 

Si vous êtes intéressé, je peux partager le code de la FDU.

Pourquoi ne pas simplement utiliser un algorithme de hachage? et utiliser un hash de l’URL?

Si vous utilisez des nombres aléatoires, vous aurez probablement des conflits parce qu’ils sont indéterminés.

les hachages ne sont probablement pas uniques, mais il y a de bonnes chances que le hachage d’une chaîne soit unique.

Correction

En fait, attendez que vous vouliez qu’ils soient lisibles par l’humain … Si vous les mettez en hexadécimal, ils sont techniquement lisibles par l’humain.

ou vous pouvez utiliser un algorithme qui convertit un hachage en une chaîne lisible par l’homme. si la chaîne lisible par l’homme est une représentation différente du hachage, elle doit également être aussi “unique” que le hachage, c’est-à-dire la base 36 du hachage d’origine.

Je générerais une valeur aléatoire représentative des données que vous allez hachage, puis hachez-la et vérifiez les clahses plutôt que d’essayer de simuler avec des hachages faits manuellement. Cela vous donnera un meilleur indicateur. Et vous aurez plus de hasard parce que vous aurez plus de choses à randomiser (en supposant que vos données soient hachées est plus grande :)).

Si vous utilisez 6 caractères, az et 0-9, le total est de 36 caractères. Le nombre de permutations est donc de 36 ^ 6 ce qui correspond à 2176782336 .. il ne devrait donc s’affronter que 1/2176782336.

de wikipedia :

Lorsque vous souhaitez imprimer moins de caractères, les GUID sont parfois encodés dans une chaîne base64 ou Ascii85. Le GUID codé en Base64 comprend de 22 à 24 caractères (selon le remplissage), par exemple:

 7QDBkvCA1+B9K/U0vrQx1A 7QDBkvCA1+B9K/U0vrQx1A== 

Le codage Ascii85 ne donne que 20 caractères, par exemple:

 5:$Hj:Pf\4RLB9%kU\Lj 

Donc, si vous êtes préoccupé par l’unicité, un GUID codé en base64 vous rapproche un peu de ce que vous voulez, bien que ce ne soit pas 6 caractères.

Il est préférable de commencer par utiliser les octets, puis de les traduire en hexadécimal pour les afficher, plutôt que de travailler directement avec des caractères.