php 短链接算法收集与分析

　　短链接就不说了，大家已经都清楚了，如下所示就是短链接：

　　新浪微博 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<[email protected]>

　　* @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<[email protected]>

　　* @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 );