De quoi parle-t-on ici ?
Je suis actuellement en train de développer une application Adobe Air comme certains le savent, et j'ai besoin (ou plutôt envie) de créer moi aussi mon propre "raccourcisseur" d'url.
Apparemment la plupart des services du genre se base sur une base de données, l'objectif pour être concurrentiel est donc d'effectuer le moins de requête possible afin que le service soit le plus rapide. Après avoir soumis à la suite plusieurs urls différentes à minurl.fr, j'ai obtenu cette suite d'url :
- http://minurl.fr/12
- http://minurl.fr/13
- http://minurl.fr/14
- http://minurl.fr/15
- http://minurl.fr/16
- http://minurl.fr/17
Que peut-on en conclure ?
- A chaque nouvelle url qui n'existe pas dans la base de données
- On créé un identifiant, supérieur au dernier identifiant, que l'ont lie à l'url (ou plutôt un équivalent compressé de l'url).
- Donc dans la table de notre base de données on à pour le moment les champs suivant :
- id varchar(10) (primary) : identifiant pour l'url qui sera afficher
- url varchar(40) (index) : champs pour l'url compressée
- Il est préférable que le contenu de ce champs soit compressé si l'on ne veut pas une énorme base de données mais cela n'est pas obligatoire !
- Dans cette exemple d'algorithme nous ne nous soucierons pas de la compression de l'url.
- Si le script reçoit un identifiant
- Chercher dans la base de données si l'id existe
- Il existe : on retourne l'url (il faudra la décompresser si on l'a compressée)
- On redirige vers cette url.
- Il n'existe pas : on informe l'utilisateur.
- Si le script ne reçoit pas d'identifiant
- On propose le formulaire d'ajout
Maintenant, on répète l'expérience avec Tinyurl, on à donc cette suite d'url :
- http://tinyurl.com/6l74df
- http://tinyurl.com/6d8r75
- http://tinyurl.com/5o5c7d
- http://tinyurl.com/5tfegj
- http://tinyurl.com/63kjqo
- http://tinyurl.com/6ys8ym
Que peut-on en conclure ?
- Il semble que Tinyurl utilise un système de création d'ID aléatoire, ce qui empêche toute prédiction sur le prochain ID à venir.
- Chaque nouvelle ID créé est de la forme 5XXXXX ou 6XXXXX (d'après mes tests). Il est donc possible que les ID de la forme 4XXXXX, 3XXXXX, 2XXXXX est déjà été tous utilisé.
- Il est donc fort probable que l'algorithme de Tinyurl, répartisse les ID fraichement créé sur deux plages qui n'ont pas encore été complètement remplie (dans notre cas 5XXXXX et 6XXXXX). Nous pouvons émettre cette hypothèse vu que les plages [4XXXXX, 3XXXXX] et [2XXXXX, 1XXXXX] on déjà été rempli.
- Exemple, si l'on entre http://google.com l'ID de TinyUrl est http://tinyurl.com/1c2 : notre théorie est donc sans doute valide car cette adresse à été entrée dans les débuts de Tinyurl (par une personne qui souhaitait tester le service) et qu'au lancement l'algorithme devait travailler sur une plage [2XXXXX, 1XXXXX].
- L'algorithme semble donc bien plus complexe que celui élaboré plus haut.
Nous avons donc une base d'algorithme pour créer notre service, bien sur, il est extrêmement conseillé de l'améliorer mais il reste néanmoins fonctionnel et c'est ce que l'on souhaite d'un algorithme n'est-ce pas ?
Message plus récent
Accueil
8 commentaires:
Ajoutez un commentaire via Google Friend Connect... ...ou en utilisant les commentaires standards sous Blogger...Hello GeekFG =)
J'ai créé http://minurl.fr, donc je vais corriger certains points de ta rétro ingénierie :
- Nous n'utilisons pas de compression d'identifiant d'url, mais un changement de base.
- Tu n'as pas testé ni le mode compteur, ni la personnalisation d'url. Ce sont des procédés qui permettent de rendre son lien unique.
- La base de données que tu as décrite ne suivra pas longtemps, une URL peut mesure jusqu'à 2k caractères. Quant à un champ ID en VARCHAR, bof bof ;)
lundi, 07 juillet, 2008
DarklgAlors, tout d'abord je sais bien que c'est de toi, et tu m'avais déjà informé que tu utilisais un changement de base.
- Je n'ai pas testé le mode compteur, ni personnalisation d'url, car, il ne faut pas l'oublier, l'objectif de ce post est de donner une base de réflection, et non de donner un exemple complet avec son lot d'option.
- Le varchar est dans cette logique, je donne une base d'analyse, et non une base complête avec une optimisation pour chaque champs etc... J'espère que tu me comprendras :).
lundi, 07 juillet, 2008
François-Guillaume RibreauAttention, je ne critique pas ton analyse, loin de là ;)
Tu as cerné l'algorithme principal, mais il y a quelques subtilités qui font que la description que tu en fais ne pourrait pas tourner efficacement.
Bien entendu, on ne va pas tout révéler ;)
Si t'as besoin d'une précision ( ou plus ) sur le fonctionnement de http://minurl.fr, n'hésite pas ;)
lundi, 07 juillet, 2008
DarklgVoila, c'est justement de cette subtilité que je te parlais. Je ne veux pas donner une réponse toute faite, ce n'est vraiment pas mon but, et cet article ne décrit pas comment fonctionne minurl.
Je me base sur quelques exemples simple de minurl, pour trouver un bout de réponse à la question "comment fonctionne les Tinyurl-like", rien de plus rien de moins :). Je donne donc un bout de réponse et laisse aux quelques lecteurs programmeurs le soin de continuer sur cette voie, d'améliorer et d'optimiser :).
Je me garde bien de donner toutes les "subtilités" c'est justement ce que je souhaite, que ceux que le veulent puisse découvrir eux même la façon de trouver ces subtilités là.
lundi, 07 juillet, 2008
François-Guillaume RibreauHello,
Je me permet de poster ma méthode, puisque j'ai créé un rapidement système similaire et plutot simple :
- Création d'un répertoire aléatoire
- Ecriture d'un .htaccess de redirection dans ce répertoire
Un répertoire = Une redirection
Simple et efficace.
jeudi, 21 août, 2008
Ju@ju en effet la méthode est simple ! Très simple même, pas de base de donnée, la rapidité avant tout.
Par contre si l'on souhaite ajouter un système de miniature, de compteur de visite etc... il faudra plus se tourner vers une méthode un peu plus "complexe". Cependant très belle réflection de votre part je n'y avait pas penser.
jeudi, 21 août, 2008
François-Guillaume Ribreauca ne pose pas un problème de créer jusqu'à 100 000 dossiers, genre quand tu vas sur ton ftp ...
(je pense au répertoire sous windows qui rament des qu'il contiennent quelques milliers de fichier/répertoire => ca m'est arrivé avec une fausse manip de remplir un répertoire)
samedi, 03 janvier, 2009
Antoine"ca ne pose pas un problème de créer jusqu'à 100 000 dossiers, genre quand tu vas sur ton ftp ...
(je pense au répertoire sous windows qui rament des qu'il contiennent quelques milliers de fichier/répertoire => ca m'est arrivé avec une fausse manip de remplir un répertoire) "
Oui tout à fait d'accord, cette solution n'est à prendre en compte que pour de petites applications. En NTFS la limite (si je me souviens bien) se trouve à 2^32 fichier/répertoire par répertoire, quasi-impossible à atteindre donc :)
samedi, 03 janvier, 2009
François-Guillaume RibreauJe veux participer à la discussion !
Soyez le premier à relayer l'information !
Me linker