Cómo codificar un acortador de URL?

Quiero crear un servicio de acortador de URL en el que pueda escribir una URL larga en un campo de entrada y el servicio acorta la URL a ” http://www.example.org/abcdef “.

Editar: Debido al continuo interés en este tema, publiqué una solución eficiente para GitHub , con implementaciones para JavaScript , PHP , Python y Java . Agrega tus soluciones si quieres 🙂

En lugar de ” abcdef ” puede haber cualquier otra cadena con seis caracteres que contengan az, AZ and 0-9 . Eso hace 56 ~ 57 mil millones de cadenas posibles.

Mi acercamiento:

Tengo una tabla de base de datos con tres columnas:

  1. id, entero, autoincremento
  2. long, string, la URL larga que ingresó el usuario
  3. short, string, la URL acortada (o solo los seis caracteres)

Luego insertaba la URL larga en la tabla. Luego seleccionaría el valor de auto incremento para ” id ” y construiría un hash de él. Este hash debería insertarse como ” short “. Pero, ¿qué tipo de hash debo construir? Los algoritmos hash como MD5 crean cadenas demasiado largas. Yo no uso estos algoritmos, creo. Un algoritmo autoconstruido también funcionará.

Mi idea:

Para ” http://www.google.de/ ” obtengo el ID de incremento automático 239472 . Luego hago los siguientes pasos:

 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. 

Eso podría repetirse hasta que el número ya no sea divisible. ¿Crees que este es un buen enfoque? Tienes una mejor idea?

Continuaría con su enfoque de “Convertir número a cadena”. Sin embargo, se dará cuenta de que su algoritmo propuesto falla si su ID es primo y mayor que 52 .

Antecedentes teóricos

Necesitas una Función Bijective f . Esto es necesario para que pueda encontrar una función inversa g (‘abc’) = 123 para su función f (123) = ‘abc’ . Esto significa:

  • No debe haber x1, x2 (con x1 ≠ x2) que hará que f (x1) = f (x2) ,
  • y por cada y debes poder encontrar una x para que f (x) = y .

Cómo convertir el ID a una URL acortada

  1. Piensa en un alfabeto que queremos usar. En tu caso, eso es [a-zA-Z0-9] . Contiene 62 letras .
  2. Tome una clave numérica única generada automáticamente (la id autoincrementada de una tabla MySQL, por ejemplo).

    Para este ejemplo usaré 125 10 (125 con una base de 10).

  3. Ahora debe convertir 125 10 a X 62 (base 62).

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

    Esto requiere el uso de división y módulo enteros. Un ejemplo de pseudo-código:

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

    Ahora asigna los índices 2 y 1 a tu alfabeto. Así es como podría verse tu mapeo (con una matriz, por ejemplo):

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

    Con 2 → c y 1 → b, recibirá cb 62 como la URL acortada.

     http://shor.ty/cb 

Cómo resolver una URL acortada a la ID inicial

El reverso es aún más fácil. Simplemente haz una búsqueda inversa en tu alfabeto.

  1. e9a 62 se resolverá con “4ª, 61ª y 0ª letra en alfabeto”.

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

  2. Ahora encuentre su registro de base de datos con WHERE id = 19158 y haga la redirección.

Algunas implementaciones (proporcionadas por los comentaristas)

  • Rubí
  • Pitón
  • CoffeeScript
  • Haskell
  • Perl
  • DO#

¿Por qué querrías usar un hash?
Solo puede usar una traducción simple de su valor de auto incremento a un valor alfanumérico. Puede hacerlo fácilmente usando alguna conversión base. Digamos que el espacio de caracteres (AZ, az, 0-9 etc. ‘) tiene 40 caracteres, convierte el ID a un número de base 40 y usa los caracteres son los 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; } } 

No es una respuesta a su pregunta, pero no usaría URL abreviadas que distingan entre mayúsculas y minúsculas. Son difíciles de recordar, generalmente ilegibles (muchas fonts representan 1 y 1, 0 y O y otros caracteres muy similares que son casi imposibles de diferenciar) y son francamente propensos a errores. Intente usar solo mayúsculas o minúsculas.

Además, intente tener un formato donde mezcle los números y los caracteres en una forma predefinida. Hay estudios que muestran que las personas tienden a recordar una forma mejor que otras (piense en los números de teléfono, donde los números se agrupan en una forma específica). Pruebe algo como num-char-char-num-char-char. Sé que esto reducirá las combinaciones, especialmente si no tiene mayúsculas y minúsculas, pero sería más útil y, por lo tanto, más útil.

Mi enfoque: Tome la ID de la base de datos, luego Base36 Codifíquela . NO usaría letras mayúsculas y minúsculas, porque eso hace que la transmisión de esas URL a través del teléfono sea una pesadilla, pero por supuesto podría ampliar fácilmente la función para que sea una base 62 en / decoder.

Aquí está mi clase 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; } } 

Podría hash toda la URL, pero si solo desea acortarla, haga lo que sugiera marcel. Escribí esta implementación de Python:

https://gist.github.com/778542

Versión 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 no quieres reinventar la rueda … 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 

Aquí está mi versión para quien lo necesite.

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

Una solución de nodo js y mongodb

Dado que conocemos el formato que mongodb usa para crear un nuevo ObjectId con 12 bytes.

  • un valor de 4 bytes que representa los segundos desde la época de Unix,
  • un identificador de máquina de 3 bytes,
  • un ID de proceso de 2 bytes
  • un contador de 3 bytes (en su máquina), comenzando con un valor aleatorio.

Ejemplo (elijo una secuencia aleatoria) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 representa los segundos desde la época de Unix,
  • 4e5f6g7 representa el identificador de la máquina,
  • h8i9 representa la identificación del proceso
  • j1k2l3 representa el contador, comenzando con un valor aleatorio.

Dado que el contador será único si almacenamos los datos en la misma máquina, podemos obtenerlo sin dudas de que será duplicado.

Entonces la URL corta será el contador y aquí hay un fragmento de código asumiendo que su servidor se está ejecutando correctamente.

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

Aquí hay una función decente de encoding URL 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; } 

No sé si a alguien le resultará útil; es más un método ‘hack n slash’, aunque es simple y funciona muy bien si solo quieres 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); } 

Sigo incrementando una secuencia de enteros por dominio en la base de datos y uso Hashids para codificar el entero en una ruta URL.

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

Ejecuté un script para ver cuánto tarda hasta que agota la longitud del personaje. Para 6 caracteres puede hacer 164,916,224 enlaces y luego sube a 7 caracteres. Bitly usa 7 caracteres. Menos de 5 caracteres me parece extraño.

Los Hashids pueden decodificar la ruta de la URL de vuelta a un número entero, pero una solución más simple es usar todo el enlace corto sho.rt/ka8ds3 como clave principal.

Aquí está el concepto 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 qué no simplemente traduces tu identificación a una cadena? Solo necesita una función que asigne un dígito entre, digamos, 0 y 61 a una sola letra (mayúscula / minúscula) o dígito. Luego, aplique esto para crear, por ejemplo, códigos de 4 letras, y tiene 14,7 millones de URL cubiertas.

Esto es lo que 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))]) 

Es muy rápido y puede tomar enteros largos.

Para un proyecto similar, para obtener una nueva clave, hago una función de envoltura alrededor de un generador de cadenas al azar que llama al generador hasta que obtengo una cadena que no se ha utilizado en mi hashtable. Este método se ralentizará una vez que su espacio de nombres comience a llenarse, pero como ha dicho, incluso con solo 6 caracteres, tiene mucho espacio de nombres para trabajar.

¿Omitiste O, 0, yo a propósito?

Acabo de crear una clase php basada en la solución de 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; } } ?>

Tengo una variante del problema, ya que almaceno páginas web de muchos autores diferentes y necesito evitar el descubrimiento de páginas por conjeturas. Así que mis URL cortas agregan un par de dígitos adicionales a la cadena Base-62 para el número de página. Estos dígitos adicionales se generan a partir de la información en el registro de la página y garantizan que solo 1 de cada 3844 URL sea válida (suponiendo Base-62 de 2 dígitos). Puede ver una descripción general en http://mgscan.com/MBWL .

Muy buena respuesta, he creado una implementación de 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 } 

Alojado en 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)); } }

Mi versión 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") 

Aquí está la implementación de Node.js que es probable que bit.ly. generar cadena de 7 caracteres altamente aleatoria. usando la criptografía Node.js para generar un juego de caracteres de 25 altamente aleatorio que selecciona al azar 7 caracteres.

 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 obtener una solución NodeJS / Javascript de calidad, consulte el módulo ID-acortador , que se ha probado exhaustivamente y se ha utilizado durante meses en la producción.

Proporciona un acortador id / url eficiente respaldado por almacenamiento enchufable predeterminado para redis , e incluso puede personalizar su conjunto corto de caracteres de identificación y si el acortamiento es idempotente . Esta es una distinción importante que no todos los acortadores de URL tienen en cuenta.

En relación con otras respuestas aquí, este módulo implementa la excelente respuesta aceptada de Marcel Jackwerth anteriormente.

El núcleo de la solución se proporciona mediante el siguiente fragmento de 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 

Implementación 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) } } 

Ejemplo de prueba con prueba de 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) } } 

Función basada en la clase 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; }