Jak utworzyć skracacz URL?

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

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 ₁₀ (125 z podstawą 10).

3. Teraz musisz przekonwertować 125 ₁₀ na X ₆₂ (baza 62).

   125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ =[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 ₆₂ 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 ₆₂ zostanie przetłumaczona na „4, 61 i 0 litera alfabetu”.

   e9a ₆₂ = [4,61,0]= 4 × 62 ² + 61 × 62 ¹ + 0 × 62 ⁰ = 19158 ₁₀

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

Przykładowe implementacje (dostarczone przez komentujących)

• C ++
• Pyton
• Rubin
• Haskell
• DO#
• CoffeeScript
• Perl

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.

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

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.

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.

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

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

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

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

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

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

// 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

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

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.

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

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

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

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ść.

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.

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.

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 .

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

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

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

}

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

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

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

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

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.

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.