Como crio um encurtador de URL?

667

Desejo criar um serviço de encurtador de URL em que você possa gravar um URL longo em um campo de entrada e o serviço encurte o URL para " http://www.example.org/abcdef".

Em vez de " abcdef", pode haver qualquer outra sequência com seis caracteres a-z, A-Z and 0-9. Isso torna 56 a 57 bilhões de strings possíveis.

Minha abordagem:

Eu tenho uma tabela de banco de dados com três colunas:

  1. id, número inteiro, incremento automático
  2. long, string, o URL longo digitado pelo usuário
  3. short, string, o URL encurtado (ou apenas os seis caracteres)

Em seguida, insiro o URL longo na tabela. Depois, selecionaria o valor de incremento automático para " id" e criaria um hash. Esse hash deve ser inserido como " short". Mas que tipo de hash devo construir? Algoritmos de hash como MD5 criam seqüências muito longas. Eu não uso esses algoritmos, eu acho. Um algoritmo auto-construído também funcionará.

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 a-z and A-Z.

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

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 quiser :)

caw
fonte
5
@gudge O objetivo dessas funções é que elas têm uma função inversa. Isso significa que você pode ter ambas encode()e decode()funções. As etapas são, portanto: (1) Salvar URL no banco de dados (2) Obter ID de linha exclusivo para esse URL do banco de dados (3) Converter o número inteiro em string curta com encode(), por exemplo, 273984para f5a4(4) Use a string curta (por exemplo f4a4) em seu URLs compartilháveis ​​(5) Ao receber uma solicitação de uma sequência curta (por exemplo 20a8), decodifique a sequência para um ID inteiro com decode()(6) Procure URL no banco de dados para o ID fornecido. Para conversão, use: github.com/delight-im/ShortURL
caw
@Marco, qual é o sentido de armazenar o hash no banco de dados?
Maksim Vi.
3
@MaksimVi. Se você tem uma função invertível, não há nenhuma. Se você tivesse uma função de hash unidirecional, haveria uma.
caw
1
seria errado se usássemos o algoritmo CRC32 simples para encurtar uma URL? Embora seja muito improvável uma colisão (uma saída CRC32 geralmente tem 8 caracteres e isso nos dá mais de 30 milhões de possibilidades). Se uma saída CRC32 gerada já foi usada anteriormente e foi encontrada no banco de dados, podemos salgar o URL longo com um número aleatório até encontrarmos uma saída CRC32 única no meu banco de dados. Quão ruim, diferente ou feio isso seria para uma solução simples?
Rakib

Respostas:

816

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

Bases teóricas

Você precisa de uma função bijetiva f . Isso é necessário para que você possa encontrar uma função inversa g ('abc') = 123 para sua função 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 para que f (x) = y .

Como converter o ID em um URL reduzido

  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 exclusiva gerada automaticamente (o incremento automático idde uma tabela MySQL, por exemplo).

    Neste exemplo, usarei 125 10 (125 com uma base de 10).

  3. Agora você deve 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 pseudo-có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 seu mapeamento (com uma matriz por exemplo) pode parecer:

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

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

    http://shor.ty/cb
    

Como resolver um URL reduzido para o ID inicial

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

  1. e9a 62 será resolvido como "quarta, 61 e 0a letra do alfabeto".

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

  2. Agora encontre seu registro no banco de dados WHERE id = 19158e faça o redirecionamento.

Implementações de exemplo (fornecidas por comentaristas)

Marcel Jackwerth
fonte
18
Não se esqueça de limpar os URLs para código javascript malicioso! Lembre-se de que o Javascript pode ser base64 codificado em uma URL então basta procurar por 'javascript' não é bom enough.j
Bjorn
3
Uma função deve ser bijetiva (injetiva e sujetiva) para ter uma inversa.
Gumbo
57
Pensando bem, pode ser útil adicionar uma soma de verificação de dois caracteres ao URL. Isso impediria a iteração direta de todos os URLs no seu sistema. Algo simples como f (soma de verificação (ID)% (62 ^ 2)) + F (id) = url_id
Koblas
6
No que diz respeito à higienização dos URLs, um dos problemas que você enfrentará são os remetentes de spam que usam seu serviço para mascarar seus URLs e evitar filtros de spam. Você precisa limitar o serviço a bons atores conhecidos ou aplicar a filtragem de spam aos URLs longos. Caso contrário, você será abusado por spammers.
Edward Falk
74
Base62 pode ser uma péssima escolha, pois tem o potencial de gerar f * palavras (por exemplo, 3792586=='F_ck'com u no lugar de _). Eu excluiria alguns caracteres como u / U para minimizar isso.
Paulo Scardine
56

Por que você gostaria de usar um hash?

Você pode apenas usar uma tradução simples do seu valor de incremento automático para um valor alfanumérico. Você pode fazer isso facilmente usando algumas conversões básicas. Digamos que o espaço de caracteres (AZ, az, 0-9 etc.) tenha 40 caracteres, converta o ID em um número de base 40 e use os caracteres como dígitos.

shoosh
fonte
13
além do fato de que AZ, az e 0-9 = 62 caracteres, e não 40, você está certo.
Evan Teran
Obrigado! Devo usar o alfabeto base 62 então? pt.wikipedia.org/wiki/Base_62 Mas como posso converter os IDs em um número de base 62?
caw
Usando um algoritmo de conversão de base é claro - en.wikipedia.org/wiki/Base_conversion#Change_of_radix
shoosh
2
Em relação a "Por que você deseja usar um hash?", Uma conversão básica com base no incremento automático criará URLs sequenciais; portanto, você deve se sentir confortável com as pessoas capazes de "navegar" pelos URLs encurtados de outras pessoas, direita?
Andrew Coleson
2
com recursos e tempo suficientes, você pode "navegar" em todos os URLs de qualquer serviço de redução de URL.
shoosh
51
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;
    }   
}
Stradivariuz
fonte
Eu realmente gosto da idéia, o único problema que tenho com ela é que eu continuo recebendo a variável num na função de decodificação fora dos limites (mesmo por muito tempo), você tem alguma idéia de como fazê-la funcionar? ou é apenas teórico?
User1322801
@ user1322801: Presumivelmente, você está tentando decodificar algo muito maior do que aquilo que a função de codificação pode realmente suportar. Você poderia obter mais milhas se convertesse todas as "ints" em BigInteger, mas, a menos que você tenha índices> 9223372036854775807, provavelmente deve ser suficiente.
Biggusjimmus
2
Posso saber qual é a importância de reverter? ou seja, sb.reverse (). toString ();
dotNet Decoder
São 62 ^ 62 = 1,7 trilhão?
Noah Tony
33

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

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

Cinza
fonte
2
Obrigado, muito boa ideia. Ainda não pensei nisso. É claro que depende do tipo de uso, se faz sentido ou não.
caw
19
Não será um problema se as pessoas copiarem e colarem estritamente os URLs curtos.
Edward Falk
2
O objetivo dos URLs curtos não é ser memorável ou fácil de falar. É apenas clicar ou copiar / colar.
Hugo Nogueira
Sim, eu pensei que o URL curto é apenas para as pessoas listá-lo ou enviá-lo por e-mail, por isso é curto e não ocupa 200 caracteres, como alguns URLs fazem, por isso, caso não seja um problema
polaridade
29

Minha abordagem: pegue o ID do banco de dados e, em seguida, o Base36 o codifique . Eu NÃO usaria letras maiúsculas e minúsculas, porque isso torna a transmissão desses URLs por telefone um pesadelo, mas é claro que você poderia estender facilmente a função para ser um decodificador / en base de 62.

Michael Stum
fonte
Obrigado, você está certo. Se você tem 2.176.782.336 possibilidades ou 56.800.235.584, é a mesma coisa: ambas serão suficientes. Então, eu vou usar a codificação base 36.
caw
Pode ser óbvio, mas aqui é algum código PHP referenciado na wikipedia para fazer base64 codificar em php tonymarston.net/php-mysql/converter.html
Ryan White
8

Aqui está minha 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;
    }
}
Xeoncross
fonte
6

Uma solução Node.js e MongoDB

Como sabemos o formato que o MongoDB usa para criar um novo ObjectId com 12 bytes.

  • um valor de 4 bytes que representa 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 aleatório.

Exemplo (escolho uma sequência aleatória) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 representa os segundos desde a época do Unix,
  • 4e5f6g7 representa o identificador da máquina,
  • h8i9 representa a identificação do processo
  • j1k2l3 representa o contador, começando com um valor aleatório.

Como o contador será único se estivermos armazenando os dados na mesma máquina, podemos obtê-los sem dúvida de que serão duplicados.

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");
    })
});
Firas Omrane
fonte
1
Como um RDBMS seria melhor que um armazenamento no-sql / key-value?
kjs3 6/06
@ kjs3 sim, você está certo, já que não há relações com outras tabelas, não há necessidade de um RDBMS e um armazenamento de valores-chave será mais rápido.
Firas Omrane 07/06
4

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;
    }   
}
user1477388
fonte
4

Você pode fazer o hash do URL inteiro, mas se quiser apenas diminuir o ID, faça o que Marcel sugeriu. Eu escrevi esta implementação Python:

https://gist.github.com/778542

bhelx
fonte
4

Continuo incrementando uma sequência inteira por domínio no banco de dados e uso Hashids para codificar o número inteiro em um caminho de URL.

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

Eu executei um script para ver quanto tempo leva até esgotar o tamanho dos caracteres. Para seis caracteres, ele pode 164,916,224criar links e depois subir para sete caracteres. Bitly usa sete caracteres. Menos de cinco caracteres me parecem estranhos.

Hashids 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/ka8ds3como 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)
}
AJcodez
fonte
3

Se você não quiser reinventar a roda ... http://lilurl.sourceforge.net/

Alister Bulman
fonte
1
"Desculpe, parece que os spammers chegaram a isso. Tente tinyurl."
takeshin
para o site de demonstração. O código fonte ainda pode ser baixado no Sourceforge.
Alister Bulman
3
// simple approach

$original_id = 56789;

$shortened_id = base_convert($original_id, 10, 36);

$un_shortened_id = base_convert($shortened_id, 36, 10);
phirschybar
fonte
2
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 precisar.

MrChrisRodriguez
fonte
1

Por que não apenas traduzir seu ID para uma string? Você só precisa de uma função 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 4 letras, e você terá 14,7 milhões de URLs cobertos.

cr333
fonte
+1 para o pensamento simplista. É realmente muito simples. Acabei de publicar uma resposta que está fazendo exatamente isso. Eu tenho algum código de produção que consulta o banco de dados para garantir que não haja seqüências de caracteres duplicadas e que tudo seja exclusivo.
Andrew Reese
1

Aqui está uma função 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;
}
Simon East
fonte
1

Não sei se alguém achará isso útil - é mais um método 'hack n slash', mas é simples e funciona bem se você deseja 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);
} 
Ryan Charmley
fonte
1

Você omitiu O, 0 e i de propósito?

Acabei de criar uma classe PHP baseada na solução 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 Stack Overflow 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 {
        /**
         * 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;
        }
    }
?>
Svetoslav Marinov
fonte
Sim. Você viu o comentário logo abaixo da declaração de classe?
Svetoslav Marinov
1

Dê uma olhada em https://hashids.org/ , é de código aberto e em vários idiomas.

A página deles descreve algumas das armadilhas de outras abordagens.

John
fonte
0

Isto é 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 números inteiros longos.

Davide Muzzarelli
fonte
0

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

Joel Berger
fonte
Essa abordagem funcionou para você a longo prazo?
31516 Chris
Para ser honesto, eu não tenho idéia de qual projeto eu estava me referindo não :-P
Joel Berger
0

Tenho uma variante do problema, pois 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álidas (considerando a Base 62 de 2 dígitos). Você pode ver uma descrição geral em http://mgscan.com/MBWL .

Graham
fonte
0

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

Jerry Jacobs
fonte
0
/**
 * <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));
    }
}
Hrishikesh Mishra
fonte
0

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

}
à deriva
fonte
0

Função baseada na classe 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;
}
Luis Neighbur
fonte
0

Aqui está uma implementação do Node.js. que provavelmente bit.ly. gerar uma cadeia de sete caracteres altamente aleatória.

Ele usa a criptografia Node.js para gerar um conjunto de caracteres 25 altamente aleatório, em vez de selecionar aleatoriamente sete 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;
    };
}
Hafiz Arslan
fonte
O que você quer dizer com "bit.ly". ?
Peter Mortensen
0

Minha versão do Python 3

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")
wyx
fonte
0

Para obter uma solução de qualidade Node.js / JavaScript, consulte o módulo de identificação-encurtador , que é exaustivamente testado e usado na produção há meses.

Ele fornece um encurtador de ID / URL eficiente, apoiado por armazenamento conectável com o padrão Redis , e você pode até personalizar seu conjunto de caracteres de ID curto e se o encurtamento é ou não idempotente . Essa é uma distinção importante que nem todos os encurtadores de URL 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 do 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
fisch2
fonte
0

Por que não gerar uma sequência aleatória e anexá-la ao URL base? Esta é uma versão muito simplificada de fazer isso em c # .

static string chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
static string baseUrl = "https://google.com/";

private static string RandomString(int length)
{
    char[] s = new char[length];
    Random rnd = new Random();
    for (int x = 0; x < length; x++)
    {
        s[x] = chars[rnd.Next(chars.Length)];
    }
    Thread.Sleep(10);

    return new String(s);
}

Em seguida, basta adicionar a sequência aleatória à baseURL:

string tinyURL = baseUrl + RandomString(5);

Lembre-se de que esta é uma versão muito simplificada de fazer isso e é possível que o método RandomString possa criar seqüências de caracteres duplicadas. Na produção, você deve considerar as seqüências de caracteres duplicadas para garantir que sempre tenha um URL exclusivo. Eu tenho algum código que leva em conta seqüências de caracteres duplicadas, consultando uma tabela de banco de dados que eu poderia compartilhar se alguém estiver interessado.

Andrew Reese
fonte
0

Este é o meu pensamento inicial, e mais pensamentos podem ser feitos, ou alguma simulação pode ser feita para verificar se funciona bem ou se é necessária alguma melhoria:

Minha resposta é lembrar a URL longa no banco de dados e usar o ID 0para 9999999999999999(ou por maior que seja o número necessário).

Mas o ID 0 para 9999999999999999pode ser um problema, porque

  1. pode ser mais curto se usarmos hexadecimal, ou mesmo base62 ou base64. (base64, assim como o YouTube, usando A- Z a- z 0- 9 _e- )
  2. se aumenta a partir 0de 9999999999999999uniformemente, em seguida, os hackers podem visitá-los nessa ordem e saber o que URLs pessoas estão enviando uns aos outros, por isso pode ser uma questão de privacidade

Nós podemos fazer isso:

  1. tem um servidor alocado 0para999 um servidor, o Servidor A, agora o Servidor A possui 1000 desses IDs. Portanto, se houver 20 ou 200 servidores constantemente querendo novos IDs, ele não precisará continuar pedindo cada novo ID, mas sim pedindo 1000 IDs uma vez.
  2. para o ID 1, por exemplo, inverta os bits. Assim , 000...00000001torna-se 10000...000, de modo que, quando convertido em base64, aumentará de maneira não uniforme os IDs a cada vez.
  3. use XOR para inverter os bits para os IDs finais. Por exemplo, XOR com 0xD5AA96...2373(como uma chave secreta) e alguns bits serão invertidos. (sempre que a chave secreta estiver com 1 bit ativado, ela mudará a parte do ID). Isso tornará os IDs ainda mais difíceis de adivinhar e parecerá mais aleatório

Seguindo esse esquema, o servidor único que aloca os IDs pode formar os IDs, assim como os 20 ou 200 servidores que solicitam a alocação de IDs. O servidor de alocação precisa usar um bloqueio / semáforo para impedir que dois servidores solicitantes obtenham o mesmo lote (ou, se estiver aceitando uma conexão por vez, isso já resolve o problema). Portanto, não queremos que a linha (fila) seja muito longa para aguardar uma alocação. É por isso que alocar 1000 ou 10000 por vez pode resolver o problema.

falta de polaridade
fonte