Bagaimana cara membuat pemendek URL?

Saya ingin membuat layanan penyingkat URL di mana Anda dapat menulis URL panjang ke dalam kolom input dan layanan mempersingkat URL menjadi " http://www.example.org/abcdef".

Alih-alih " abcdef" bisa ada string lain dengan enam karakter yang mengandung a-z, A-Z and 0-9. Itu membuat 56 ~ 57 miliar string mungkin.

Pendekatan saya:

Saya memiliki tabel database dengan tiga kolom:

1. id, integer, peningkatan otomatis
2. long, string, URL panjang yang dimasukkan pengguna
3. pendek, string, URL singkat (atau hanya enam karakter)

Saya kemudian akan memasukkan URL panjang ke tabel. Lalu saya akan memilih nilai kenaikan-otomatis untuk " id" dan membangun hashnya. Hash ini kemudian harus dimasukkan sebagai " short". Tapi hash macam apa yang harus saya bangun? Algoritma hash seperti MD5 membuat string terlalu panjang. Saya tidak menggunakan algoritma ini, saya pikir. Algoritma yang dibangun sendiri akan bekerja juga.

Ide saya:

Untuk " http://www.google.de/" saya mendapatkan id kenaikan-otomatis 239472. Lalu saya melakukan langkah-langkah berikut:

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.

Itu bisa diulang sampai jumlahnya tidak habis dibagi lagi. Apakah Anda pikir ini pendekatan yang baik? Apakah Anda punya ide yang lebih baik?

_{Karena minat yang sedang berlangsung dalam topik ini, saya telah menerbitkan solusi yang efisien untuk GitHub , dengan implementasi untuk JavaScript , PHP , Python , dan Java . Tambahkan solusi Anda jika Anda suka :)}

Saya akan melanjutkan pendekatan "convert number to string" Anda. Namun, Anda akan menyadari bahwa algoritma yang Anda usulkan gagal jika ID Anda adalah yang utama dan lebih besar dari 52 .

Latar belakang teoritis

Anda membutuhkan Fungsi Bijektif f . Ini diperlukan agar Anda dapat menemukan fungsi terbalik g ('abc') = 123 untuk fungsi f Anda (123) = 'abc' . Ini berarti:

• Tidak boleh ada x1, x2 (dengan x1 ≠ x2) yang akan membuat f (x1) = f (x2) ,
• dan untuk setiap y Anda harus dapat menemukan x sehingga f (x) = y .

Cara mengonversi ID ke URL yang disingkat

1. Pikirkan alfabet yang ingin kita gunakan. Dalam kasus Anda, itu [a-zA-Z0-9]. Ini berisi 62 huruf .

2. Ambil kunci numerik unik yang dibuat secara otomatis ( idmisalnya tabel MySQL yang ditambahkan secara otomatis ).

   Untuk contoh ini, saya akan menggunakan 125 ₁₀ (125 dengan basis 10).

3. Sekarang Anda harus mengonversi 125 ₁₀ ke X ₆₂ (basis 62).

   125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ =[2,1]

   Ini membutuhkan penggunaan pembagian integer dan modulo. Contoh kode pseudo:

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

   Sekarang petakan indeks 2 dan 1 ke alfabet Anda. Beginilah tampilan pemetaan Anda (dengan array misalnya):

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

   Dengan 2 → c dan 1 → b, Anda akan menerima cb ₆₂ sebagai URL singkat.

   http://shor.ty/cb
   

Cara mengatasi URL singkat ke ID awal

Kebalikannya bahkan lebih mudah. Anda hanya melakukan pencarian terbalik di alfabet Anda.

1. e9a ₆₂ akan diselesaikan menjadi "huruf ke-4, ke-61, dan ke-0 dalam alfabet".

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

2. Sekarang temukan database-record Anda dengan WHERE id = 19158dan lakukan redirect.

Contoh implementasi (disediakan oleh komentator)

• C ++
• Python
• Rubi
• Haskell
• C #
• CoffeeScript
• Perl

Mengapa Anda ingin menggunakan hash?

Anda bisa menggunakan terjemahan sederhana dari nilai kenaikan otomatis Anda ke nilai alfanumerik. Anda dapat melakukannya dengan mudah dengan menggunakan beberapa konversi basis. Say you space karakter (AZ, az, 0-9, dll.) Memiliki 40 karakter, konversikan id ke nomor base-40 dan gunakan karakter sebagai digit.

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

Bukan jawaban untuk pertanyaan Anda, tetapi saya tidak akan menggunakan URL singkat yang peka terhadap huruf besar-kecil. Mereka sulit untuk diingat, biasanya tidak dapat dibaca (banyak font membuat 1 dan l, 0 dan O dan karakter lainnya sangat mirip sehingga mereka hampir tidak mungkin untuk mengetahui perbedaannya) dan rawan kesalahan. Coba gunakan huruf kecil atau huruf besar saja.

Juga, cobalah memiliki format tempat Anda mencampur angka dan karakter dalam bentuk yang telah ditentukan. Ada penelitian yang menunjukkan bahwa orang cenderung mengingat satu bentuk lebih baik daripada yang lain (pikirkan nomor telepon, di mana jumlahnya dikelompokkan dalam bentuk tertentu). Cobalah sesuatu seperti num-char-char-num-char-char. Saya tahu ini akan menurunkan kombinasi, terutama jika Anda tidak memiliki huruf besar dan kecil, tetapi akan lebih bermanfaat dan karenanya berguna.

Pendekatan saya: Ambil ID Database, lalu Base36 Encode . Saya TIDAK akan menggunakan kedua huruf besar dan huruf kecil, karena itu membuat pengiriman URL tersebut melalui telepon menjadi mimpi buruk, tetapi tentu saja Anda dapat dengan mudah memperluas fungsi menjadi basis 62 en / decoder.

Ini kelas PHP 5 saya.

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

Solusi Node.js dan MongoDB

Karena kita tahu format yang digunakan MongoDB untuk membuat ObjectId baru dengan 12 byte.

• nilai 4-byte mewakili detik sejak zaman Unix,
• pengidentifikasi mesin 3-byte,
• id proses 2 byte
• penghitung 3 byte (di mesin Anda), dimulai dengan nilai acak.

Contoh (saya memilih urutan acak) a1b2c3d4e5f6g7h8i9j1k2l3

• a1b2c3d4 mewakili detik sejak zaman Unix,
• 4e5f6g7 mewakili pengidentifikasi mesin,
• h8i9 mewakili id ​​proses
• j1k2l3 mewakili penghitung, dimulai dengan nilai acak.

Karena penghitung akan menjadi unik jika kita menyimpan data di mesin yang sama kita bisa mendapatkannya tanpa ragu bahwa itu akan duplikat.

Jadi URL pendek akan menjadi penghitung dan di sini ada potongan kode dengan asumsi server Anda berjalan dengan baik.

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

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

Anda dapat meng-hash seluruh URL, tetapi jika Anda hanya ingin mempersingkat id, lakukan seperti yang disarankan marcel. Saya menulis implementasi Python ini:

https://gist.github.com/778542

Saya terus menambahkan urutan integer per domain dalam database dan menggunakan Hashids untuk menyandikan integer ke jalur URL.

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

Saya menjalankan skrip untuk melihat berapa lama sampai panjang karakter habis. Untuk enam karakter dapat melakukan 164,916,224tautan dan kemudian naik hingga tujuh karakter. Sedikit menggunakan tujuh karakter. Di bawah lima karakter terlihat aneh bagiku.

Hashids dapat mendekode jalur URL kembali ke integer tetapi solusi yang lebih sederhana adalah dengan menggunakan seluruh tautan pendeksho.rt/ka8ds3 sebagai kunci utama.

Inilah konsep lengkapnya:

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

Jika Anda tidak ingin menemukan kembali roda ... 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

Inilah versi saya untuk siapa pun yang membutuhkannya.

Mengapa tidak menerjemahkan id Anda ke string saja? Anda hanya perlu fungsi yang memetakan digit antara, katakanlah, 0 dan 61 ke satu huruf (huruf besar / kecil) atau digit. Kemudian terapkan ini untuk membuat, katakanlah, kode 4 huruf, dan Anda mendapatkan 14,7 juta URL.

Berikut adalah fungsi penyandian URL yang layak untuk 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;
}

Tidak tahu apakah ada yang akan menemukan ini berguna - ini lebih dari metode 'hack n slash', namun sederhana dan berfungsi dengan baik jika Anda hanya menginginkan karakter tertentu.

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

Apakah Anda sengaja menghilangkan O, 0, dan saya?

Saya baru saja membuat kelas PHP berdasarkan pada solusi 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;
        }
    }
?>

Lihatlah https://hashids.org/ ini adalah open source dan dalam banyak bahasa.

Halaman mereka menguraikan beberapa jebakan dari pendekatan lain.

Inilah yang saya gunakan:

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

Ini sangat cepat dan bisa memakan waktu lama.

Untuk proyek serupa, untuk mendapatkan kunci baru, saya membuat fungsi pembungkus di sekitar generator string acak yang memanggil generator sampai saya mendapatkan string yang belum pernah digunakan dalam hashtable saya. Metode ini akan melambat begitu ruang nama Anda mulai penuh, tetapi seperti yang telah Anda katakan, bahkan dengan hanya 6 karakter, Anda memiliki banyak ruang nama untuk digunakan.

Saya memiliki varian masalah, yaitu saya menyimpan halaman web dari banyak penulis yang berbeda dan perlu mencegah penemuan halaman dengan menebak. Jadi URL pendek saya menambahkan beberapa digit tambahan ke string Base-62 untuk nomor halaman. Digit tambahan ini dihasilkan dari informasi dalam catatan halaman itu sendiri dan mereka memastikan bahwa hanya 1 dari 3844 URL yang valid (dengan asumsi 2-digit Base-62). Anda dapat melihat uraian garis besar di http://mgscan.com/MBWL .

Jawaban yang sangat bagus, saya telah membuat implementasi Golang 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
}

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

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

Contoh uji dengan uji 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)
  }

}

Fungsi berbasis di Kelas 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;
}

Berikut ini adalah implementasi Node.js yang cenderung bit.ly. menghasilkan string tujuh karakter yang sangat acak.

Ini menggunakan Node.js crypto untuk menghasilkan charset 25 yang sangat acak daripada secara acak memilih tujuh karakter.

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

Versi Python 3 saya

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

Untuk solusi Node.js / JavaScript yang berkualitas, lihat modul id-shortener , yang diuji secara menyeluruh dan telah digunakan dalam produksi selama berbulan-bulan.

Ini menyediakan id / pemendek efisien yang didukung oleh penyimpanan pluggable default ke Redis , dan Anda bahkan dapat menyesuaikan set karakter id pendek Anda dan apakah pemendekan idempoten atau tidak . Ini adalah perbedaan penting yang tidak diperhitungkan oleh semua penyingkat URL.

Sehubungan dengan jawaban lain di sini, modul ini mengimplementasikan jawaban yang diterima sangat baik oleh Marcel Jackwerth di atas.

Inti dari solusi disediakan oleh cuplikan Redis Lua berikut :

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

Mengapa tidak hanya membuat string acak dan menambahkannya ke URL dasar? Ini adalah versi yang sangat sederhana untuk melakukan ini di 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);
}

Kemudian cukup tambahkan append string acak ke baseURL:

string tinyURL = baseUrl + RandomString(5);

Ingat ini adalah versi yang sangat sederhana untuk melakukan ini dan mungkin metode RandomString dapat membuat string duplikat. Dalam produksi, Anda ingin memperhitungkan string duplikat untuk memastikan Anda akan selalu memiliki URL unik. Saya memiliki beberapa kode yang memperhitungkan string duplikat dengan menanyakan tabel database yang bisa saya bagikan jika ada yang tertarik.

Ini adalah pemikiran awal saya, dan lebih banyak pemikiran dapat dilakukan, atau beberapa simulasi dapat dilakukan untuk melihat apakah itu bekerja dengan baik atau diperlukan perbaikan:

Jawaban saya adalah mengingat URL panjang dalam database, dan menggunakan ID 0untuk 9999999999999999(atau seberapa besar jumlahnya diperlukan).

Tetapi ID 0 untuk 9999999999999999dapat menjadi masalah, karena

1. bisa lebih pendek jika kita menggunakan heksadesimal, atau bahkan base62 atau base64. (base64 seperti YouTube menggunakan A- Z a- z 0- 9 _dan -)
2. jika meningkat dari 0menjadi 9999999999999999seragam, maka peretas dapat mengunjunginya dalam urutan itu dan mengetahui URL apa yang orang kirim satu sama lain, sehingga ini bisa menjadi masalah privasi

Kita bisa melakukan ini:

1. minta satu server dialokasikan 0untuk999 satu server, Server A, jadi sekarang Server A memiliki 1000 ID tersebut. Jadi jika ada 20 atau 200 server terus-menerus menginginkan ID baru, itu tidak harus terus meminta setiap ID baru, tetapi meminta satu kali untuk 1000 ID
2. untuk ID 1, misalnya, balikkan bit. Jadi 000...00000001menjadi 10000...000, sehingga ketika dikonversi ke base64, itu akan meningkatkan ID yang tidak seragam setiap kali.
3. gunakan XOR untuk membalik bit untuk ID akhir. Misalnya, XOR dengan 0xD5AA96...2373(seperti kunci rahasia), dan beberapa bit akan dibalik. (setiap kali kunci rahasia diaktifkan 1 bit, itu akan membalik bit ID). Ini akan membuat ID semakin sulit ditebak dan tampak lebih acak

Mengikuti skema ini, server tunggal yang mengalokasikan ID dapat membentuk ID, dan begitu juga 20 atau 200 server yang meminta alokasi ID. Server pengalokasian harus menggunakan kunci / semafor untuk mencegah dua server yang meminta mendapatkan batch yang sama (atau jika menerima satu koneksi pada satu waktu, ini sudah memecahkan masalah). Jadi kami tidak ingin antrean terlalu lama menunggu untuk mendapatkan alokasi. Jadi itu sebabnya mengalokasikan 1000 atau 10.000 sekaligus dapat menyelesaikan masalah.