Come codificare un URL shortener?

Voglio creare un servizio di abbreviazione degli URL in cui è ansible scrivere un URL lungo in un campo di input e il servizio accorcia l’URL a ” http://www.example.org/abcdef “.

Modifica: a causa dell’interesse continuo in questo argomento, ho pubblicato una soluzione efficiente per GitHub , con implementazioni per JavaScript , PHP , Python e Java . Aggiungi le tue soluzioni se ti piace 🙂

Invece di ” abcdef ” ci può essere qualsiasi altra stringa con sei caratteri contenenti az, AZ and 0-9 . Ciò rende 56 ~ 57 miliardi di possibili stringhe.

Il mio approccio:

Ho una tabella di database con tre colonne:

  1. id, intero, autoincremento
  2. long, string, l’URL lungo che l’utente ha inserito
  3. breve, stringa, l’URL abbreviato (o solo i sei caratteri)

Inserirò quindi l’URL lungo nella tabella. Quindi selezionerei il valore di incremento automatico per ” id ” e ne costruirò un hash. Questo hash dovrebbe quindi essere inserito come ” short “. Ma che tipo di hash dovrei build? Gli algoritmi di hash come MD5 creano stringhe troppo lunghe. Non uso questi algoritmi, penso. Funzionerà anche un algoritmo auto-costruito.

La mia idea:

Per ” http://www.google.de/ ” viene visualizzato l’ID di incremento automatico 239472 . Quindi faccio i seguenti passi:

 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 az and AZ. 

Questo potrebbe essere ripetuto fino a quando il numero non sarà più divisibile. Pensi che questo sia un buon approccio? Hai un’idea migliore?

Continuerò il tuo approccio “Converti numero in stringa”. Tuttavia, ti renderai conto che il tuo algoritmo proposto fallisce se il tuo ID è un numero primo e maggiore di 52 .

Background teorico

Hai bisogno di una funzione biiettiva f . Questo è necessario in modo che tu possa trovare una funzione inversa g (‘abc’) = 123 per la tua funzione f (123) = ‘abc’ . Questo significa:

  • Non ci devono essere x1, x2 (con x1 ≠ x2) che renderà f (x1) = f (x2) ,
  • e per ogni y devi essere in grado di trovare una x in modo che f (x) = y .

Come convertire l’ID in un URL abbreviato

  1. Pensa ad un alfabeto che vogliamo usare. Nel tuo caso è [a-zA-Z0-9] . Contiene 62 lettere .
  2. Prendi una chiave numerica unica generata automaticamente (l’ id auto-incrementato di una tabella MySQL per esempio).

    Per questo esempio userò 125 10 (125 con una base di 10).

  3. Ora devi convertire da 125 10 a X 62 (base 62).

    125 10 = 2 × 62 1 + 1 × 62 0 = [2,1]

    Ciò richiede l’uso della divisione intera e del modulo. Un esempio di pseudo-codice:

     digits = [] while num > 0 remainder = modulo(num, 62) digits.push(remainder) num = divide(num, 62) digits = digits.reverse 

    Ora mappare gli indici 2 e 1 al tuo alfabeto. Ecco come potrebbe apparire la tua mapping (con una matrice per esempio):

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

    Con 2 → c e 1 → b riceverai cb 62 come URL abbreviato.

     http://shor.ty/cb 

Come risolvere un URL abbreviato nell’ID iniziale

Il contrario è ancora più semplice. Fai una ricerca inversa nel tuo alfabeto.

  1. e9a 62 verrà risolto in “4 °, 61 ° e 0 ° lettera in alfabeto”.

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

  2. Ora trova il tuo record del database con WHERE id = 19158 e fai il reindirizzamento.

Alcune implementazioni (fornite dai commentatori)

  • Rubino
  • Pitone
  • CoffeeScript
  • Haskell
  • Perl
  • C #

Perché vorresti usare un hash?
Puoi semplicemente utilizzare una semplice traduzione del tuo valore di incremento automatico su un valore alfanumerico. Puoi farlo facilmente usando alcune conversioni di base. Supponi che lo spazio dei caratteri (AZ, az, 0-9 etc ‘) abbia 40 caratteri, converti l’id in un numero base-40 e utilizzi i caratteri come cifre.

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

Non è una risposta alla tua domanda, ma non userei gli URL abbreviati con maiuscole e minuscole. Sono difficili da ricordare, in genere illeggibili (molti tipi di caratteri rendono 1 e l, 0 e O e altri caratteri molto simili che sono quasi impossibili da distinguere) e decisamente inclini all’errore. Prova a utilizzare solo lettere maiuscole o minuscole.

Inoltre, prova ad avere un formato in cui mischi i numeri e i caratteri in una forma predefinita. Esistono studi che dimostrano che le persone tendono a ricordare una forma meglio di altre (si pensi ai numeri di telefono, dove i numeri sono raggruppati in una forma specifica). Prova qualcosa come num-char-char-num-char-char. So che questo abbasserà le combinazioni, soprattutto se non si dispone di maiuscole e minuscole, ma sarebbe più utilizzabile e quindi utile.

Il mio approccio: prendi l’ID del database, poi Base36 lo codifica . NON userei mai le lettere maiuscole e minuscole, perché questo rende la trasmissione di quegli URL al telefono un incubo, ma si potrebbe naturalmente facilmente estendere la funzione per essere un en / decoder di base 62.

Ecco la mia class PHP 5.

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

Potresti cancellare l’intero URL, ma se vuoi solo abbreviare l’id, fai come suggerito da marcel. Ho scritto questa implementazione Python:

https://gist.github.com/778542

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

Se non vuoi reinventare la ruota … 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 

Ecco la mia versione per chi ne ha bisogno.

 // simple approach $original_id = 56789; $shortened_id = base_convert($original_id, 10, 36); $un_shortened_id = base_convert($shortened_id, 36, 10); 

Una soluzione nodo js e mongodb

Dato che conosciamo il formato che mongodb utilizza per creare un nuovo ObjectId con 12 byte.

  • un valore di 4 byte che rappresenta i secondi dall’epoca Unix,
  • un identificatore macchina a 3 byte,
  • un ID processo a 2 byte
  • un contatore da 3 byte (nella macchina), a partire da un valore casuale.

Esempio (scelgo una sequenza casuale) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 rappresenta i secondi dall’epoca Unix,
  • 4e5f6g7 rappresenta l’identificativo della macchina,
  • h8i9 rappresenta l’ID del processo
  • j1k2l3 rappresenta il contatore, a partire da un valore casuale.

Poiché il contatore sarà unico se stiamo memorizzando i dati nella stessa macchina, possiamo ottenerlo senza dubbi che sarà duplicato.

Quindi l’URL breve sarà il contatore e qui c’è uno snippet di codice presupponendo che il tuo server stia funzionando correttamente.

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

Ecco una funzione di codifica URL decente per 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; } 

Non so se qualcuno troverà questo utile – è più un metodo ‘hack n slash’, ma è semplice e funziona bene se vuoi solo caratteri specifici.

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

Continuo ad incrementare una sequenza intera per dominio nel database e uso Hashid per codificare il numero intero in un percorso URL.

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

Ho eseguito una sceneggiatura per vedere quanto tempo ci vuole prima che esaurisca la lunghezza del carattere. Per 6 caratteri può fare 164,916,224 link e quindi può 164,916,224 fino a 7 caratteri. Bitly utilizza 7 caratteri. Sotto i 5 personaggi sembra strano per me.

Gli hashid possono decodificare il percorso dell’URL su un numero intero, ma una soluzione più semplice consiste nell’utilizzare l’intero collegamento breve sho.rt/ka8ds3 come chiave primaria.

Ecco il concetto completo:

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

Perché non tradurre semplicemente il tuo ID in una stringa? Hai solo bisogno di una funzione che mappa una cifra tra, per esempio, 0 e 61 su una singola lettera (maiuscole / minuscole) o una cifra. Quindi applica questo per creare, ad esempio, codici a 4 lettere e hai 14,7 milioni di URL coperti.

Questo è quello che uso:

 # 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))]) 

È molto veloce e può richiedere interi lunghi.

Per un progetto simile, per ottenere una nuova chiave, faccio una funzione wrapper attorno a un generatore di stringhe casuali che chiama il generatore fino a quando non ottengo una stringa che non è già stata usata nel mio hashtable. Questo metodo rallenta una volta che il tuo spazio dei nomi inizia a riempirsi, ma come hai detto, anche con solo 6 caratteri, hai un sacco di spazio dei nomi con cui lavorare.

hai omesso O, 0, io apposta?

Ho appena creato una class PHP basata sulla soluzione di Ryan.

  Short link: ' . $shorty->encode(1000); echo '
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; } } ?>

Ho una variante del problema, nel senso che immagazzino pagine web di molti autori diversi e ho bisogno di impedire la scoperta di pagine da parte di congetture. Quindi i miei URL brevi aggiungono un paio di cifre in più alla stringa Base-62 per il numero di pagina. Queste cifre aggiuntive sono generate dalle informazioni nel record della pagina stessa e assicurano che solo 1 URL 3844 siano validi (presupponendo Base-62 a 2 cifre). Puoi vedere una descrizione del profilo su http://mgscan.com/MBWL .

Risposta molto buona, ho creato un’implementazione di Golang del 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 } 

Ospitato su github: https://github.com/xor-gate/go-bjf

 /** * 

* Integer to character and vice-versa *

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

La mia versione 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") 

Ecco l’implementazione di Node.js che è probabile che bit.ly. genera una stringa di 7 caratteri altamente casuale. utilizzando la crittografia Node.js per generare un set di caratteri 25 altamente casuali di selezionare 7 caratteri casuali.

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

Per una soluzione NodeJS / Javascript di qualità, consultare il modulo id- shortener, che è stato accuratamente testato ed è stato utilizzato in produzione per mesi.

Fornisce un efficace id / url shortener supportato da uno storage innestabile di default redis , e puoi anche personalizzare il tuo set di caratteri short id e se accorciare o meno è idempotente . Questa è una distinzione importante che non tutti gli abbreviazioni URL prendono in considerazione.

In relazione ad altre risposte qui, questo modulo implementa l’eccellente risposta accettata di Marcel Jackwerth sopra.

Il nucleo della soluzione è fornito dal seguente snippet Redis Lua:

 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 

Implementazione in 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) } } 

Prova l’esempio con il 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) } } 

Funzione basata su Xeoncross Class

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