标签归档:BCMath

短网址生成

有时候我们想把一个URL分享给别人,如果URL参数太多,或者太长了,生成的二维码就不好扫描,不方便分享。于是便有了缩短网址的需求,比如微博的t.cn,微信的url.cn,Twitter的t.co。甚至有Bitly.com这样的第三方短网址服务商,提供url访问统计/营销。
怎么样将一个长URL映射成短的URL?如果只是单纯的字符串压缩,很难达到,没办法预计URL有多长。将URL MD5后看起来可行,但是有点长,我们不需要那么多位。最简单的就是在数据库里面存储,一个ID对应一个URL。事实上世界上的URL仍然没有超过2的64次方,因此我们采用自增数字ID就可以了,比如数据库自增量或分布式ID生成器。使用自增数字ID的好处是它可以作为数据库主键,通过它来查找对应的URL就很快来。但是随着ID的增长,它也会变得很长,我们还可以将它缩短:将一个10进制的数字转换为62进制的字符串,最多只要11个字符就可以了。


如果能预计需要生成的网址数量,还可以再缩短,譬如世界上的网址数量大概50亿,62的7次方远大于这个数,因此7个字符足够了。
当访问短网址时,需要301/302重定向到原本的长网址。如果是301永久重定向,则搜索引擎会直接显示重定向后的地址。
PHP函数base_convert可以在2和36进制之间转换,对于62进制就不行,这里分享一个Base62 的转换类,可以将10进制数字转换位62进制

<?php

declare(strict_types=1);

namespace Dig\Conversion;


class Base
{
    const BASE_MIN = 2;
    const BASE_MAX = 62;

    public function __construct(int $base, string $aplphabet)
    {
        if (($base < self::BASE_MIN) || ($base > self::BASE_MAX)) {
            throw new \Exception('base convert only require '.self::BASE_MIN.' <= base <= '.self::BASE_MAX);
        }
        if (empty($aplphabet)) {
            throw new \Exception('cannot have empty aplphabet');
        }
        if ($base > \strlen($aplphabet)) {
            throw new \Exception('base convert only require base <= aplphabet length ');
        }
        $this->base = $base;
        $this->alphabet = $aplphabet;
    }

    public function encode(int $number): string
    {
        $number = (string) $number;
        $base = (string) $this->base;
        $reminder = \bcmod($number, $base);
        $quotient = \bcdiv($number, $base);
        $result = $this->alphabet[$reminder];

        while ($quotient) {
            $reminder = \bcmod($quotient, $base);
            $quotient = \bcdiv($quotient, $base);
            $result = $this->alphabet[$reminder] . $result;
        }
        return $result;
    }
    public function decode(string $number): int
    {
        $base = (string) $this->base;
        $length = \strlen($number);
        $result = (string) \strpos($this->alphabet, $number[0]);

        for ($i = 1; $i < $length; $i++) {
            $result = \bcadd(\bcmul($base, $result), (string) \strpos($this->alphabet, $number[$i]));
        }
        return (int)$result;
    }
}

class Base62 extends Base
{
    public function __construct()
    {
        parent::__construct(62, '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ');
    }
}

这里使用a-z表示10-36,A-Z表示37-62。注意这里需要用到BCMath扩展,否则对于超过2的32次方的大数字数不准确。也可以使用GMP扩展的gmp_strval函数直接转换。注意gmp使用A-Z表示10-36,a-z表示37-62。
测试一下:

include __DIR__.'/../vendor/autoload.php';

use Dig\Conversion\Base62;


$base62 = new Base62();
$id = 56800235584;

for ($i = 1; $i < 100; $i++) {
    $encode = $base62->encode($id);
    $decode = $base62->decode($encode);
    echo $id.'->'.$encode.'->'.$decode.PHP_EOL;
    $id += $i;
}

这里的起始ID可以自定义或者在分布式ID生成器里面更改CUSTOM_EPOCH生成合适的值。
由于这个ID本身就是唯一,映射为固定长度的字符,也可以用来做唯一标识,比如匿名用户的ID,Ngrok三级域名等等。
这个类可以扩展成支持任意2-64进制的转换,更改映射的字符串就行了。
注意这里的Base62转换于PHP函数base64_encode/base64_decode没有任何关系,即使在这个类的基础上增加2个字符支持Base64编码也不一样。Base64是使用64个可打印字符对二进制数据的编码解码,它的编码表与这里定义的不一样。

参考链接:
如何设计一个短网址服务(TinyURL)?
converting a number base 10 to base 62 (a-zA-Z0-9)
Generating IDs like Youtube or Bit.ly using PHP
PHP Base-62 encoding
Shortening Strings (URLs) using Base 62 Encoding
Base 2, 8, 16, 62, N Conversion – PHP