Comment créer un raccourcisseur d'URL ?

Question

Je veux créer un service de raccourcissement d'URL où vous pouvez écrire une longue URL dans un champ de saisie et le service raccourcit l'URL en " http://www.example.org/abcdef ".

Au lieu de " abcdef "il peut y avoir n'importe quelle autre chaîne de six caractères contenant a-z, A-Z and 0-9 . Cela fait 56~57 milliards de chaînes possibles.

Mon approche :

J'ai une table de base de données avec trois colonnes :

1. id, entier, auto-incrémenté
2. long, string, l'URL longue que l'utilisateur a saisie
3. short, string, l'URL raccourcie (ou juste les six caractères)

J'insérerais ensuite l'URL longue dans le tableau. Je sélectionnerais ensuite la valeur d'auto-incrémentation pour " id "et construire un hachage de celui-ci. Ce hachage doit ensuite être inséré comme " short ". Mais quel type de hachage dois-je construire ? Les algorithmes de hachage comme MD5 créent des chaînes trop longues. Je n'utilise pas ces algorithmes. Un algorithme construit par moi-même fonctionnera aussi.

Mon idée :

Pour " http://www.google.de/ " J'obtiens l'identifiant auto-incrémenté 239472 . Ensuite, je procède aux étapes suivantes :

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

Cela pourrait être répété jusqu'à ce que le nombre ne soit plus divisible. Pensez-vous que c'est une bonne approche ? Avez-vous une meilleure idée ?

_{<em>En raison de l'intérêt constant pour ce sujet, j'ai <a href="https://github.com/delight-im/ShortURL" rel="noreferrer">a publié une solution efficace pour GitHub </a>avec des mises en œuvre pour <a href="https://github.com/delight-im/ShortURL/blob/master/JavaScript/ShortURL.js" rel="noreferrer">JavaScript </a>, <a href="https://github.com/delight-im/ShortURL/blob/master/PHP/ShortURL.php" rel="noreferrer">PHP </a>, <a href="https://github.com/delight-im/ShortURL/blob/master/Python/shorturl.py" rel="noreferrer">Python </a>et <a href="https://github.com/delight-im/ShortURL/blob/master/Java/ShortURL.java" rel="noreferrer">Java </a>. Ajoutez vos solutions si vous le souhaitez :)</em>}

Answer 1

Je continuerais votre approche "convertir le nombre en chaîne". Cependant, vous vous rendrez compte que l'algorithme que vous proposez échoue si votre ID est un premier et supérieur à 52 .

Contexte théorique

Vous avez besoin d'un Fonction bijective f . Ceci est nécessaire pour pouvoir trouver une fonction inverse g('abc') = 123 pour votre f(123) = "abc fonction. Cela signifie :

• Il ne doit pas y avoir x1, x2 (avec x1 x2) qui fera f(x1) = f(x2) ,
• et pour chaque y vous devez être en mesure de trouver un x de sorte que f(x) = y .

Comment convertir l'ID en une URL raccourcie ?

1. Pensez à un alphabet que nous voulons utiliser. Dans votre cas, c'est [a-zA-Z0-9] . Il contient 62 lettres .

2. Prenez une clé numérique unique générée automatiquement (la clé numérique auto-incrémentée). id d'une table MySQL par exemple).

   Pour cet exemple, je vais utiliser 125 ₁₀ (125 avec une base de 10).

3. Maintenant, vous devez convertir 125 ₁₀ à X ₆₂ (base 62).

   125 ₁₀ \= 2×62 1 + 1×62 0 \= [2,1]

   Cela nécessite l'utilisation de la division entière et du modulo. Un exemple de pseudo-code :

   digits = []
   
   while num > 0
     remainder = modulo(num, 62)
     digits.push(remainder)
     num = divide(num, 62)
   
   digits = digits.reverse

   Maintenant, mappez le indices 2 et 1 à votre alphabet. Voici à quoi pourrait ressembler votre mappage (avec un tableau par exemple) :

   0   a
   1   b
   ...
   25  z
   ...
   52  0
   61  9

   Avec 2 c et 1 b, vous obtiendrez cb ₆₂ comme URL raccourcie.

   http://shor.ty/cb

Comment résoudre une URL raccourcie vers l'ID initial ?

L'inverse est encore plus facile. Il suffit de faire une recherche inversée dans votre alphabet.

1. e9a ₆₂ sera résolu en "4ème, 61ème, et 0ème lettre de l'alphabet".

   e9a ₆₂ \= [4,61,0] = 4×62 2 + 61×62 1 + 0×62 0 \= 19158 ₁₀

2. Maintenant, trouvez votre enregistrement de base de données avec WHERE id = 19158 et faire la redirection.

Exemples de mise en œuvre (fournis par les commentateurs)

• C++
• Python
• Ruby
• Haskell
• C#
• CoffeeScript
• Perl

Answer 2

Pourquoi voudriez-vous utiliser un hash ?

Vous pouvez utiliser une simple traduction de votre valeur d'auto-incrémentation en une valeur alphanumérique. Vous pouvez le faire facilement en utilisant une conversion de base. Si votre espace de caractères (A-Z, a-z, 0-9, etc.) comporte 62 caractères, convertissez l'identifiant en un nombre en base 40 et utilisez les caractères comme chiffres.

Answer 3

public class UrlShortener {
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int    BASE     = ALPHABET.length();

    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();   
    }

    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }   
}

Answer 4

Ce n'est pas une réponse à votre question, mais je n'utiliserais pas d'URL raccourcies sensibles à la casse. Elles sont difficiles à mémoriser, généralement illisibles (de nombreuses polices de caractères rendent le 1 et le l, le 0 et le O et d'autres caractères très très similaires, si bien qu'il est presque impossible de faire la différence) et carrément sujettes aux erreurs. Essayez d'utiliser uniquement des minuscules ou des majuscules.

Essayez également d'avoir un format dans lequel vous mélangez les chiffres et les caractères sous une forme prédéfinie. Des études montrent que les gens ont tendance à mieux se souvenir d'une forme que des autres (pensez aux numéros de téléphone, où les chiffres sont regroupés sous une forme spécifique). Essayez quelque chose comme num-char-char-num-char-char. Je sais que cela réduira les combinaisons, surtout si vous n'avez pas de majuscules et de minuscules, mais ce serait plus utilisable et donc utile.

Answer 5

Mon approche : Prendre l'ID de la base de données, puis Base36 Encodez-le . Je n'utiliserais PAS les lettres majuscules ET minuscules, car la transmission de ces URL par téléphone serait un cauchemar, mais vous pourriez bien sûr facilement étendre la fonction pour en faire un décodeur de base 62.