Question Comment coder un raccourcisseur d'URL?


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

Modifier: En raison de l'intérêt continu pour ce sujet, j'ai a publié une solution efficace pour GitHub, avec des implémentations pour JavaScript, PHP, Python et Java. Ajoutez vos solutions si vous aimez :)

Au lieu de "abcdef"il peut y avoir toute autre chaîne avec 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, chaîne, l'URL longue entrée par l'utilisateur
  3. short, string, l'URL raccourcie (ou seulement les six caractères)

J'insérerais alors l'URL longue dans la table. Ensuite, je sélectionnerais la valeur d'auto-incrément pour "id"et construisez un hachage de celui-ci.Ce hachage devrait alors ê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, je pense.Un algorithme auto-construit fonctionnera aussi.

Mon idée:

Pour "http://www.google.de/"Je reçois l'identifiant de l'auto-incrément 239472. Ensuite, je fais les é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? As-tu une meilleure idée?


572
2018-04-12 16:29


origine


Réponses:


Je continuerais votre approche "convertir le nombre en chaîne". Cependant, vous réaliserez que votre algorithme proposé échoue si votre ID est un Premier et plus grand que 52.

Contexte théorique

Tu as besoin d'un Fonction bijective  F. Ceci est nécessaire pour que vous puissiez trouver une fonction inverse g ('abc') = 123 pour votre f (123) = 'abc' fonction. Ça signifie:

  • Il ne doit pas y avoir x1, x2 (avec x1 ≠ x2) cela fera f (x1) = f (x2),
  • et pour tous y vous devez être capable de trouver un X pour 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. Prendre une clé numérique unique générée automatiquement (l'incrémentation automatique id d'une table MySQL par exemple).

    Pour cet exemple, j'utiliserai 125dix (125 avec une base de 10).

  3. Maintenant vous devez convertir 125dix à X62 (base 62).

    125dix = 2 × 621 + 1 × 620 = [2,1]

    Cela nécessite l'utilisation de la division entière et 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 cartographie le indices 2 et 1 à votre alphabet. Voici comment votre mapping (avec un tableau par exemple) pourrait ressembler:

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

    Avec 2 → c et 1 → b vous recevrez cb62 comme l'URL raccourci.

    http://shor.ty/cb
    

Comment résoudre une URL raccourcie à l'ID initial

L'inverse est encore plus facile. Vous faites juste une recherche inversée dans votre alphabet.

  1. e9a62 sera résolu à "4ème, 61ème et 0ème lettre en alphabet".

    e9a62 = [4,61,0] = 4 × 622 + 61 × 621 + 0 × 620 = 19158dix

  2. Trouvez maintenant votre enregistrement de base de données avec WHERE id = 19158 et faites la redirection.

Quelques implémentations (fournies par les commentateurs)


713
2018-04-12 16:34



Pourquoi voudriez-vous utiliser un hachage?
Vous pouvez simplement utiliser une simple translation de votre valeur d'incrémentation automatique à une valeur alphanumérique. Vous pouvez le faire facilement en utilisant une conversion de base. Dites que votre espace de caractères (A-Z, a-z, 0-9, etc.) a 40 caractères, convertissez l'identifiant en un nombre de base-40 et utilisez les caractères sont les chiffres.


49
2017-07-11 01:30



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;
    }   
}

44
2018-04-12 17:50



Ce n'est pas une réponse à votre question, mais je n'utiliserais pas d'URL raccourcies sensibles à la casse. Ils sont difficiles à retenir, généralement illisibles (beaucoup de polices rendent 1 et 1, 0 et O et d'autres caractères très très proches qu'ils sont presque impossibles à faire la différence) et carrément erronés. Essayez d'utiliser des majuscules ou des minuscules uniquement.

En outre, essayez d'avoir un format où vous mélanger les nombres et les caractères dans un formulaire prédéfini. Il y a des études qui montrent que les gens ont tendance à se souvenir d'une forme mieux que d'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 abaissera les combinaisons, surtout si vous n'avez pas de majuscules et minuscules, mais ce serait plus utile et donc utile.


30
2018-04-14 08:02



Mon approche: Prenez l'identifiant de la base de données, puis Base36 l'encoder. Je n'utiliserais PAS les lettres majuscules et minuscules, car cela rendrait la transmission de ces URLs au-dessus du téléphone un cauchemar, mais vous pourriez bien sûr étendre facilement la fonction pour en faire un décodeur de base.


26
2017-11-04 20:10



Voici ma classe PHP 5.

<?php
class Bijective
{
    public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public function __construct()
    {
        $this->dictionary = str_split($this->dictionary);
    }

    public function encode($i)
    {
        if ($i == 0)
        return $this->dictionary[0];

        $result = '';
        $base = count($this->dictionary);

        while ($i > 0)
        {
            $result[] = $this->dictionary[($i % $base)];
            $i = floor($i / $base);
        }

        $result = array_reverse($result);

        return join("", $result);
    }

    public function decode($input)
    {
        $i = 0;
        $base = count($this->dictionary);

        $input = str_split($input);

        foreach($input as $char)
        {
            $pos = array_search($char, $this->dictionary);

            $i = $i * $base + $pos;
        }

        return $i;
    }
}

7
2018-01-17 21:35



Vous pouvez hacher l'intégralité de l'URL, mais si vous souhaitez simplement raccourcir l'identifiant, faites comme suggéré par marcel. J'ai écrit cette implémentation de Python:

https://gist.github.com/778542


3
2018-03-08 20:17



Version C #:

public class UrlShortener 
{
    private static String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static int    BASE     = 62;

    public static String encode(int num)
    {
        StringBuilder sb = new StringBuilder();

        while ( num > 0 )
        {
            sb.Append( ALPHABET[( num % BASE )] );
            num /= BASE;
        }

        StringBuilder builder = new StringBuilder();
        for (int i = sb.Length - 1; i >= 0; i--)
        {
            builder.Append(sb[i]);
        }
        return builder.ToString(); 
    }

    public static int decode(String str)
    {
        int num = 0;

        for ( int i = 0, len = str.Length; i < len; i++ )
        {
            num = num * BASE + ALPHABET.IndexOf( str[(i)] ); 
        }

        return num;
    }   
}

3
2018-04-12 17:12



Si vous ne voulez pas réinventer la roue ... http://lilurl.sourceforge.net/


2
2017-11-21 22:21



alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10))

def lookup(k, a=alphabet):
    if type(k) == int:
        return a[k]
    elif type(k) == str:
        return a.index(k)


def encode(i, a=alphabet):
    '''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.'''
    try:
        i = int(i)
    except Exception:
        raise TypeError("Input must be an integer.")

    def incode(i=i, p=1, a=a):
        # Here to protect p.                                                                                                                                                                                                                
        if i <= 61:
            return lookup(i)

        else:
            pval = pow(62,p)
            nval = i/pval
            remainder = i % pval
            if nval <= 61:
                return lookup(nval) + incode(i % pval)
            else:
                return incode(i, p+1)

    return incode()



def decode(s, a=alphabet):
    '''Takes a base 62 string in our alphabet and returns it in base10.'''
    try:
        s = str(s)
    except Exception:
        raise TypeError("Input must be a string.")

    return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a

Voici ma version pour ceux qui en ont besoin.


2
2017-12-20 10:59