Como codificar um encurtador de URL?

Eu quero criar um serviço de encurtamento de URL onde você pode escrever um URL longo em um campo de input e o serviço encurta o URL para ” http://www.example.org/abcdef “.

Edit: Devido ao interesse contínuo neste tópico, publiquei uma solução eficiente para o GitHub , com implementações para JavaScript , PHP , Python e Java . Adicione suas soluções se você gosta 🙂

Em vez de ” abcdef “, pode haver qualquer outra string com seis caracteres contendo az, AZ and 0-9 . Isso faz de 56 a 57 bilhões de cadeias possíveis.

Minha abordagem:

Eu tenho uma tabela de database com três colunas:

  1. id, inteiro, incremento automático
  2. longo, string, o URL longo que o usuário digitou
  3. short, string, o URL abreviado (ou apenas os seis caracteres)

Em seguida, insiro o URL longo na tabela. Então eu selecionaria o valor de incremento automático para ” id ” e criaria um hash dele. Este hash deve então ser inserido como ” short “. Mas que tipo de hash devo construir? Algoritmos de hash como o MD5 criam strings muito longas. Eu não uso esses algoritmos, eu acho. Um algoritmo auto-criado funcionará também.

Minha ideia:

Para ” http://www.google.de/ “, obtenho o ID de incremento automático 239472 . Então eu faço os seguintes passos:

 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. 

Isso pode ser repetido até que o número não seja mais divisível. Você acha que esta é uma boa abordagem? Você tem uma ideia melhor?

Eu continuaria sua abordagem “converter número para string”. No entanto, você perceberá que seu algoritmo proposto falhará se seu ID for primo e maior que 52 .

Bases teóricas

Você precisa de uma Função Bijetiva f . Isto é necessário para que você possa encontrar uma function inversa g (‘abc’) = 123 para sua function f (123) = ‘abc’ . Isso significa:

  • Não deve haver x1, x2 (com x1 ≠ x2) que fará f (x1) = f (x2) ,
  • e para cada y você deve ser capaz de encontrar um x de modo que f (x) = y .

Como converter o ID em um URL abreviado

  1. Pense em um alfabeto que queremos usar. No seu caso isso é [a-zA-Z0-9] . Contém 62 letras .
  2. Pegue uma chave numérica única gerada automaticamente (o id auto-incrementado de uma tabela MySQL, por exemplo).

    Para este exemplo, vou usar 125 10 (125 com uma base de 10).

  3. Agora você tem que converter 125 10 para X 62 (base 62).

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

    Isso requer o uso de divisão inteira e módulo. Um exemplo de pseudocódigo:

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

    Agora mapeie os índices 2 e 1 para o seu alfabeto. É assim que o seu mapeamento (com uma matriz, por exemplo) poderia ser semelhante:

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

    Com 2 → c e 1 → b, você receberá o cb 62 como o URL abreviado.

     http://shor.ty/cb 

Como resolver um URL abreviado para o ID inicial

O reverso é ainda mais fácil. Você acabou de fazer uma pesquisa inversa em seu alfabeto.

  1. e9a 62 será resolvido para “4ª, 61ª e 0ª letra em alfabeto”.

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

  2. Agora encontre seu registro de database com WHERE id = 19158 e faça o redirecionamento.

Algumas implementações (fornecidas por comentadores)

  • Rubi
  • Python
  • CoffeeScript
  • Haskell
  • Perl
  • C #

Por que você quer usar um hash?
Você pode simplesmente usar uma tradução simples do seu valor de incremento automático para um valor alfanumérico. Você pode fazer isso facilmente usando alguma conversão de base. Digamos que seu espaço de caractere (AZ, az, 0-9 etc ‘) tenha 40 caracteres, converta o ID em um número de base 40 e use os caracteres como os dígitos.

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

Não é uma resposta para sua pergunta, mas eu não usaria URLs encurtados com diferenciação de maiúsculas e minúsculas. Eles são difíceis de lembrar, geralmente ilegíveis (muitas fonts renderizam 1 e l, 0 e O e outros caracteres muito semelhantes que são quase impossíveis de dizer a diferença) e propensos a erros. Tente usar apenas maiúsculas ou minúsculas.

Além disso, tente ter um formato onde você misture os números e caracteres em um formulário predefinido. Há estudos que mostram que as pessoas tendem a se lembrar de uma forma melhor do que outras (pense nos números de telefone, em que os números são agrupados em uma forma específica). Tente algo como num-char-char-num-char-char. Eu sei que isso irá diminuir as combinações, especialmente se você não tiver letras maiúsculas e minúsculas, mas seria mais utilizável e, portanto, útil.

Minha abordagem: pegue o ID do database e, em seguida, Base36 Codifique-o . Eu NÃO usaria letras maiúsculas e minúsculas, porque isso faz da transmissão dessas URLs pelo telefone um pesadelo, mas é claro que você poderia estender facilmente a function para ser um decodificador básico.

Aqui está a minha class 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; } } 

Você poderia fazer o hash de todo o URL, mas se quiser apenas encurtar o id, faça como marcel sugeriu. Eu escrevi esta implementação de python:

https://gist.github.com/778542

Versão 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 você não quer reinventar a roda … 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 

Aqui está a minha versão para quem precisa.

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

Uma solução de nó js e mongodb

Já que conhecemos o formato que o mongodb usa para criar um novo ObjectId com 12 bytes.

  • um valor de 4 bytes representando os segundos desde a época do Unix,
  • um identificador de máquina de 3 bytes,
  • um ID de processo de 2 bytes
  • um contador de 3 bytes (na sua máquina), começando com um valor random.

Exemplo (eu escolho uma seqüência aleatória) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 representa os segundos desde a época do Unix,
  • 4e5f6g7 representa o identificador de máquina,
  • h8i9 representa o id do processo
  • j1k2l3 representa o contador, começando com um valor random.

Como o contador será único se estivermos armazenando os dados na mesma máquina, podemos obtê-lo sem dúvidas de que ele será duplicado.

Portanto, o URL curto será o contador e aqui está um trecho de código, supondo que seu servidor esteja funcionando corretamente.

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

Aqui está uma function de codificação de URL decente para 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; } 

Não sei se alguém achará isso útil – é mais um método ‘hack n slash’, mas é simples e funciona bem se você quiser apenas caracteres específicos.

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

Eu continuo incrementando uma sequência inteira por domínio no database e uso Hashids para codificar o inteiro em um caminho de URL.

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

Eu corri um script para ver quanto tempo demora até esgotar o comprimento do caractere. Para 6 caracteres, ele pode fazer 164,916,224 links e depois subir para 7 caracteres. Bitly usa 7 caracteres. Menos de 5 caracteres parece estranho para mim.

Os hashides podem decodificar o caminho da URL de volta para um número inteiro, mas uma solução mais simples é usar o link curto inteiro sho.rt/ka8ds3 como chave primária.

Aqui está o conceito 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) } 

Por que não apenas traduzir seu id para uma string? Você só precisa de uma function que mapeie um dígito entre, digamos, 0 e 61 para uma única letra (maiúscula / minúscula) ou dígito. Em seguida, aplique isso para criar, digamos, códigos de quatro letras e você terá 14,7 milhões de URLs cobertos.

Isso é o que eu 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))]) 

É muito rápido e pode levar inteiros longos.

Para um projeto semelhante, para obter uma nova chave, faço uma function wrapper em torno de um gerador de strings aleatórias que chama o gerador até obter uma string que já não tenha sido usada na minha hashtable. Esse método diminuirá quando o espaço de nomes começar a ficar cheio, mas, como você disse, mesmo com apenas 6 caracteres, você tem muito espaço para trabalhar.

você omitiu O, 0, i de propósito?

Acabei de criar uma class php baseada na solução de Ryan.

 < ?php $shorty = new App_Shorty(); echo 'ID: ' . 1000; echo '
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; } } ?>

Eu tenho uma variante do problema, em que eu armazeno páginas da web de muitos autores diferentes e preciso impedir a descoberta de páginas por adivinhação. Portanto, meus URLs curtos adicionam alguns dígitos extras à string Base-62 para o número da página. Esses dígitos extras são gerados a partir de informações no próprio registro da página e garantem que apenas 1 em 3844 URLs sejam válidos (assumindo Base-62 de 2 dígitos). Você pode ver uma descrição da estrutura de tópicos em http://mgscan.com/MBWL .

Resposta muito boa, eu criei uma implementação Golang do 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 } 

Hospedado no 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)); } }

Minha versão 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") 

Aqui está a implementação do Node.js que provavelmente será bit.ly. gerar uma sequência de 7 caracteres altamente aleatória. Usando o Node.js crypto para gerar um caractere random de 25 caracteres em vez de 7 caracteres randoms.

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

Para uma solução NodeJS / Javascript de qualidade, consulte o módulo do redutor de ID , que é testado e usado na produção há meses.

Ele fornece um eficiente encurtador id / url suportado pelo armazenamento plugável que se ajusta aos redis , e você pode até customizar seu conjunto de caracteres id curto e se o encurtamento é ou não idempotente . Essa é uma distinção importante que nem todos os redutores de URLs levam em consideração.

Em relação a outras respostas aqui, este módulo implementa a excelente resposta aceita de Marcel Jackwerth acima.

O núcleo da solução é fornecido pelo seguinte 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 

Implementação em 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) } } 

Exemplo de teste com o teste 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) } } 

Função baseada na class 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; }