Comment créer un raccourcisseur d'URL?

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 toute autre chaîne contenant six caractères 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, incrémentation automatique
2. long, string, l'URL longue saisie par l'utilisateur
3. court, chaîne, l'URL raccourcie (ou seulement les six caractères)

Je voudrais ensuite insérer l'URL longue dans le tableau. Ensuite, je sélectionnerais la valeur d'incrémentation automatique pour " id" et j'en créerais un hachage. Ce hachage doit ensuite être inséré en tant que " short". Mais quelle sorte de hachage dois-je créer? 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 également.

Mon idée:

Pour " http://www.google.de/", j'obtiens l'ID d'incrémentation automatique 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?

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

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

Contexte théorique

Vous avez besoin d'une fonction bijective f . Ceci est nécessaire pour que vous puissiez trouver une fonction inverse g ('abc') = 123 pour votre fonction f (123) = 'abc' . Ça 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 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. Prenez une clé numérique unique générée automatiquement (l'incrémentation automatique idd'une table MySQL par exemple).

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

3. Vous devez maintenant convertir 125 ₁₀ en X ₆₂ (base 62).

   125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ =[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
   

   Mappez maintenant les 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 recevrez cb ₆₂ comme URL raccourcie.

   http://shor.ty/cb
   

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

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

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

   e9a ₆₂ = [4,61,0]= 4 × 62 ² + 61 × 62 ¹ + 0 × 62 ⁰ = 19158 ₁₀

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

Exemples d'implémentations (fournies par les commentateurs)

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

Pourquoi voudriez-vous utiliser un hachage?

Vous pouvez simplement utiliser une simple traduction de votre valeur d'incrémentation automatique en une valeur alphanumérique. Vous pouvez le faire facilement en utilisant une conversion de base. Supposons que votre espace de caractères (AZ, az, 0-9, etc.) comporte 40 caractères, convertissez l'identifiant en un nombre de base 40 et utilisez les caractères comme chiffres.

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

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 (de nombreuses polices affichent 1 et l, 0 et O et d'autres caractères très très similaires qu'ils sont presque impossibles à faire la différence) et carrément sujets 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. Il existe 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 numéros 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.

Mon approche: prendre l'ID de base de données, puis encoder en Base36 . Je n'utiliserais PAS les deux lettres majuscules ET minuscules, car cela fait de la transmission de ces URL par téléphone un cauchemar, mais vous pouvez bien sûr facilement étendre la fonction pour en faire un décodeur / base 62.

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

Une solution Node.js et MongoDB

Puisque nous connaissons le format utilisé par MongoDB pour créer un nouvel ObjectId avec 12 octets.

• une valeur de 4 octets représentant les secondes depuis l'époque Unix,
• un identifiant machine de 3 octets,
• un identifiant de processus de 2 octets
• un compteur à 3 octets (dans votre machine), en commençant par une valeur aléatoire.

Exemple (je choisis une séquence aléatoire) a1b2c3d4e5f6g7h8i9j1k2l3

• a1b2c3d4 représente les secondes depuis l'époque Unix,
• 4e5f6g7 représente l'identifiant de la machine,
• h8i9 représente l'ID de processus
• j1k2l3 représente le compteur, en commençant par une valeur aléatoire.

Étant donné que le compteur sera unique si nous stockons les données dans la même machine, nous pouvons l'obtenir sans aucun doute qu'il sera dupliqué.

Ainsi, l'URL courte sera le compteur et voici un extrait de code en supposant que votre serveur fonctionne correctement.

const mongoose = require('mongoose');
const Schema = mongoose.Schema;

// Create a schema
const shortUrl = new Schema({
    long_url: { type: String, required: true },
    short_url: { type: String, required: true, unique: true },
  });
const ShortUrl = mongoose.model('ShortUrl', shortUrl);

// The user can request to get a short URL by providing a long URL using a form

app.post('/shorten', function(req ,res){
    // Create a new shortUrl */
    // The submit form has an input with longURL as its name attribute.
    const longUrl = req.body["longURL"];
    const newUrl = ShortUrl({
        long_url : longUrl,
        short_url : "",
    });
    const shortUrl = newUrl._id.toString().slice(-6);
    newUrl.short_url = shortUrl;
    console.log(newUrl);
    newUrl.save(function(err){
        console.log("the new URL is added");
    })
});

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

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

https://gist.github.com/778542

Je continue à incrémenter une séquence entière par domaine dans la base de données et j'utilise Hashids pour coder l'entier dans un chemin URL.

static hashids = Hashids(salt = "my app rocks", minSize = 6)

J'ai exécuté un script pour voir combien de temps cela prend jusqu'à ce qu'il épuise la longueur du personnage. Pour six caractères, il peut faire des 164,916,224liens puis monter jusqu'à sept caractères. Bitly utilise sept caractères. Moins de cinq personnages me semble bizarre.

Les Hashids peuvent décoder le chemin URL vers un entier, mais une solution plus simple consiste à utiliser le lien court entier sho.rt/ka8ds3comme clé primaire.

Voici le concept complet:

function addDomain(domain) {
    table("domains").insert("domain", domain, "seq", 0)
}

function addURL(domain, longURL) {
    seq = table("domains").where("domain = ?", domain).increment("seq")
    shortURL = domain + "/" + hashids.encode(seq)
    table("links").insert("short", shortURL, "long", longURL)
    return shortURL
}

// GET /:hashcode
function handleRequest(req, res) {
    shortURL = req.host + "/" + req.param("hashcode")
    longURL = table("links").where("short = ?", shortURL).get("long")
    res.redirect(301, longURL)
}

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

// simple approach

$original_id = 56789;

$shortened_id = base_convert($original_id, 10, 36);

$un_shortened_id = base_convert($shortened_id, 36, 10);

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 qui en a besoin.

Jetez un œil à https://hashids.org/ il est open source et dans de nombreuses langues.

Leur page décrit certains des pièges d'autres approches.

Pourquoi ne pas simplement traduire votre identifiant en une chaîne? Vous avez juste besoin d'une fonction qui mappe un chiffre entre, disons, 0 et 61 à une seule lettre (majuscule / minuscule) ou chiffre. Ensuite, appliquez-le pour créer, disons, des codes à 4 lettres, et vous avez couvert 14,7 millions d'URL.

Voici une fonction de codage d'URL décente pour PHP ...

// From http://snipplr.com/view/22246/base62-encode--decode/
private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') {
    $str = '';
    do {
        $i = fmod($val, $base);
        $str = $chars[$i] . $str;
        $val = ($val - $i) / $base;
    } while($val > 0);
    return $str;
}

Je ne sais pas si quelqu'un trouvera cela utile - il s'agit plutôt d'une méthode 'hack n slash', mais elle est simple et fonctionne bien si vous ne voulez que des caractères spécifiques.

$dictionary = "abcdfghjklmnpqrstvwxyz23456789";
$dictionary = str_split($dictionary);

// Encode
$str_id = '';
$base = count($dictionary);

while($id > 0) {
    $rem = $id % $base;
    $id = ($id - $rem) / $base;
    $str_id .= $dictionary[$rem];
}


// Decode
$id_ar = str_split($str_id);
$id = 0;

for($i = count($id_ar); $i > 0; $i--) {
    $id += array_search($id_ar[$i-1], $dictionary) * pow($base, $i - 1);
} 

Avez-vous omis O, 0 et i exprès?

Je viens de créer une classe PHP basée sur la solution de Ryan.

<?php

    $shorty = new App_Shorty();

    echo 'ID: ' . 1000;
    echo '<br/> Short link: ' . $shorty->encode(1000);
    echo '<br/> Decoded Short Link: ' . $shorty->decode($shorty->encode(1000));


    /**
     * A nice shorting class based on Ryan Charmley's suggestion see the link on Stack Overflow below.
     * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca
     * @see http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945
     */
    class App_Shorty {
        /**
         * Explicitly omitted: i, o, 1, 0 because they are confusing. Also use only lowercase ... as
         * dictating this over the phone might be tough.
         * @var string
         */
        private $dictionary = "abcdfghjklmnpqrstvwxyz23456789";
        private $dictionary_array = array();

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

        /**
         * Gets ID and converts it into a string.
         * @param int $id
         */
        public function encode($id) {
            $str_id = '';
            $base = count($this->dictionary_array);

            while ($id > 0) {
                $rem = $id % $base;
                $id = ($id - $rem) / $base;
                $str_id .= $this->dictionary_array[$rem];
            }

            return $str_id;
        }

        /**
         * Converts /abc into an integer ID
         * @param string
         * @return int $id
         */
        public function decode($str_id) {
            $id = 0;
            $id_ar = str_split($str_id);
            $base = count($this->dictionary_array);

            for ($i = count($id_ar); $i > 0; $i--) {
                $id += array_search($id_ar[$i - 1], $this->dictionary_array) * pow($base, $i - 1);
            }
            return $id;
        }
    }
?>

Voici ce que j'utilise:

# Generate a [0-9a-zA-Z] string
ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91))

def encode_id(id_number, alphabet=ALPHABET):
    """Convert an integer to a string."""
    if id_number == 0:
        return alphabet[0]

    alphabet_len = len(alphabet) # Cache

    result = ''
    while id_number > 0:
        id_number, mod = divmod(id_number, alphabet_len)
        result = alphabet[mod] + result

    return result

def decode_id(id_string, alphabet=ALPHABET):
    """Convert a string to an integer."""
    alphabet_len = len(alphabet) # Cache
    return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))])

C'est très rapide et peut prendre de longs entiers.

Pour un projet similaire, pour obtenir une nouvelle clé, je crée une fonction wrapper autour d'un générateur de chaîne aléatoire qui appelle le générateur jusqu'à ce que j'obtienne une chaîne qui n'a pas déjà été utilisée dans ma table de hachage. Cette méthode ralentira une fois que votre espace de noms commencera à être plein, mais comme vous l'avez dit, même avec seulement 6 caractères, vous avez beaucoup d'espace de noms avec lequel travailler.

J'ai une variante du problème, en ce sens que je stocke des pages Web de nombreux auteurs différents et que je dois empêcher la découverte de pages par conjecture. Donc, mes URL courtes ajoutent quelques chiffres supplémentaires à la chaîne Base-62 pour le numéro de page. Ces chiffres supplémentaires sont générés à partir des informations contenues dans l'enregistrement de page lui-même et garantissent que seules 1 URL sur 3844 sont valides (en supposant une base-62 à 2 chiffres). Vous pouvez voir une description générale sur http://mgscan.com/MBWL .

Très bonne réponse, j'ai créé une implémentation Golang du bjf:

package bjf

import (
    "math"
    "strings"
    "strconv"
)

const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func Encode(num string) string {
    n, _ := strconv.ParseUint(num, 10, 64)
    t := make([]byte, 0)

    /* Special case */
    if n == 0 {
        return string(alphabet[0])
    }

    /* Map */
    for n > 0 {
        r := n % uint64(len(alphabet))
        t = append(t, alphabet[r])
        n = n / uint64(len(alphabet))
    }

    /* Reverse */
    for i, j := 0, len(t) - 1; i < j; i, j = i + 1, j - 1 {
        t[i], t[j] = t[j], t[i]
    }

    return string(t)
}

func Decode(token string) int {
    r := int(0)
    p := float64(len(token)) - 1

    for i := 0; i < len(token); i++ {
        r += strings.Index(alphabet, string(token[i])) * int(math.Pow(float64(len(alphabet)), p))
        p--
    }

    return r
}

Hébergé sur github: https://github.com/xor-gate/go-bjf

/**
 * <p>
 *     Integer to character and vice-versa
 * </p>
 *  
 */
public class TinyUrl {

    private final String characterMap = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final int charBase = characterMap.length();

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

        while (num > 0){
            sb.append(characterMap.charAt(num % charBase));
            num /= charBase;
        }

        return sb.reverse().toString();
    }

    public int covertToInteger(String str){
        int num = 0;
        for(int i = 0 ; i< str.length(); i++)
            num += characterMap.indexOf(str.charAt(i)) * Math.pow(charBase , (str.length() - (i + 1)));

        return num;
    }
}

class TinyUrlTest{

    public static void main(String[] args) {
        TinyUrl tinyUrl = new TinyUrl();
        int num = 122312215;
        String url = tinyUrl.covertToCharacter(num);
        System.out.println("Tiny url:  " + url);
        System.out.println("Id: " + tinyUrl.covertToInteger(url));
    }
}

Mise en œuvre à Scala:

class Encoder(alphabet: String) extends (Long => String) {

  val Base = alphabet.size

  override def apply(number: Long) = {
    def encode(current: Long): List[Int] = {
      if (current == 0) Nil
      else (current % Base).toInt :: encode(current / Base)
    }
    encode(number).reverse
      .map(current => alphabet.charAt(current)).mkString
  }
}

class Decoder(alphabet: String) extends (String => Long) {

  val Base = alphabet.size

  override def apply(string: String) = {
    def decode(current: Long, encodedPart: String): Long = {
      if (encodedPart.size == 0) current
      else decode(current * Base + alphabet.indexOf(encodedPart.head),encodedPart.tail)
    }
    decode(0,string)
  }
}

Exemple de test avec test Scala:

import org.scalatest.{FlatSpec, Matchers}

class DecoderAndEncoderTest extends FlatSpec with Matchers {

  val Alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

  "A number with base 10" should "be correctly encoded into base 62 string" in {
    val encoder = new Encoder(Alphabet)
    encoder(127) should be ("cd")
    encoder(543513414) should be ("KWGPy")
  }

  "A base 62 string" should "be correctly decoded into a number with base 10" in {
    val decoder = new Decoder(Alphabet)
    decoder("cd") should be (127)
    decoder("KWGPy") should be (543513414)
  }

}

Fonction basée sur la classe Xeoncross

function shortly($input){
$dictionary = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9'];
if($input===0)
    return $dictionary[0];
$base = count($dictionary);
if(is_numeric($input)){
    $result = [];
    while($input > 0){
        $result[] = $dictionary[($input % $base)];
        $input = floor($input / $base);
    }
    return join("", array_reverse($result));
}
$i = 0;
$input = str_split($input);
foreach($input as $char){
    $pos = array_search($char, $dictionary);
    $i = $i * $base + $pos;
}
return $i;
}

Voici une implémentation Node.js qui est susceptible de bit.ly. générer une chaîne de sept caractères hautement aléatoire.

Il utilise la cryptographie Node.js pour générer un jeu de caractères 25 très aléatoire plutôt que de sélectionner au hasard sept caractères.

var crypto = require("crypto");
exports.shortURL = new function () {
    this.getShortURL = function () {
        var sURL = '',
            _rand = crypto.randomBytes(25).toString('hex'),
            _base = _rand.length;
        for (var i = 0; i < 7; i++)
            sURL += _rand.charAt(Math.floor(Math.random() * _rand.length));
        return sURL;
    };
}

Ma version Python 3

base_list = list("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
base = len(base_list)

def encode(num: int):
    result = []
    if num == 0:
        result.append(base_list[0])

    while num > 0:
        result.append(base_list[num % base])
        num //= base

    print("".join(reversed(result)))

def decode(code: str):
    num = 0
    code_list = list(code)
    for index, code in enumerate(reversed(code_list)):
        num += base_list.index(code) * base ** index
    print(num)

if __name__ == '__main__':
    encode(341413134141)
    decode("60FoItT")

Pour une solution Node.js / JavaScript de qualité, consultez le module id-shortener , qui est minutieusement testé et utilisé en production depuis des mois.

Il fournit un raccourcisseur id / URL efficace soutenu par un stockage enfichable par défaut sur Redis , et vous pouvez même personnaliser votre jeu de caractères id court et si le raccourcissement est idempotent ou non . Il s'agit d'une distinction importante que tous les raccourcisseurs d'URL ne prennent pas en compte.

Par rapport aux autres réponses ici, ce module implémente l'excellente réponse acceptée de Marcel Jackwerth ci-dessus.

Le cœur de la solution est fourni par l' extrait de code Redis Lua suivant :

local sequence = redis.call('incr', KEYS[1])

local chars = '0123456789ABCDEFGHJKLMNPQRSTUVWXYZ_abcdefghijkmnopqrstuvwxyz'
local remaining = sequence
local slug = ''

while (remaining > 0) do
  local d = (remaining % 60)
  local character = string.sub(chars, d + 1, d + 1)

  slug = character .. slug
  remaining = (remaining - d) / 60
end

redis.call('hset', KEYS[2], slug, ARGV[1])

return slug

Pourquoi ne pas simplement générer une chaîne aléatoire et l'ajouter à l'URL de base? Il s'agit d'une version très simplifiée de cette opération en C # .

static string chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
static string baseUrl = "https://google.com/";

private static string RandomString(int length)
{
    char[] s = new char[length];
    Random rnd = new Random();
    for (int x = 0; x < length; x++)
    {
        s[x] = chars[rnd.Next(chars.Length)];
    }
    Thread.Sleep(10);

    return new String(s);
}

Ensuite, ajoutez simplement la chaîne aléatoire à l'URL de base:

string tinyURL = baseUrl + RandomString(5);

N'oubliez pas qu'il s'agit d'une version très simplifiée de cette opération et qu'il est possible que la méthode RandomString puisse créer des chaînes en double. En production, vous voudrez tenir compte des chaînes en double pour vous assurer d'avoir toujours une URL unique. J'ai du code qui prend en compte les chaînes en double en interrogeant une table de base de données que je pourrais partager si quelqu'un est intéressé.

Voici mes premières réflexions, et plus de réflexion peut être faite, ou une simulation peut être faite pour voir si cela fonctionne bien ou si une amélioration est nécessaire:

Ma réponse est de se souvenir de l'URL longue dans la base de données et d'utiliser l'ID 0pour 9999999999999999(ou quel que soit le nombre requis).

Mais l'ID 0 9999999999999999peut être un problème, car

1. il peut être plus court si nous utilisons hexadécimal, ou même base62 ou base64. (base64 comme YouTube en utilisant A- Z a- z 0- 9 _et -)
2. si elle augmente de 0à 9999999999999999uniformément, les pirates peuvent les visiter dans cet ordre et savoir quelles URL les gens s'envoient, ce qui peut donc être un problème de confidentialité

Nous pouvons le faire:

1. avoir un serveur alloué 0à 999un serveur, le serveur A, donc maintenant le serveur A a 1000 de ces ID. Donc, s'il y a 20 ou 200 serveurs qui veulent constamment de nouveaux identifiants, il ne doit pas continuer à demander chaque nouvel identifiant, mais plutôt à demander une fois 1000 identifiants
2. pour l'ID 1, par exemple, inversez les bits. Donc , 000...00000001devient 10000...000, de sorte que lorsqu'il est converti en base64, il sera de plus en plus ID non uniforme à chaque fois.
3. utilisez XOR pour retourner les bits pour les ID finaux. Par exemple, XOR avec 0xD5AA96...2373(comme une clé secrète), et les quelques bits seront retournés. (chaque fois que la clé secrète a le bit 1, elle retournera le bit de l'ID). Cela rendra les ID encore plus difficiles à deviner et apparaîtra plus aléatoire

Suivant ce schéma, le serveur unique qui alloue les ID peut former les ID, tout comme les 20 ou 200 serveurs qui demandent l'allocation des ID. Le serveur d'allocation doit utiliser un verrou / sémaphore pour empêcher deux serveurs demandeurs d'obtenir le même lot (ou s'il accepte une connexion à la fois, cela résout déjà le problème). Nous ne voulons donc pas que la ligne (file d'attente) soit trop longue pour attendre d'obtenir une allocation. C'est pourquoi l'allocation de 1 000 ou 10 000 à la fois peut résoudre le problème.