Comment coder un raccourcisseur D'URL?

Pourquoi voudriez-vous utiliser un hachage?
Vous pouvez simplement utiliser une simple traduction de votre valeur d'incrément automatique en une valeur alphanumérique. Vous pouvez le faire facilement en utilisant une conversion de base. Disons que l'espace de caractères (A-Z,a-z,0-9 etc') a 40 caractères, convertissez l'id en un nombre de base-40 et utilisez les caractères sont les 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 rendent 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 sujettes aux erreurs. Essayez d'utiliser uniquement des majuscules ou des majuscules.

Aussi, essayez d'avoir un format où vous mélangez les nombres et les caractères sous une forme prédéfinie. 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 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: prenez L'ID de base de données, puis Base36 L'Encoder . Je n'utiliserais pas les lettres majuscules et minuscules, car cela rend la transmission de ces URL par téléphone un cauchemar, mais vous pourriez bien sûr facilement étendre la fonction pour être une base 62 en/décodeur.

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

Vous pouvez hacher l'URL entière, mais si vous voulez juste raccourcir l'id, faites comme marcel l'a suggéré. J'ai écrit cette implémentation python:

Https://gist.github.com/778542

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

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

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.

// simple approach

$original_id = 56789;

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

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

une solution de noeud js et mongodb

Puisque nous connaissons le format que mongodb utilise pour créer un nouvel ObjectId de 12 octets.

• une valeur de 4 octets représentant les secondes depuis L'époque Unix,
• un identifiant de machine de 3 octets,
• un identifiant de processus de 2 octets
• un compteur de 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.

Puisque 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é.

Donc l'URL courte sera le comptoir 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");
    })
});

Voici une fonction d'encodage 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 - c'est plus 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);
} 

Je continue à 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 jusqu'à ce qu'il épuise la longueur du caractère. Pour 6 caractères, il peut faire des liens 164,916,224, puis passe à 7 caractères. Bitly utilise 7 caractères. Moins de 5 caractères me semble bizarre.

Hashids {[6] } peut décoder le chemin D'URL vers un entier, mais une solution plus simple consiste à utiliser le short entier lien 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)
}

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

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.

Pour un projet similaire, pour obtenir une nouvelle clé, je crée une fonction wrapper autour d'un random string generator 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 permettra de ralentir une fois votre nom d'espace commence à être plein, mais comme vous l'avez dit, même avec seulement 6 caractères, vous avez beaucoup d'espace de noms pour travailler avec.

Avez-vous omis O, 0, I exprès ?

Vient 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 stackoverflow 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 {
        /**
         * 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;
        }
    }

?>

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 de base-62 pour le numéro de page. Ces chiffres supplémentaires sont générés à partir d'informations dans l'enregistrement de la page elle-même et ils garantissent que seulement 1 URL sur 3844 sont valides (en supposant que 2 chiffres Base-62). Vous pouvez voir une description de contour à 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));
    }
}

MA version 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")

Voici le nœud.mise en œuvre js qui est susceptible de bit.ly. générer une chaîne de 7 caractères hautement aléatoire. en utilisant Node.js crypto pour générer un jeu de caractères 25 hautement aléatoire que aléatoire sélectionner 7 caractère.

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

Pour une solution NodeJS / Javascript de qualité, consultez le module id-shortener , qui est soigneusement testé et utilisé en production depuis des mois.

Il fournit un raccourcisseur d'id / url efficace soutenu par un stockage enfichable par défaut à redis , et vous pouvez même personnaliser votre jeu de caractères ID court et si le raccourcissement est idempotent . C'est 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 noyau de la solution est fourni par le redis Lua snippet 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

Mise en œuvre dans 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 Scala test:

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