algorithm personnalisé - Comment coder un raccourcisseur d'URL?




14 Answers

Je continuerais votre approche "convertir le nombre en chaîne". Cependant, vous réaliserez que votre algorithme proposé échoue si votre ID est un nombre premier et 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 tout y, vous devez être capable 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 (l' id auto-incrémenté d'une table MySQL par exemple).

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

  3. Maintenant, vous devez convertir 125 10 en X 62 (base 62).

    125 10 = 2 × 62 1 + 1 × 62 0 = [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 les 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 cb 62 comme URL raccourcie.

    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. e9a 62 sera résolu à "4ème, 61ème et 0ème lettre en alphabet".

    e9a 62 = [4,61,0] = 4 × 62 2 + 61 × 62 1 + 0 × 62 0 = 19158 10

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

Quelques implémentations (fournies par les commentateurs)

google shortener

Je souhaite 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 à " http://www.example.org/abcdef ".

Edit: 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 aimez :)

Au lieu de " abcdef " il peut y avoir n'importe quelle autre chaîne avec six caractères contenant az, AZ 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 voudrais sélectionner la valeur d'auto-incrémentation pour " id " et construire un hachage de celui-ci. Ce hachage devrait alors être inséré comme " short ". Mais quel genre de hash devrais-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/ ", j'obtiens l'identifiant d'auto-incrémentation 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?




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



Mon approche: Prenez l'ID de base de données, puis Base36 Encodez-le . 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.




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:

Python







// simple approach

$original_id = 56789;

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

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



Je ne sais pas si quelqu'un trouvera cela utile - il s'agit plutôt d'une méthode «hack n slash», pourtant simple et qui 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);
} 



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

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

J'ai couru un script pour voir combien de temps il faut pour éponger la longueur du personnage. Pour 6 caractères, il peut faire 164,916,224 liens, puis aller jusqu'à 7 caractères. Bitly utilise 7 caractères. Moins de 5 caractères me semble bizarre.

Hashids peut décoder le chemin de l'URL en entier, mais une solution plus simple consiste à utiliser le raccourci sho.rt/ka8ds3 comme 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)
}



C'est 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.




avez-vous omis O, 0, je exprès?

Juste créé 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  below.
     * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca
     * @see http://.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945
     */
    class App_Shorty {
        /**
         * Explicitely 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;
        }
    }

?>



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é à github: https://github.com/xor-gate/go-bjf




Ma version de python3

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 NodeJS / Javascript de qualité, consultez le module id-shortener shortener, qui a fait l'objet de tests approfondis et a été utilisé en production pendant des mois.

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

Par rapport à d'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' snippet Redis Lua snippet :

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



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



Related

algorithm url