Jak utworzyć Skracacz adresów URL?

Po co Ci hash?

Możesz po prostu użyć prostego tłumaczenia wartości auto-increment na wartość alfanumeryczną. Możesz to zrobić łatwo za pomocą konwersji bazowej. Powiedzmy, że spacja znaków (A-Z, A-Z, 0-9, itd.) ma 62 znaki, Przelicz id na liczbę bazową-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 uwzględniających wielkość liter. Są one trudne do zapamiętania, Zwykle nieczytelne (wiele czcionek renderuje 1 i l, 0 I O oraz inne znaki bardzo podobne, że są prawie niemożliwe do odróżnienia) i wręcz podatne na błędy. Staraj się używać tylko małych lub dużych liter.

Spróbuj również mieć format, w którym mieszasz Liczby i znaki w predefiniowanej formie. Istnieją badania, które pokazują, że ludzie mają tendencję do zapamiętywania jednej formy lepiej niż inne (pomyśl numery telefonów, gdzie numery są pogrupowane w określonej formie). Spróbuj czegoś w stylu num-char-char-num-char-char. Wiem, że to obniży kombinacje, zwłaszcza jeśli nie masz wielkich i małych liter, ale byłoby to bardziej użyteczne i dlatego użyteczne.

Moje podejście: weź identyfikator bazy danych, a następnie Base36 Zakoduj go . Nie używałbym zarówno wielkich, jak i małych liter, ponieważ to sprawia, że przesyłanie tych adresów URL przez telefon jest koszmarem, ale można oczywiście łatwo rozszerzyć funkcję do bazy 62 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;
    }
}

Węzeł.rozwiązanie JS i MongoDB

Ponieważ znamy format, którego MongoDB używa do tworzenia nowego ObjectId z 12 bajtami.

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

Przykład (wybieram losowo Sekwencja) a1b2c3d4e5f6g7h8i9j1k2l3

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

Ponieważ licznik będzie unikalny, jeśli będziemy przechowywać dane w tej samej maszynie, możemy go uzyskać Bez wątpliwości, że będzie duplikowany.

więc krótki adres URL będzie licznik a oto fragment kodu zakładając, że twój 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");
    })
});

Ciągle zwiększam sekwencję całkowitą dla domeny w bazie danych i używam Hashids do kodowania liczby całkowitej w ścieżce URL.

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

Uruchomiłem skrypt, aby zobaczyć, jak długo potrwa, zanim wyczerpie długość znaków. Dla sześciu znaków może to zrobić 164,916,224 Linki, a następnie przechodzi do siedmiu znaków. Bitly używa siedmiu znaków. Poniżej pięciu znaków wygląda dziwnie.

Hashids może dekodować ścieżkę URL z powrotem do liczby całkowitej, ale prostszym rozwiązaniem jest użycie cały Krótki link sho.rt/ka8ds3 jako klucz podstawowy.

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

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 hashować cały URL, ale jeśli chcesz tylko skrócić id, zrób to, co zasugerował marcel. Napisałem tę implementację Pythona:

Https://gist.github.com/778542

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

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

Jeśli nie chcesz ponownie wynaleźć 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

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

Oto porządna funkcja kodowania 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 komuś się to przyda - jest to raczej metoda 'hack n slash', ale jest prosta i działa ładnie, jeśli chcesz tylko konkretne znaki.

$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 pominąłeś O, 0,a 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;
        }
    }
?>

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

Tego 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 trwać długo.

Dla podobnego projektu, aby uzyskać nowy klucz, wykonuję funkcję wrappera wokół random string generator, który wywołuje generator, dopóki nie otrzymam ciągu, który nie został jeszcze użyty w moim hashtable. Ta metoda spowolni, gdy przestrzeń nazw zacznie się wypełniać, ale jak już powiedziałeś, nawet z zaledwie 6 znakami, masz mnóstwo przestrzeni nazw do pracy.

Mam wariant problemu, w którym przechowuję strony internetowe od wielu różnych autorów i muszę zapobiec 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 adresy URL są ważne (zakładając 2-cyfrową bazę-62). Możesz zobaczyć opis w http://mgscan.com/MBWL .

Bardzo dobra odpowiedź, stworzyłem implementację Golanga 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
}

Hosted at github: https://github.com/xor-gate/go-bjf

Implementacja 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 węzeł.implementacja js, która prawdopodobnie bit.ly. Wygeneruj wysoce losowy siedmioznakowy ciąg znaków.

Używa węzła.js crypto, aby wygenerować wysoce losowy zestaw znaków 25, zamiast losowo wybierać siedem 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 Pythona 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")

Dla węzła jakości.rozwiązanie JS / JavaScript, patrz moduł id-shortener , który jest dokładnie testowany i jest używany w produkcji od miesięcy.

Zapewnia wydajne skracanie id / URL wspierane przez pamięć pluggable domyślnie do Redis , a nawet można dostosować zestaw znaków krótkiego id i czy skracanie jest idempotent . Jest to ważne rozróżnienie, które nie uwzględnia wszystkich skrótów URL.

W stosunku do innych odpowiedzi tutaj, moduł ten realizuje doskonałą akceptowaną odpowiedź Marcela Jackwerth powyżej.

Rdzeń roztworu jest dostarczany przez 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 nie dołączyć go do podstawowego adresu URL? Jest to bardzo uproszczona wersja robienia tego w 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 dodaj losowy ciąg do bazy:

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 łańcuchów. W produkcji chcesz wziąć pod uwagę duplikaty ciągów, aby upewnić się, że zawsze będziesz mieć unikalny adres URL. I mieć jakiś kod, który bierze pod uwagę duplikaty ciągów, pytając tabelę bazy danych, którą mógłbym udostępnić, jeśli ktoś jest zainteresowany.

To jest moje pierwsze myśli, i więcej myślenia można zrobić, lub niektóre symulacje mogą być wykonane, aby zobaczyć, czy to działa dobrze lub jakaś poprawa jest potrzebna:]}

Moją odpowiedzią jest zapamiętanie długiego adresu URL w bazie danych i użycie ID 0 do 9999999999999999 (lub jakkolwiek duża liczba jest potrzebna).

Ale ID 0 do 9999999999999999 może być problemem, ponieważ

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

Możemy to zrobić:

1. mieć jeden serwer przydzielić 0 do 999 do jednego serwera, serwer a, więc teraz serwer A ma 1000 takich identyfikatorów. Więc jeśli jest 20 lub 200 serwerów, które ciągle chcą nowych identyfikatorów, nie musi ciągle pytać o każde nowe ID, ale raczej pytać once for 1000 IDs
2. dla ID 1, na przykład, Odwróć bity. Tak więc 000...00000001 staje się 10000...000, tak że po przekonwertowaniu do base64, będzie to niejednolicie zwiększające się identyfikatory za każdym razem.
3. użyj XOR, aby odwrócić bity dla końcowych identyfikatorów. Na przykład, XOR z 0xD5AA96...2373 (jak tajny klucz), a niektóre bity zostaną odwrócone. (gdy klucz tajny ma włączony 1 bit, odwróci on bit identyfikatora). To sprawi, że identyfikatory będą jeszcze trudniejsze do odgadnięcia i pojawią się bardziej random

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 przydzielający musi użyć blokady / semafora, aby zapobiec pobraniu tej samej partii przez dwa serwery żądające (lub jeśli przyjmuje jedno połączenie na raz, to już rozwiązuje problem). Nie chcemy więc, aby linia (kolejka) była zbyt długa, aby czekać na przydział. Dlatego przydzielanie 1000 lub 10000 na czas może rozwiązać problem.