algorithm - personalizar - ¿Cómo creo un acortador de URL?

twitter url shortener (27)

Una solución Node.js y MongoDB

Como sabemos el formato que utiliza MongoDB 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 obtenerlos sin dudas de que se duplicarán.

Por lo tanto, la URL corta será el contador y aquí hay un fragmento de código que asume que su servidor se está ejecutando correctamente.

Quiero crear un servicio de acortador de URL donde puede escribir una URL larga en un campo de entrada y el servicio acorta la URL a " http://www.example.org/abcdef ".

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:

ID, entero, auto-incremento
long, string, la URL larga que ingresó el usuario
corto, cadena, la URL abreviada (o solo los seis caracteres)

Luego insertaría la URL larga en la tabla. Luego seleccionaría el valor de incremento automático para " id " y crearía un hash. Este hash debe ser insertado como " short ". Pero, ¿qué tipo de hash debería construir? Los algoritmos de hash como MD5 crean cadenas demasiado largas. No uso estos algoritmos, creo. Un algoritmo auto construido 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 a-z and A-Z.

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

_{Debido al interés continuo en este tema, he publicado una solución eficiente para GitHub , con implementaciones para JavaScript , PHP , Python y Java .} _{Añade tus soluciones si quieres :)}

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

Acabo de crear una clase de PHP basada en la solución 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 below. * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca * @see http://.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945 */ class App_Shorty { /** * Explicitly 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; } } ?>

¿Por qué no traducir tu id a una cadena? Solo necesita una función que asigne un dígito entre, por ejemplo, 0 y 61 a una sola letra (mayúscula / minúscula) o dígito. Luego aplique esto para crear, digamos, códigos de 4 letras, y ya tiene cubiertos 14.7 millones de URL.

¿Por qué querrías usar un hash?

Solo puede usar una traducción simple de su valor de incremento automático a un valor alfanumérico. Puedes 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 en un número base-40 y usa los caracteres como dígitos.

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

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

Aquí hay una implementación de Node.js que es probable que bit.ly. generar una cadena de siete caracteres altamente aleatorios.

Utiliza Node.js crypto para generar un juego de caracteres altamente aleatorio en lugar de seleccionar siete caracteres al azar.

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

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

Antecedentes teóricos

Necesitas una función biyectiva 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 para cada y debes poder encontrar una x para que f (x) = y .

Cómo convertir el ID a una URL acortada

Piensa en un alfabeto que queremos usar. En su caso, eso es [a-zA-Z0-9] . Contiene 62 letras .
Tome una clave numérica única, generada automáticamente (por ejemplo, la id incremento automático de una tabla MySQL).
Para este ejemplo usaré 125 ₁₀ (125 con una base de 10).
Ahora tienes que convertir 125 ₁₀ a X ₆₂ (base 62).
125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ = [2,1]
Esto requiere el uso de división entera y módulo. Un ejemplo de pseudocódigo:
digits = [] while num > 0 remainder = modulo(num, 62) digits.push(remainder) num = divide(num, 62) digits = digits.reverse
Ahora mapea los índices 2 y 1 a tu alfabeto. Así es como se vería tu asignación (con una matriz, por ejemplo):
0 → a 1 → b ... 25 → z ... 52 → 0 61 → 9
Con 2 → c y 1 → b, recibirá cb ₆₂ como la URL abreviada.
http://shor.ty/cb

Cómo resolver una URL acortada a la ID inicial

Lo contrario es aún más fácil. Usted acaba de hacer una búsqueda inversa en su alfabeto.

e9a ₆₂ se resolverá como "4ª, 61ª y 0ª letras en alfabeto".
e9a ₆₂ = [4,61,0] = 4 × 62 ² + 61 × 62 ¹ + 0 × 62 ⁰ = 19158 ₁₀
Ahora encuentre su base de datos con WHERE id = 19158 y haga la redirección.

Algunas implementaciones (proporcionadas por comentaristas)

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 llevar enteros largos.

Función basada en la clase Xeoncross

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

Mi enfoque: tomar el ID de la base de datos, luego Base36 codificarlo 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 extender fácilmente la función para que sea una base 62 en / decoder.

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

My Python 3 version

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

No es una respuesta a su pregunta, pero no usaría URL acortadas que distinguen entre mayúsculas y minúsculas. Son difíciles de recordar, generalmente ilegibles (muchas fuentes representan 1 y l, 0 y O y otros caracteres muy similares que son casi imposibles de notar) y son propensos a errores. Trate de usar mayúsculas o minúsculas solamente.

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 las cifras se agrupan en una forma específica). Intente 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, útil.

No sé si a alguien le resultará útil; es más bien un método de "barra y barra", pero es simple y funciona 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); }

Para obtener una solución Node.js / JavaScript de calidad, consulte el módulo de id-shortener , que se ha probado exhaustivamente y se ha utilizado en la producción durante meses.

Proporciona un acortador id / URL eficiente respaldado por el almacenamiento conectable que se establece de manera predeterminada en Redis , e incluso puede personalizar el conjunto de caracteres de id corto y si el acortamiento es idempotente o no. 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 arriba.

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

Para un proyecto similar, para obtener una nueva clave, hago una función de envoltorio alrededor de un generador de cadenas aleatorias que llama al generador hasta que obtengo una cadena que no se ha utilizado en mi tabla hash. 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 un montón de espacio de nombres para trabajar.

Podría codificar la URL completa, pero si solo desea acortar la identificación, haga lo que marcel sugirió. Escribí esta implementación de Python:

Python

Si no quieres reinventar la rueda ... http://lilurl.sourceforge.net/

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

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

Ejecuté un script para ver cuánto tiempo se tarda en agotar la longitud del carácter. Para seis caracteres puede hacer 164,916,224 enlaces y luego sube a siete caracteres. Bitly utiliza siete caracteres. Menos de cinco personajes me parece raro.

Hashids puede decodificar la ruta URL de nuevo a un 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) }

Tengo una variante del problema, ya que almaceno páginas web de diferentes autores 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 aseguran que solo 1 en 3844 URL son válidas (suponiendo 2-Base-62 dígitos). Puede ver una descripción del esquema en http://mgscan.com/MBWL .

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

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

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

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

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 la necesite.