如何创建 URL 缩短器？ [关闭]

我会继续你的“将数字转换为字符串”的方法。但是，如果您的 ID 是素数且大于 52，您将意识到您提出的算法将失败。

理论背景

您需要一个 Bijective Function f。这是必要的，以便您可以为您的 f(123) = 'abc' 函数找到一个反函数 g('abc') = 123。这表示：

一定没有 x1, x2 (x1 ≠ x2) 会使 f(x1) = f(x2),

并且对于每个 y，您必须能够找到一个 x，使得 f(x) = y。

如何将 ID 转换为缩短的 URL

想想我们想要使用的字母表。在您的情况下，这是 [a-zA-Z0-9]。它包含 62 个字母。采用自动生成的唯一数字键（例如 MySQL 表的自动递增 id）。在本例中，我将使用 12510（125 以 10 为底）。现在您必须将 12510 转换为 X62（base 62）。 12510 = 2×621 + 1×620 = [2,1] 这需要使用整数除法和取模。伪代码示例： digits = [] while num > 0 余数 = modulo(num, 62) digits.push(remainder) num = divide(num, 62) digits = digits.reverse 现在将索引 2 和 1 映射到您的字母。这就是您的映射（例如使用数组）的样子： 0 → a 1 → b ... 25 → z ... 52 → 0 61 → 9 使用 2 → c 和 1 → b，您将收到 cb62作为缩短的 URL。 http://shor.ty/cb

如何将缩短的 URL 解析为初始 ID

反过来更容易。您只需在字母表中进行反向查找。

e9a62 将被解析为“字母表中的第 4、61 和 0 个字母”。 e9a62 = [4,61,0] = 4×622 + 61×621 + 0×620 = 1915810 现在找到 WHERE id = 19158 的数据库记录并进行重定向。

示例实现（由评论者提供）

C++

Python

红宝石

哈斯克尔

C＃

咖啡脚本

Perl

---

为什么要使用哈希？

您只需将自动增量值简单转换为字母数字值即可。您可以通过使用一些基本转换轻松地做到这一点。假设您的字符空间（AZ、az、0-9 等）有 62 个字符，将 id 转换为 base-40 数字并将字符用作数字。

---

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

---

不是您问题的答案，但我不会使用区分大小写的缩短 URL。它们很难记住，通常不可读（许多字体呈现 1 和 l、0 和 O 以及其他字符非常相似，几乎无法区分）并且容易出错。尝试仅使用小写或大写。

此外，尝试采用一种格式，将数字和字符以预定义的形式混合在一起。有研究表明，人们倾向于比其他形式更好地记住一种形式（想想电话号码，其中数字以特定形式分组）。尝试类似 num-char-char-num-char-char 的方法。我知道这会降低组合，特别是如果你没有大写和小写，但它会更有用，因此更有用。

---

我的方法：获取数据库 ID，然后是 Base36 Encode it。我不会同时使用大写和小写字母，因为这会使通过电话传输这些 URL 成为一场噩梦，但您当然可以轻松地将功能扩展为 base 62 en/decoder。

---

这是我的 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;
    }
}

---

Node.js 和 MongoDB 解决方案

因为我们知道 MongoDB 用来创建一个 12 字节的新 ObjectId 的格式。

一个 4 字节的值，表示自 Unix 纪元以来的秒数，

一个 3 字节的机器标识符，

一个 2 字节的进程 ID

一个 3 字节的计数器（在您的机器中），从一个随机值开始。

示例（我选择一个随机序列）a1b2c3d4e5f6g7h8i9j1k2l3

a1b2c3d4 表示自 Unix 纪元以来的秒数，

4e5f6g7 代表机器标识符，

h8i9 代表进程id

j1k2l3 代表计数器，从一个随机值开始。

由于如果我们将数据存储在同一台机器中，计数器将是唯一的，我们可以毫无疑问地得到它，它会重复。

所以短 URL 将是计数器，这里是一个代码片段，假设您的服务器运行正常。

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

---

我不断增加数据库中每个域的整数序列，并使用 Hashids 将整数编码为 URL 路径。

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

我运行了一个脚本来查看用完字符长度需要多长时间。对于六个字符，它可以执行 164,916,224 链接，然后最多可达七个字符。 Bitly 使用七个字符。五个字符以下对我来说看起来很奇怪。

Hashids 可以将 URL 路径解码回整数，但更简单的解决方案是使用整个短链接 sho.rt/ka8ds3 作为主键。

这是完整的概念：

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

---

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

---

您可以散列整个 URL，但如果您只想缩短 id，请按照 marcel 的建议进行操作。我写了这个 Python 实现：

https://gist.github.com/778542

---

看看 https://hashids.org/，它是开源的并支持多种语言。

他们的页面概述了其他方法的一些陷阱。

---

如果您不想重新发明轮子... 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

这是我的版本，供需要的人使用。

---

为什么不把你的 id 翻译成一个字符串呢？您只需要一个将 0 到 61 之间的数字映射到单个字母（大写/小写）或数字的函数。然后应用它来创建，比如说，4 个字母的代码，你已经覆盖了 1470 万个 URL。

---

这是一个不错的 PHP URL 编码函数...

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

---

不知道是否有人会觉得这很有用——它更像是一种“hack n slash”方法，但如果你只想要特定的字符，它很简单而且效果很好。

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

---

您是否故意省略了 O、0 和 i？

我刚刚基于 Ryan 的解决方案创建了一个 PHP 类。

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

---

这就是我使用的：

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

它非常快并且可以取长整数。

---

对于一个类似的项目，为了获得一个新密钥，我围绕一个调用生成器的 random string generator 创建了一个包装函数，直到我得到一个尚未在我的哈希表中使用的字符串。一旦您的名称空间开始变满，此方法会变慢，但正如您所说，即使只有 6 个字符，您也有足够的名称空间可以使用。

---

我有一个问题的变体，因为我存储了来自许多不同作者的网页，并且需要防止通过猜测发现页面。因此，我的短 URL 为页码的 Base-62 字符串添加了几个额外的数字。这些额外的数字是根据页面记录本身的信息生成的，它们确保 3844 个 URL 中只有 1 个有效（假设为 2 位 Base-62）。您可以在 http://mgscan.com/MBWL 中看到概要说明。

---

很好的答案，我创建了 bjf 的 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
}

托管在 github：https://github.com/xor-gate/go-bjf

---

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

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

}

---

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

---

这是一个可能 bit.ly 的 Node.js 实现。生成一个高度随机的七字符字符串。

它使用 Node.js 加密来生成高度随机的 25 个字符集，而不是随机选择 7 个字符。

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

---

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

---

如需优质的 Node.js/JavaScript 解决方案，请参阅 id-shortener 模块，该模块经过全面测试并已在生产环境中使用数月。

它提供了一个高效的 id / URL 缩短器，由默认为 Redis 的可插入存储支持，您甚至可以自定义短 id 字符集以及缩短是否是幂等的。这是一个重要的区别，并非所有 URL 缩短器都考虑在内。

关于此处的其他答案，此模块实现了上述 Marcel Jackwerth 出色的公认答案。

解决方案的核心由以下 Redis Lua snippet 提供：

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

---

为什么不直接生成一个随机字符串并将其附加到基本 URL？这是在 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);
}

然后只需将随机字符串添加到 baseURL：

string tinyURL = baseUrl + RandomString(5);

请记住，这是一个非常简化的版本，RandomString 方法可能会创建重复的字符串。在生产中，您需要考虑重复字符串，以确保您始终拥有唯一的 URL。我有一些代码通过查询我可以共享的数据库表来考虑重复字符串，如果有人感兴趣的话。

---

这是我的初步想法，还可以多做一些思考，或者做一些模拟，看看效果好不好或者需要改进：

我的答案是记住数据库中的长 URL，并使用 ID 0 到 9999999999999999（或者需要多大的数字）。

但是 ID 0 到 9999999999999999 可能是个问题，因为

如果我们使用十六进制，甚至 base62 或 base64，它可以更短。 （base64 就像 YouTube 使用 AZ az 0-9 _ 和 -）如果它从 0 统一增加到 9999999999999999，那么黑客可以按该顺序访问它们并知道人们相互发送的 URL，因此这可能是一个隐私问题

我们做得到：

让一台服务器将 0 到 999 分配给一台服务器，服务器 A，所以现在服务器 A 有 1000 个这样的 ID。因此，如果有 20 或 200 台服务器不断地需要新 ID，它不必一直要求每个新 ID，而是为 ID 1 要求 1000 个 ID，例如，反转位。所以000...00000001变成了10000...000，这样转换成base64后，每次都是非均匀递增的ID。使用 XOR 翻转最终 ID 的位。例如，与 0xD5AA96...2373 进行异或（如密钥），一些位将被翻转。 （只要密钥打开 1 位，它就会翻转 ID 的位）。这将使 ID 更加难以猜测并且显得更加随机

按照这种方案，分配 ID 的单个服务器可以形成 ID，请求分配 ID 的 20 或 200 个服务器也可以形成 ID。分配服务器必须使用锁/信号量来防止两个请求服务器获得相同的批次（或者如果它一次接受一个连接，这已经解决了问题）。所以我们不希望行（队列）太长等待获得分配。这就是为什么一次分配 1000 或 10000 可以解决问题的原因。

---