Cherche algorithme de compression pour URL

[Orbite]

Je cherche un algorithme de compression pour réduire la taille des URL. J'aimerais inclure un tel algorithme dans un script de redirection à la manière de http://www.tinyurl.com/ .

Je pensais utiliser un encodage Huffman sauf qu'il n'est pas du tout évident que je puisse obtenir un taux de compression intéressant pour le cas bien particulier des adresses Web. Il faut absolument que la chaîne compressé s'exprime en chiffres et en lettres, sans caractères spéciaux.

Aucun résultats concluants avec les recherches Google « lossless text compression », « algorithm for shortening urls », etc.

[Benoit]

Je vois plusieurs solutions
- une clé de hashing (md5) de l'URL -- mais ça te fait toujours 32 caractères c'est peut-être encore trop long?
- quelque chose basé sur un timestamp du moment où a été faite la requête ... que tu peux raccourcir en passant en hexadécimal, voire en base 36 avec tous les chiffres et toutes les lettres.

Ces deux trucs te donneront une chaine de chiffres et lettres de longueur relativement fixe. Dans les deux cas tu dois stocker quelque part la correspondance entre la chaine générée et l'URL (dans une base de données ou un fichier) mais je pense que même chez tinyurl c'est comme ça qu'ils font.

[Orbite]

Merci, mais je pensais plutôt à un arbre binaire du genre :

Code : Tout sélectionner

          /\
http://www. \ 
            /\ 
     .com/    \
              /\
          .html \
                /\
            [a-Z]  ...

exemple :  http://www.google.com/

http://www. = 00
g = 1110001
o = 1110001
o = 1110111
g = 1110001
l = 1111011
e = 1110101
.com/ = 01

-> 00.1110001.1110001.1110001.1110001.111101.111101.01
-> 00111000.11110001.11100011.110001111.10111110.101
-> S.R.Q.G.D.d
-> SRQGDd

Je ne veux pas créer une banque de liens. Je veux réduire la taille du URL. Le URL comprimé doit contenir la totalité de l'information.

[Benoit]

Tu fais beaucoup trop d'hypothèses sur l'aspect de ton URL. Qu'est-ce que tu fais si

• C'est une URL pour un autre protocole (ftp://, irc://, mailto:, ...)
• C'est un domaine de pays. Il y a beaucoup plus de 100 extensions si tu comptes tous les pays (.fr, .be, .ch, .uk (sans parler des .co.uk, .ac.be, ...) + .com, .info, .net, .biz, .name, ...)
• C'est dans un sous-répertoire (je te fais remarquer que dans ton exemple, seul les partie "http://www" et ".com" sont compressées, le gain se réduit très vite)
• Ca ne commence pas par www mais par autre chose ... encore une fois plus de 100 possibilités (membres.lycos.fr, geckozone.tuxfamily.org, fr.openoffice.org, users.pandora.be, ...)
• C'est un langage de script que tu ne connais pas (.cgi, .asp, .jsp, .php[3-4-5], .cfm, .dll, ...)
• Il faut passer des variables (un post dans un forum)
• Il y a une cible dans la page (#target)
• ...

De toute façon, c'est ton serveur qui devra faire la transformation inverse chaine générée => URL complète. Alors quel que soit le moyen que tu utilises pour générer ta clé unique, il est beaucoup plus simple de récupérer l'URL via un tableau associatif (au sens large). Et une base de données ça fonctionne exactement comme ton arbre binaire, c'est juste que ce n'est pas toi qui dois t'en occuper.

[Orbite]

Tu fais beaucoup trop d'hypothèses sur l'aspect de ton URL

Absolument pas. Je connais exactement le domaine d'application puisque c'est moi qui l'ai défini.

C'est une URL pour un autre protocole (ftp://, irc://, mailto:, ...)

C'est moi qui décide. Je n'ai jamais eu l'intention d'utiliser un autre protocole que le HTTP.

Il faut passer des variables (un post dans un forum)

Ce n'est pas l'usage que j'en fais.

.cgi, .asp, .jsp, .php, .com, .info, .net, .biz, .name, #target, ...

Ils sont encodé de la même façon que « google » dans mon exemple. L'idée est de bénéficier d'un gain important par la réduction des termes les plus fréquents.

il est beaucoup plus simple de récupérer l'URL via un tableau associatif

Il est encore plus facile de ne rien faire. Mon objectif n'est pas la facilité. Je cherche un algorithme de compression sans perte qui puisse s'appliquer à un URL. Merci quand même pour les suggestions.

[Nucleos]

et les formats de compression comme gzip accessibles via php, y as-tu pensé ?

[Orbite]

Oui, sauf qu'ils sont très facile à battre dans ce contexte très spécialisé. De plus, ils opèrent mieux sur des données brutes que du texte.

[Invité]

Ce n'est qu'une impression, mais je pense plutôt que tiny utilise un système d'id. http://www.tinyurl.com/nom_de_l_id ! Je ne pense pas qu'il y est la moindre compression dans ces urls, mais bon .

AllanTK

[Orbite]

Assurément, TinyUrl utilise un banque de liens indexée. C'était seulement un exemple pour faire comprendre l'allure de ce je cherche.

Enfin, merci pour toutes vos contributions. J'ai trouvé une piste, le code source de http://entries.the5k.org/367/index.html

[skonk]

wha effectivement c terrible cette methode de compression decompression en javascript