这是一篇迟来的讨论，因为短网址大行其道还是在2010年前后，部分人刚刚用上智能手机的时候。不过，似乎仍然有一些有趣的地方可以讨论。

如何设计一个短码方案？

短码方案是指将任意长度的url编码成新的固定长度的URL,并且新URL的长度要大大小于之前的URL。同时，一般还要求URL所使用的字符容易识别和输入，并且不包含不合法的URL字符。实际上，这是将任意长度的字符串压缩成较短的固定长度的字符串的一个特例。

将任意长度的字符串无损压缩成固定长度的较短字符串，一般会借助字典，比如RLE算法。在我们这个例子里，期望对原URL直接编码，一步到位生成易识别、易输入的短码几乎是不可能的。假如原URL长度为20字符，短码使用5位字符方案，粗略计算的话，压缩比达到了 20^62 / 5^62之多，显然任何无损压缩是不可能达到这么高的比例的，我们知道比较好的压缩算法，可能最高也就是90%左右（比如对日志进行压缩时）。

因此方案必然是先进行摘要，然后对摘要值进行编码，然后建立编码结果到原网址的映射。在对压缩后的网址进行还原时，通过hash查找出对应的键值就可以了。所以，整个方案包括： 1. 用什么算法对原网址进行散列（摘要）？ 2. 如何将散列值进一步转换（编码）成易识别、易输入的短码？ 3. 如何保存映射表? 4. 为何要进行摘要？

摘要算法的选择

选择摘要算法时主要考虑性能与冲突概率。 对字符串进行摘要，比较知名的有md5,crc等算法 。这里介绍一个名为xxhash的算法。根据他的benchmark，比crc和md5都要快：

xxhash算法可以生成64bit的摘要，如果只是为自己的网站生成短码方案，这个长度是足够了(注意crc32,md5-32应该都是128bit)。如果是专业提供网址压缩服务，则应该考虑MD5-32或者更长的摘要算法。 xxhash摘要算法的使用如下所示：

import xxhash

digest_tool = xxhash.xxh64()

def get_hash(text: str):
  digest_tool.reset()
  digest_tool.update(text)
  return digest_tool.intdigest()

我们返回int型的hash值，以便后面的编码方法使用。

编码方案的选择

假设我们只能使用5位短字符串，要将一个64bit的整数完全编码，仍然是不可能的。我们的选择有hex编码（字符集包含16个字符，可以编码16^5，约100万个网址），或者使用全部字母（包含大小写）和数字，这样字符集大小为62（一般称作base62)，可以编码62^5，约9亿个网址)。与64bit可以表示的样本空间相比，又损失了不少。显然， hex编码是不可取的。但base62也有其缺点，因为包含了容易混淆，不易识别的字符对0和o,1和l。因此，在我们的编码方案中，我们需要将其排除掉，只使用58位字符集，这个方案一般被称为base58编码，这也是比特币中常用的地址编码方案。

BASE58 = "23456789abcdefghijkmnopqrstuvwxyzABCDEFGHIJKLMNPQRSTUVWXYZ"
def encode(num, alphabet=BASE58):
    if num == 0:
        return alphabet[0]
    arr = []
    base = len(alphabet)
    while num:
        num, rem = divmod(num, base)
        arr.append(alphabet[rem])
    arr.reverse()
    return ''.join(arr)

如果使用5位短码的话，可以编码的网址约6.5亿。

除法陷阱：python 2与python 3的区别

上面的算法取自https://stackoverflow.com/a/1119769/1210352。在同一个问题下，还有一个未采纳的回答如下：

import string
BASE_LIST = string.digits + string.letters + '_@'
BASE_DICT = dict((c, i) for i, c in enumerate(BASE_LIST))

def base_decode(string, reverse_base=BASE_DICT):
    length = len(reverse_base)
    ret = 0
    for i, c in enumerate(string[::-1]):
        ret += (length ** i) * reverse_base[c]

    return ret

def base_encode(integer, base=BASE_LIST):
    if integer == 0:
        return base[0]

    length = len(base)
    ret = ''
    while integer != 0:
        ret = base[integer % length] + ret
        integer /= length

    return ret

答主认为这个算法比被接受的答案更快。如果仔细观察，这段代码实际上有两个问题： 1. 这段代码实际上是python 2的。在python 3中， integer /= length会得到一个浮点结果，实际上导致这个算法很难结束（因为integer很难变为0）。 2. 算法使用了字符串拼接，这应该比前一个方法更慢，特别是会产生大量的临时字符串。

映射表的保存

现在，我们可以对任意的URL进行编码了：

def convert_short_url(url):
    _h = get_hash(url)
    short = encode(_h)
    return short, _h

根据具体的业务要求，可以使用redis或者数据库来保存短码与长码之间的映射。但在保存这个映射时，建议使用64bit的整数hash来作为键值，可能会得到更好的查找性能，所以convert_short_url也将这个hash值返回出来。

测试结果一

我们希望知道上面的方法的时间花销，以及它的抗碰撞强度。我们使用下面的代码来进行测试:

import sys
import time
length = int(sys.argv[1])

result = set()
t0 = time.time()
for i in range(1000000):
    s = ShortURL.convert_short_url('server_path?param={}'.format(i))
    result.add(s[:length])
print("unique ratio for generating {} chars short url".format(len(result)/1000000, length))
print("Costed {} seconds".format(time.time() - t0))

代码将生成的N位短码保存到一个set中，通过set的长度与生成的短码总数之比来计算短码的惟一性。 下表显示了分别使用4,5,6位短码时，对100万个网址进行编码所用的时间以及碰撞率：

n_char  |  time cost   | collision rate
--------|--------------|---------------
    4   |      4.96秒  |       5.9%
    5   |      5.2秒   |       0.11%  
    6   |      5.39秒  |       0.003%

也就是说，如果你的网站需要编码约100万个网址的话，只使用4位短码，可能会产生5.9%的碰撞率。所谓碰撞，就是指两个不同的URL被编码成为同一个短码。

为何要进行摘要？

在上面的方案中，我们先对原始网址进行了摘要处理--这给了我们某种心理安慰，使得我们以为新生成的短网址是跟原始网址一一关联的。但实际上，这个关联真正的建立发生成我们通过redis（或者数据库）建立键值对的映射时。因此，这个digest是毫无必要的。实际上，我们只是利用digest算法（这里是xxhash）来生成了一个随机数而已。

既然如此，也许我们可以抛弃digest算法，直接生成一个随机数？ 现在，我们将convert_short_url()改造下面的代码:

import random
def convert_short_url():
  return random.getrandbits(30)

这里使用内置随机数发生器random的getrandbits函数来生成30位的随机整数，它的样本空间比58^5略大一些。然后我们同样进行测试。测试结果如下：

n_char  |   time cost   | collision rate
--------|--------------|---------------
   4    |   2.9秒      |  17%
   5    |   2.8秒      |  1.1%

生成的速度要快许多，但是碰撞率也大为增加，到了几乎不能使用的程度。

终极方案

直接生成随机数的想法没有问题，但是它的防撞强度太差。必须寻找更好的算法。我的最终推荐是shortuuid这个库。

import shortuuid
print(shortuuid.random(5))
---output--
3BiYv

shortuuid并不使用base58编码，而是使用base57编码，所以当你使用5位短码时，它的样本空间将比base58少9% 左右。与我们前面使用的base58方案相比，它将大写的I也移除掉了。在许多字体中，数字1与小写的l，大写的I确实是很难分辨。 现在我们来测试一下它的生成速度和碰撞率：

if __name__ == "__main__":
    import sys
    import time
    length = int(sys.argv[1])

    result = set()
    t0 = time.time()
    for i in range(1000000):
        result.add(shortuuid.random(length))
    print("unique ratio for generating {} chars short url".format(len(result)/1000000, length))
    print("Costed {} seconds".format(time.time() - t0))

测试结果如下：

n_char  | time cost  | collision rate  
--------|------------|----------------
   4    |  5.77秒    |  5%
   5    |  5.73秒    |  0.083%
   6    |  6.19秒    |  0.001%

三者速度相差不多，总体的碰撞率是本文所讨论的方案中最好的一个，当使用5位短码时，就已经可以得到非常不错的碰撞率了。

结论

由于我们对短网址编码极高压缩率的要求，使得任何无损的压缩方案都不可能，而必须使用摘要->网址的映射方案。shortuuid提供了性能、碰撞率与易用性兼得的一个方案。而篇头的讨论揭示了这个方案的大致原理。

【缩我短链接】免费网络营销软件短链接生成器，是为网络推广人员量身定制的高效推广工具，也是私域运营神器，不仅可以缩短美化推广链接，提高点击率的同时，还不易引起反感，不容易被删除，也能够在QQ、微信等生态中完美兼容，短链接工具完全免费，大家可以点击缩我短链接（短链接-免费长网址在线生成短网址缩短服务），赶紧去试试吧！