Jak utworzyć skracacz URL?

667

Chcę utworzyć usługę skracania adresów URL, w której możesz wpisać długi adres URL w polu wejściowym, a usługa skróci adres URL do „ http://www.example.org/abcdef”.

Zamiast „ abcdef” może znajdować się dowolny ciąg zawierający sześć znaków a-z, A-Z and 0-9. To daje 56 ~ 57 miliardów możliwych ciągów.

Moje podejście:

Mam tabelę bazy danych z trzema kolumnami:

  1. id, liczba całkowita, auto-inkrement
  2. długi, ciąg, długi URL podany przez użytkownika
  3. krótki, ciąg znaków, skrócony adres URL (lub tylko sześć znaków)

Następnie wstawiłbym długi adres URL do tabeli. Następnie wybrałbym wartość automatycznego przyrostu dla „ id” i zbudowałem jej skrót. Ten skrót należy następnie wstawić jako „ short”. Ale jaki hash powinienem zbudować? Algorytmy skrótu, takie jak MD5, tworzą zbyt długie ciągi znaków. Myślę, że nie używam tych algorytmów. Algorytm samokonstruujący również będzie działał.

Mój pomysł:

Dla „ http://www.google.de/” otrzymuję identyfikator automatycznego przyrostu 239472. Następnie wykonuję następujące kroki:

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.

Można to powtarzać, dopóki liczba nie będzie już podzielna. Czy uważasz, że to dobre podejście? Czy masz lepszy pomysł?

Ze względu na ciągłe zainteresowanie tym tematem opublikowałem wydajne rozwiązanie dla GitHub , z implementacjami dla JavaScript , PHP , Python i Java . Dodaj swoje rozwiązania, jeśli chcesz :)

krakanie
źródło
5
@udge Istotą tych funkcji jest to, że mają one funkcję odwrotną. Oznacza to, że możesz mieć obie funkcje encode()i decode()funkcje. Kroki są zatem następujące: (1) Zapisz adres URL w bazie danych (2) Uzyskaj unikalny identyfikator wiersza dla tego adresu URL z bazy danych (3) Konwertuj liczbę całkowitą na krótki ciąg encode(), np. 273984Na f5a4(4) Użyj krótkiego ciągu (np. f4a4) W swoim współdzielone adresy URL (5) Po otrzymaniu żądania krótkiego ciągu (np. 20a8) dekoduj ciąg do identyfikatora liczb całkowitych za pomocą decode()(6) Wyszukaj adres URL w bazie danych dla danego identyfikatora. Do konwersji użyj: github.com/delight-im/ShortURL
caw
@Marco, jaki jest sens przechowywania skrótu w bazie danych?
Maksim Vi.
3
@MaksimVi. Jeśli masz funkcję odwracalną, nie ma żadnej. Gdybyś miał jednokierunkową funkcję skrótu, byłaby taka.
caw
1
czy byłoby źle, gdybyśmy użyli prostego algorytmu CRC32 do skrócenia adresu URL? Chociaż bardzo mało prawdopodobne jest zderzenie (wyjście CRC32 ma zwykle 8 znaków, co daje nam ponad 30 milionów możliwości). Jeśli wygenerowane wyjście CRC32 było już wcześniej używane i znaleziono je w bazie danych, moglibyśmy zasolić długi adres URL losową liczbą dopóki nie znajdziemy wyjścia CRC32, które jest unikalne w mojej bazie danych. Jak źle, inaczej czy brzydko byłoby dla prostego rozwiązania?
Rakib

Odpowiedzi:

816

Chciałbym kontynuować twoje podejście do konwersji liczby na ciąg znaków. Jednak zdasz sobie sprawę, że zaproponowany algorytm zawiedzie, jeśli Twój identyfikator jest liczbą pierwszą i większą niż 52 .

Podłoże teoretyczne

Potrzebujesz funkcji Bijective f . Jest to konieczne, aby znaleźć funkcję odwrotną g („abc”) = 123 dla funkcji f (123) = „abc” . To znaczy:

  • Nie może być żadnych x1, x2 (z x1 ≠ x2), które spowodują, że f (x1) = f (x2) ,
  • i dla każdego y musisz znaleźć x , aby f (x) = y .

Jak przekonwertować identyfikator na skrócony adres URL

  1. Pomyśl o alfabecie, którego chcemy użyć. W twoim przypadku tak jest [a-zA-Z0-9]. Zawiera 62 litery .
  2. Weź automatycznie wygenerowany, unikalny klucz numeryczny (na przykład automatyczne zwiększenie idtabeli MySQL).

    W tym przykładzie użyję 125 10 (125 z podstawą 10).

  3. Teraz musisz przekonwertować 125 10 na X 62 (baza 62).

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

    Wymaga to użycia podziału na liczby całkowite i modulo. Przykład pseudokodu:

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

    Teraz zmapuj indeksy 2 i 1 do swojego alfabetu. Tak mogłoby wyglądać twoje mapowanie (na przykład z tablicą):

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

    Przy 2 → ci 1 → b otrzymasz cb 62 jako skrócony adres URL.

    http://shor.ty/cb
    

Jak rozwiązać skrócenie adresu URL do początkowego identyfikatora

Odwrotna sytuacja jest jeszcze łatwiejsza. Po prostu odwróć alfabet.

  1. e9a 62 zostanie przetłumaczona na „4, 61 i 0 litera alfabetu”.

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

  2. Teraz znajdź swój rekord bazy danych WHERE id = 19158i przekieruj.

Przykładowe implementacje (dostarczone przez komentujących)

Marcel Jackwerth
źródło
18
Nie zapomnij wyczyścić adresów URL złośliwego kodu javascript! Pamiętaj, że javascript może być zakodowany w formacie base64 w adresie URL, więc samo wyszukiwanie „javascript” nie jest wystarczająco dobre. J
Bjorn
3
Funkcja musi być bijectywna (iniekcyjna i przymiotnikowa), aby mieć odwrotność.
Gumbo
57
Zastanów się, warto dodać do adresu URL dwuznakową sumę kontrolną. Zapobiegnie to bezpośredniej iteracji wszystkich adresów URL w systemie. Coś prostego, na przykład f (suma kontrolna (id)% (62 ^ 2)) + f (id) = identyfikator url
koblas,
6
Jeśli chodzi o odkażanie adresów URL, jednym z problemów, z którymi będziesz musiał się zmierzyć, są spamerzy używający twojej usługi do maskowania swoich adresów URL w celu uniknięcia filtrów spamu. Musisz ograniczyć usługę do znanych dobrych aktorów lub zastosować filtrowanie spamu do długich adresów URL. W przeciwnym razie spamerzy będą wykorzystywani.
Edward Falk
74
Base62 może być złym wyborem, ponieważ ma potencjał do generowania f * słów (na przykład 3792586=='F_ck'z u zamiast _). Wykluczę niektóre znaki, takie jak u / U, aby to zminimalizować.
Paulo Scardine
56

Dlaczego miałbyś chcieć użyć skrótu?

Możesz po prostu użyć prostego tłumaczenia wartości auto-przyrostu na wartość alfanumeryczną. Możesz to łatwo zrobić za pomocą konwersji bazowej. Powiedzmy, że przestrzeń znaków (AZ, az, 0-9 itd.) Ma 40 znaków, przekonwertuj identyfikator na liczbę podstawową 40 ​​i użyj znaków jako cyfr.

buta
źródło
13
poza tym, że AZ, az i 0-9 = 62 znaki, a nie 40, masz rację.
Evan Teran,
Dzięki! Czy powinienem używać alfabetu base-62? en.wikipedia.org/wiki/Base_62 Ale jak mogę przekonwertować identyfikatory na numer base-62?
caw
Korzystanie z podstawowego algorytmu konwersji oczywiście - en.wikipedia.org/wiki/Base_conversion#Change_of_radix
shoosh
2
Jeśli chodzi o „Dlaczego chcesz użyć skrótu?”, Podstawowa konwersja oparta na automatycznym zwiększaniu będzie tworzyć kolejne adresy URL, więc musisz czuć się swobodnie, gdy ludzie będą mogli „przeglądać” skrócone adresy URL innych osób, dobrze?
Andrew Coleson
2
z wystarczającą ilością zasobów i czasu możesz „przeglądać” wszystkie adresy URL dowolnej usługi skracania adresów 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
źródło
Naprawdę podoba mi się ten pomysł, jedynym problemem, jaki mam z tym, jest to, że ciągle wypuszczam zmienną num w funkcji dekodowania poza granice (nawet na długo), czy masz jakiś pomysł, jak to zrobić? czy jest to tylko teoretyczne?
user1322801
@ user1322801: Prawdopodobnie próbujesz zdekodować coś, co było znacznie większe niż to, co faktycznie może obsłużyć funkcja kodowania. Możesz z niego uzyskać więcej przebiegów, jeśli przekonwertujesz wszystkie „ints” na BigInteger, ale jeśli nie masz> 9223372036854775807 indeksów, prawdopodobnie powinno wystarczyć.
biggusjimmus,
2
Czy mogę wiedzieć, jakie znaczenie ma cofanie? tj. sb.reverse (). toString ();
Dekoder dotNet
Czy to 62 ^ 62 = 1,7 biliona?
Noah Tony
33

Nie jest to odpowiedź na twoje pytanie, ale nie używałbym skróconych adresów URL z rozróżnianiem wielkości liter. Są trudne do zapamiętania, zwykle nieczytelne (wiele czcionek renderuje 1 i 1, 0 i O oraz inne znaki bardzo bardzo podobne, że prawie niemożliwe jest ich odróżnienie) i wręcz podatne na błędy. Staraj się używać tylko małych lub wielkich liter.

Spróbuj także mieć format, w którym zmieszane są liczby i znaki we wstępnie zdefiniowanej formie. Istnieją badania, które pokazują, że ludzie zapamiętują jedną formę lepiej niż inne (pomyśl numery telefonów, gdzie numery są pogrupowane w określonej formie). Spróbuj czegoś takiego jak num-char-char-num-char-char. Wiem, że to obniży kombinacje, szczególnie jeśli nie masz wielkich i małych liter, ale byłoby bardziej użyteczne i dlatego przydatne.

Popiół
źródło
2
Dziękuję bardzo dobry pomysł. Jeszcze o tym nie myślałem. Oczywiste jest, że zależy to od rodzaju zastosowania, czy ma to sens, czy nie.
caw
19
Nie będzie problemu, jeśli ludzie będą ściśle kopiować i wklejać krótkie adresy URL.
Edward Falk
2
Krótki adres URL nie ma na celu zapominania ani łatwego mówienia. To tylko kliknij lub skopiuj / wklej.
Hugo Nogueira,
tak, myślałem, że krótki adres URL jest tylko dla ludzi, aby go wymienić lub wysłać e-mailem, więc jest krótki i nie może zająć 200 znaków, jak niektóre adresy URL, więc sprawa nie stanowi problemu
nonpolarity
29

Moje podejście: weź identyfikator bazy danych, a następnie zakoduj go w Base36 . NIE użyłbym zarówno wielkich, jak i małych liter, ponieważ to sprawia, że ​​przesyłanie tych adresów URL przez telefon jest koszmarem, ale oczywiście można łatwo rozszerzyć tę funkcję na podstawową en / dekoder.

Michael Stum
źródło
Dzięki, masz rację. Niezależnie od tego, czy masz 2176 782 336 możliwości, czy 56 800 235 584, to samo: oba będą wystarczające. Użyję więc kodowania podstawowego 36.
caw
Może to być oczywiste, ale oto kod PHP, do którego odwołuje się wikipedia, aby wykonać kodowanie base64 w php tonymarston.net/php-mysql/converter.html
Ryan White
8

Oto moja klasa 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
źródło
6

Rozwiązanie Node.js i MongoDB

Ponieważ wiemy, jakiego formatu używa MongoDB do utworzenia nowego obiektu ObjectId z 12 bajtami.

  • 4-bajtowa wartość reprezentująca sekundy od epoki Uniksa,
  • 3-bajtowy identyfikator maszyny,
  • 2-bajtowy identyfikator procesu
  • 3-bajtowy licznik (w twoim komputerze), zaczynający się od losowej wartości.

Przykład (wybieram losową sekwencję) a1b2c3d4e5f6g7h8i9j1k2l3

  • a1b2c3d4 reprezentuje sekundy od epoki Uniksa,
  • 4e5f6g7 reprezentuje identyfikator maszyny,
  • h8i9 reprezentuje identyfikator procesu
  • j1k2l3 reprezentuje licznik, zaczynając od wartości losowej.

Ponieważ licznik będzie unikalny, jeśli przechowujemy dane na tej samej maszynie, możemy je uzyskać bez wątpienia, że ​​zostaną zduplikowane.

Tak więc krótki adres URL będzie licznikiem, a oto fragment kodu przy założeniu, że serwer działa poprawnie.

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
źródło
1
W jaki sposób RDBMS byłby lepszy niż magazyn bez klucza / wartości kluczowej?
kjs3
@ kjs3 tak masz rację, ponieważ nie ma relacji z innymi tabelami, nie ma potrzeby korzystania z RDBMS, a magazyn wartości klucza będzie szybszy.
Firas Omrane
4

Wersja 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;
    }   
}
użytkownik1477388
źródło
4

Możesz haszować cały adres URL, ale jeśli chcesz tylko skrócić identyfikator, postępuj zgodnie z sugestią Marcel. Napisałem tę implementację Pythona:

https://gist.github.com/778542

bhelx
źródło
4

Wciąż zwiększam sekwencję liczb całkowitych dla domeny w bazie danych i używam Hashids do kodowania liczb całkowitych w ścieżce URL.

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

Uruchomiłem skrypt, aby zobaczyć, ile czasu zajmuje mu wyczerpanie długości znaku. W przypadku sześciu znaków może tworzyć 164,916,224linki, a następnie dochodzi do siedmiu znaków. Bitly używa siedmiu znaków. Poniżej pięciu znaków wygląda dla mnie dziwnie.

Hashids mogą dekodować ścieżkę URL z powrotem do liczby całkowitej, ale prostszym rozwiązaniem jest użycie całego krótkiego linkusho.rt/ka8ds3 jako klucza podstawowego.

Oto pełna koncepcja:

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
źródło
3

Jeśli nie chcesz na nowo wynajdować koła ... http://lilurl.sourceforge.net/

Alister Bulman
źródło
1
„Przepraszam, wygląda na to, że spamerzy się tym zajęli. Zamiast tego spróbuj tinyurl”.
trwa
na stronie demonstracyjnej. Kod źródłowy nadal można pobrać z 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
źródło
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

Oto moja wersja dla każdego, kto jej potrzebuje.

MrChrisRodriguez
źródło
1

Dlaczego nie po prostu przetłumaczyć swojego identyfikatora na ciąg? Potrzebujesz tylko funkcji, która odwzorowuje cyfrę między, powiedzmy, 0 a 61 na pojedynczą literę (wielkie / małe litery) lub cyfrę. Następnie zastosuj to, aby utworzyć, powiedzmy, 4-literowe kody, a otrzymasz 14,7 miliona adresów URL.

cr333
źródło
+1 za uproszczone myślenie. To naprawdę jest takie proste. Właśnie opublikowałem odpowiedź, która właśnie to robi. Mam kod produkcyjny, który odpytuje bazę danych, aby upewnić się, że nie ma zduplikowanych ciągów, a wszystko jest unikalne.
Andrew Reese,
1

Oto przyzwoita funkcja kodowania adresów URL dla 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
źródło
1

Nie wiem, czy ktokolwiek uzna to za przydatne - jest to raczej metoda „hack n slash”, ale jest prosta i działa dobrze, jeśli chcesz tylko określonych znaków.

$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
źródło
1

Czy celowo ominąłeś O, 0 i ja?

Właśnie stworzyłem klasę PHP opartą na rozwiązaniu Ryana.

<?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
źródło
Tak. Czy widziałeś komentarz tuż pod deklaracją klasy?
Svetoslav Marinov,
1

Spójrz na https://hashids.org/ jest to oprogramowanie typu open source w wielu językach.

Ich strona przedstawia niektóre pułapki innych podejść.

Jan
źródło
0

Oto, czego używam:

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

Jest bardzo szybki i może zająć długie liczby całkowite.

Davide Muzzarelli
źródło
0

W przypadku podobnego projektu, aby uzyskać nowy klucz, uruchamiam funkcję otoki wokół losowego generatora ciągów, który wywołuje generator, dopóki nie otrzymam ciągu, który nie był jeszcze używany w mojej tablicy mieszającej. Ta metoda zwolni, gdy przestrzeń nazw zacznie się zapełniać, ale jak już powiedziałeś, nawet z zaledwie 6 znakami, masz mnóstwo przestrzeni nazw do pracy.

Joel Berger
źródło
Czy to podejście sprawdziło się na dłuższą metę?
Chris
Szczerze mówiąc, nie mam pojęcia, do którego projektu się tam odnosiłem :-P
Joel Berger
0

Mam wariant problemu, polegający na tym, że przechowuję strony internetowe wielu różnych autorów i muszę zapobiegać wykrywaniu stron przez zgadywanie. Więc moje krótkie adresy URL dodają kilka dodatkowych cyfr do ciągu Base-62 dla numeru strony. Te dodatkowe cyfry są generowane z informacji w samym rekordzie strony i zapewniają, że tylko 1 na 3844 adresów URL jest prawidłowy (przy założeniu 2-cyfrowej wartości Base-62). Ogólny opis można zobaczyć na stronie http://mgscan.com/MBWL .

Graham
źródło
0

Bardzo dobra odpowiedź, stworzyłem implementację bjf w Golang:

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
}

Hostowane na github: https://github.com/xor-gate/go-bjf

Jerry Jacobs
źródło
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
źródło
0

Wdrożenie w Scali:

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

Przykład testu z testem 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)
  }

}
dryfujący
źródło
0

Funkcja oparta na klasie 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
źródło
0

Oto implementacja Node.js, która prawdopodobnie jest bit.ly. generuje wysoce losowy ciąg siedmiu znaków.

Wykorzystuje krypto Node.js do generowania wysoce losowego zestawu znaków 25 zamiast losowego wybierania siedmiu znaków.

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
źródło
Co rozumiesz przez „bit.ly”. ?
Peter Mortensen
0

Moja wersja 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
źródło
0

Aby uzyskać wysokiej jakości rozwiązanie Node.js / JavaScript, zobacz moduł id-shortener , który został dokładnie przetestowany i był używany w produkcji od miesięcy.

Zapewnia efektywne skrócenie identyfikatora / adresu URL wspierane przez pamięć wtykową domyślnie ustawioną na Redis , a nawet można dostosować zestaw znaków krótkiego identyfikatora i określić, czy skrócenie jest idempotentne . Jest to ważne rozróżnienie, które nie wszystkie skracacze URL biorą pod uwagę.

W odniesieniu do innych odpowiedzi tutaj, moduł ten implementuje doskonale przyjętą powyżej odpowiedź Marcela Jackwertha.

Rdzeń rozwiązania zapewnia następujący fragment 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
źródło
0

Dlaczego po prostu nie wygenerować losowego ciągu i dołączyć go do podstawowego adresu URL? Jest to bardzo uproszczona wersja robienia tego w języku 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);
}

Następnie po prostu dodaj ciąg losowy do baseURL:

string tinyURL = baseUrl + RandomString(5);

Pamiętaj, że jest to bardzo uproszczona wersja robienia tego i jest możliwe, że metoda RandomString może tworzyć duplikaty ciągów. W produkcji należy wziąć pod uwagę zduplikowane ciągi, aby mieć zawsze unikalny adres URL. Mam kod, który bierze pod uwagę zduplikowane ciągi, poprzez zapytanie do tabeli bazy danych, którą mógłbym udostępnić, jeśli ktoś jest zainteresowany.

Andrew Reese
źródło
0

Oto moje początkowe przemyślenia i można zrobić więcej przemyśleń lub przeprowadzić symulację, aby sprawdzić, czy działa ona dobrze, czy konieczna jest poprawa:

Moja odpowiedź to zapamiętanie długiego adresu URL w bazie danych i użycie identyfikatora 0do 9999999999999999(lub jak dużej liczby jest potrzebny).

Ale identyfikator 0 9999999999999999może być problemem, ponieważ

  1. może być krótszy, jeśli użyjemy szesnastkowej, a nawet base62 lub base64. (base64 podobnie jak YouTube przy użyciu A- Z a- z 0- 9 _i -)
  2. jeśli wzrośnie z 0do 9999999999999999równomiernie, hakerzy mogą odwiedzać ich w tej kolejności i wiedzieć, jakie adresy URL wysyłają sobie nawzajem, więc może to być problem z prywatnością

Możemy to zrobić:

  1. mają jeden serwer przeznaczyć 0na999 jednego serwera, Serwer A, więc teraz Serwer A ma 1000 takich identyfikatorów. Więc jeśli 20 lub 200 serwerów ciągle chce nowych identyfikatorów, nie musi ciągle pytać o każdy nowy identyfikator, a raczej pytać raz o 1000 identyfikatorów
  2. dla ID 1 na przykład odwróć bity. Tak więc 000...00000001staje się 10000...000, tak, że po przekonwertowaniu do base64, to będzie nierównomiernie zwiększanie numerów ID za każdym razem.
  3. użyj XOR, aby przerzucić bity na ostateczne identyfikatory. Na przykład XOR z 0xD5AA96...2373(jak tajny klucz), a niektóre bity zostaną odwrócone. (za każdym razem, gdy tajny klucz ma włączony 1 bit, odwróci bit identyfikatora). To sprawi, że identyfikatory będą jeszcze trudniejsze do odgadnięcia i będą wyglądać bardziej losowo

Zgodnie z tym schematem pojedynczy serwer, który przydziela identyfikatory, może tworzyć identyfikatory, podobnie jak 20 lub 200 serwerów żądających przydzielenia identyfikatorów. Serwer alokujący musi użyć blokady / semafora, aby zapobiec otrzymaniu tej samej partii przez dwa serwery żądające (lub jeśli przyjmuje jedno połączenie na raz, to już rozwiązuje problem). Dlatego nie chcemy, aby linia (kolejka) była zbyt długa, aby mogła czekać na przydział. Dlatego przydzielenie 1000 lub 10000 na raz może rozwiązać problem.

niepolarność
źródło