[algorithm] Comment coder un raccourcisseur d'URL?


Answers

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ère (AZ, az, 0-9 etc) a 40 caractères, convertissez l'identifiant en un nombre base-40 et utilisez les caractères sont les chiffres.

Question

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?




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



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.




J'ai une variante du problème, en ce sens que je stocke des pages Web de nombreux auteurs différents et que j'ai besoin d'empêcher la découverte de pages par devinettes. Ainsi, 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 ils garantissent que seulement 1 des 3844 URL sont valides (en supposant que la base-62 à 2 chiffres). Vous pouvez voir une description du plan sur http://mgscan.com/MBWL .




Implémentation en 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)
  }

}



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



/**
 * <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));
    }
}



Un nœud js et une solution mongodb

Puisque nous connaissons le format que mongodb utilise pour créer un nouvel ObjectId avec 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'identifiant du 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é.

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



Voici l'implémentation de Node.js qui est susceptible de bit.ly. génère une chaîne de caractères à 7 caractères hautement aléatoires. en utilisant Node.js crypto pour générer un jeu de caractères hautement aléatoire de 25 caractères que de sélectionner au hasard 7 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;
    };
}



Voici une fonction d'encodage d'URL décent 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;
}



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.




Pourquoi ne pas simplement traduire votre identifiant en 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. Appliquez-le ensuite pour créer, disons, des codes à 4 lettres, et 14,7 millions d'URL sont couvertes.




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 encore été utilisée dans ma hashtable. 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.




Related