php 短链接算法收集与分析
程序员文章站
2022-05-14 12:51:59
短链接就不说了，大家已经都清楚了，如下所示就是短链接： 新浪微博 http://t.cn/svponm 腾讯微博 http://url.cn/302yor yun.io h...
短链接就不说了，大家已经都清楚了，如下所示就是短链接：
新浪微博 http://t.cn/svponm
腾讯微博 http://url.cn/302yor
yun.io http://d.yun.io/pnri2v
短链接的好处：1、内容需要；2、用户友好；3、便于管理。
如何实现呢，大概有三个步骤：
1、定义一个url映射算法，可以将长的url映射成短字符串；
2、使用一个存储（数据库？nosql？）来存储完成的映射；
3、实现自己的url映射算法；
一般来说，第三步是我们比较头疼的，如何将一个长的url字符串，映射成一个较短的字符串呢。我总结了三种办法：
普通实现
我想以前大家学习过十进制和二进制的互相转换，或者十进制和十六进制的互相转换，那么为了更短，我们可以使用62进制，对于一个数字id进行转码，转换成一个短字符串。
这种做法的缺点是没有办法保证所有链接都是固定的位数的长度，而且在高并发的情况下，如何保证能够快速分发是个问题。
具体实现方法：
/**
* 利用62进制对数字id进行短链接编码，缺点不能保证每个短链接是固定长度
*
* @author wanshiqiang<wangshiqiang@360.cn>
* @param integer $integer
* @param string $base
*/
private function getshortenedurlfromid ($integer, $base = allowed_chars)
{
$length = strlen($base);
while($integer > $length - 1)
{
$out = $base[fmod($integer, $length)] . $out;
$integer = floor( $integer / $length );
}
return $base[$integer] . $out;
}
/**
* 对62进制编码的短链接进行解码
*
* @author wangshiqiang<wangshiqiang@360.cn>
* @param string $string
* @param string $base
*/
private function getidfromshortenedurl ($string, $base = allowed_chars)
{
$length = strlen($base);
$size = strlen($string) - 1;
$string = str_split($string);
$out = strpos($base, array_pop($string));
foreach($string as $i => $char)
{
$out += strpos($base, $char) * pow($length, $size - $i);
}
return $out;
}
文艺实现
算法描述：使用6个字符来表示短链接，我们使用ascii字符中的'a'-'z','0'-'5'，共计32个字符做为集合。每个字符有32种状态，六个字符就可以表示32^6（1073741824），那么如何得到这六个字符，描述如下：
对传入的长url进行md5，得到一个32位的字符串，这个字符串变化很多，是16的32次方，基本上可以保证唯一性。将这32位分成四份，每一份8个字符，这时机率变成了16的8次方，是4294967296，这个数字碰撞的机率也比较小啦，关键是后面的一次处理。我们将这个8位的字符认为是16进制整数，也就是1*('0x'.$val)，然后取0-30位，每5个一组，算出他的整数值，然后映射到我们准备的32个字符中，最后就能够得到一个6位的短链接地址。
php实现如下：
function shorten( $long_url )
{
$base32 = "abcdefghijklmnopqrstuvwxyz012345";
$hex = md5( $long_url );
$hexlen = strlen( $hex );
$subhexlen = $hexlen / 8;
$output = array();
for( $i = 0; $i < $subhexlen; $i++ )
{
$subhex = substr( $hex, $i * 8, 8 );
$subhex = 0x3fffffff & ( 1 * ('0x' . $subhex ) );
$out = '';
for( $j = 0; $j < 6; $j++ )
{
$val = 0x0000001f & $int;
$out .= $base32[$val];
$int = $int >> 5;
}
$output[] = $out;
}
return $output;
}
二逼实现
下面这个函数使用了纯随机的方式来生成一个短链接，虽然我们可以通过查询操作来确保不重复使用短链接，可是... 这样真的靠谱吗~~
function random($length, $pool = '') {
$random = '';
if (empty($pool)) { $pool = 'abcdefghkmnpqrstuvwxyz'; $pool .=
'23456789'; }
srand ((double)microtime()*1000000);
for($i = 0; $i < $length; $i++) { $random .=
substr($pool,(rand()%(strlen ($pool))), 1); }
return $random;
}
新浪微博 http://t.cn/svponm
腾讯微博 http://url.cn/302yor
yun.io http://d.yun.io/pnri2v
短链接的好处：1、内容需要；2、用户友好；3、便于管理。
如何实现呢，大概有三个步骤：
1、定义一个url映射算法，可以将长的url映射成短字符串；
2、使用一个存储（数据库？nosql？）来存储完成的映射；
3、实现自己的url映射算法；
一般来说，第三步是我们比较头疼的，如何将一个长的url字符串，映射成一个较短的字符串呢。我总结了三种办法：
普通实现
我想以前大家学习过十进制和二进制的互相转换，或者十进制和十六进制的互相转换，那么为了更短，我们可以使用62进制，对于一个数字id进行转码，转换成一个短字符串。
这种做法的缺点是没有办法保证所有链接都是固定的位数的长度，而且在高并发的情况下，如何保证能够快速分发是个问题。
具体实现方法：
复制代码 代码如下:
/**
* 利用62进制对数字id进行短链接编码，缺点不能保证每个短链接是固定长度
*
* @author wanshiqiang<wangshiqiang@360.cn>
* @param integer $integer
* @param string $base
*/
private function getshortenedurlfromid ($integer, $base = allowed_chars)
{
$length = strlen($base);
while($integer > $length - 1)
{
$out = $base[fmod($integer, $length)] . $out;
$integer = floor( $integer / $length );
}
return $base[$integer] . $out;
}
/**
* 对62进制编码的短链接进行解码
*
* @author wangshiqiang<wangshiqiang@360.cn>
* @param string $string
* @param string $base
*/
private function getidfromshortenedurl ($string, $base = allowed_chars)
{
$length = strlen($base);
$size = strlen($string) - 1;
$string = str_split($string);
$out = strpos($base, array_pop($string));
foreach($string as $i => $char)
{
$out += strpos($base, $char) * pow($length, $size - $i);
}
return $out;
}
文艺实现
算法描述：使用6个字符来表示短链接，我们使用ascii字符中的'a'-'z','0'-'5'，共计32个字符做为集合。每个字符有32种状态，六个字符就可以表示32^6（1073741824），那么如何得到这六个字符，描述如下：
对传入的长url进行md5，得到一个32位的字符串，这个字符串变化很多，是16的32次方，基本上可以保证唯一性。将这32位分成四份，每一份8个字符，这时机率变成了16的8次方，是4294967296，这个数字碰撞的机率也比较小啦，关键是后面的一次处理。我们将这个8位的字符认为是16进制整数，也就是1*('0x'.$val)，然后取0-30位，每5个一组，算出他的整数值，然后映射到我们准备的32个字符中，最后就能够得到一个6位的短链接地址。
php实现如下：
复制代码 代码如下:
function shorten( $long_url )
{
$base32 = "abcdefghijklmnopqrstuvwxyz012345";
$hex = md5( $long_url );
$hexlen = strlen( $hex );
$subhexlen = $hexlen / 8;
$output = array();
for( $i = 0; $i < $subhexlen; $i++ )
{
$subhex = substr( $hex, $i * 8, 8 );
$subhex = 0x3fffffff & ( 1 * ('0x' . $subhex ) );
$out = '';
for( $j = 0; $j < 6; $j++ )
{
$val = 0x0000001f & $int;
$out .= $base32[$val];
$int = $int >> 5;
}
$output[] = $out;
}
return $output;
}
二逼实现
下面这个函数使用了纯随机的方式来生成一个短链接，虽然我们可以通过查询操作来确保不重复使用短链接，可是... 这样真的靠谱吗~~
复制代码 代码如下:
function random($length, $pool = '') {
$random = '';
if (empty($pool)) { $pool = 'abcdefghkmnpqrstuvwxyz'; $pool .=
'23456789'; }
srand ((double)microtime()*1000000);
for($i = 0; $i < $length; $i++) { $random .=
substr($pool,(rand()%(strlen ($pool))), 1); }
return $random;
}
technorati 标签: ,short url,,
参考资料：
1、
2、
4、free php url shorten script that kicks ass
5、php short url algorithm implementation
6、implement your own short url
7、