生成短链接的URL

时间：2023-03-08 21:52:24

　　假设你想做一个像微博短链接那样的短链接服务，短链接服务生成的URL都非常短例如: http://t.cn/E70Piib, 我们应该都能想到链接中的E70Piib对应的就是存储长链接地址的数据记录的ID，可是这个有大小写字母和数字构成的唯一ID是怎么生成的呢，刚学编程的时候我们用的方法都试拼接一个足够唯一的字符串（比如时间戳加用户ID等等）然后再用MD5或者SHA1散列算法算出一个散列值，用这种方法得到的唯一ID有可能比原始的链接的长度还要长，所以如何来优雅的生成足够短的字符串唯一ID呢？

我们先来看一个数学问题，普通的数字ID是用十进制来表示的，在十进制中每位都有10种可能（0-9），所以5位的十进制数能呈现最多 10*10*10*10*10=100,000个ID。

现在如果用32进制来表达一个5位数字需要多少位呢？

<?php

echo base_convert(,,);//答案是 '90g'

32进制是数字和一些小些字母来组成，所以5位32进制可表达的唯一ID有 32*32*32*32*32=33,554,432个，数量已经很大了。使用32进制也能生成比较短的字符串唯一ID，不过还有更好的解决方案，你也看到了上面短链接的唯一ID里还包含大写字母。接下来我们使用62进制转换，将一个十进制数字转化为对应的62进制表示（为什么用62进制？数字加大小写字母一共是62个）。常用的这几个编程语言里没有提供62进制的转换，所以就需要我们自己写一个函数来进行10进制到62进制的转换。

一)

function shorturl($value, $b = )

{

    $base = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';

    $r = $value  % $b;

    $result = $base[$r];

    $q = floor($value / $b);

    while ($q)

    {

        $r = $q % $b;

        $q = floor($q / $b);

        $result = $base[$r].$result;

    }

    return $result;

}

二)

function shorturl($input)

{

    $base32 = array (

        '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', '', '', '', '',

        '', '');

    $hex = md5('prefix' . $input . 'surfix');

    $hexLen = strlen($hex);

    $subHexLen = $hexLen / ;

    $output = array();

    for ($i = ; $i < $subHexLen; $i++)

    {

        $subHex = substr($hex, $i * , );

        $int = 0x3FFFFFFF & ( * ('0x' . $subHex));

        $out = '';

        for ($j = ; $j < ; $j++)

        {

            $val = 0x0000001F & $int;

            $out .= $base32[$val];

            $int = $int >> ;

        }

        $output = $out;

    }

    return $output;

}

理解了将十进制正整数转换成62进制的字符串表示形式的原理后，在任何编程语言里都可以很轻松地实现一个转换函数，下面再提供一个Python版本的 Base62.encode：

#!/usr/bin/python

# -*- coding=UTF- -*-

from __future__ import print_function, division

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(num, alphabet=BASE62):

    """Encode a positive number in Base X

    Arguments:

    - `num`: The number to encode

    - `alphabet`: The alphabet to use for encoding

    """

    if num == :

        return alphabet[]

    arr = []

    base = len(alphabet)

    while num:

        num, rem = divmod(num, base)

        arr.append(alphabet[rem])

    arr.reverse()

    return ''.join(arr)

Python函数注解

  • python的divmod函数用第一个参数num除以第二个参数base，并以元组的形式返回商和余数。

  • 因为divmod返回两个元素构成的元组，在python中元组可以简写省略两边地括号，所以 num,rem=divmod(num,base)是一个元组赋值表达式，并不是divmod函数返回了两个返回值。

一亿用62进制表示出来后的结果是 6LAze , 生成的唯一字符串ID足够短。短链接只是一个应用场景， base62还可以应用到很多需要表示唯一ID的地方，这样一来你就不用再使用那些哈希算法来生成那么冗长的字符串了，虽然只是节省了一些空间但是这在高访问量的URL和海量数据的存储中还是能省下来不少资源的。

思考:

　　没有办法保证转化的短链接字符串的长度(数值越大,字符串越长),在高并发的情况下,无法保证快速分发

将生成的连接地址都统一使用6位进行表示

function code62($x){

    $show='';

    while($x>){

        $s=$x % ;

        if ($s>){

              $s=chr($s+);

        }elseif($s>&&$s<=){

              $s=chr($s+);

        }

        $show.=$s;

        $x=floor($x/);

    }

    return $show;

}

function shorturl($url){

    $url=crc32($url);

    $result=sprintf("%u",$url);

    return code62($result);

}

相关文章