免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1643 | 回复: 1

短链接算法收集与分析 [复制链接]

论坛徽章:
0
发表于 2012-01-07 16:18 |显示全部楼层
短链接算法收集与分析








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

新浪微博     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进行转码,转换成一个短字符串。

这种做法的缺点是没有办法保证所有链接都是固定的位数的长度,而且在高并发的情况下,如何保证能够快速分发是个问题。

具体实现方法:
  1.    /**
  2.      * 利用62进制对数字ID进行短链接编码,缺点不能保证每个短链接是固定长度
  3.      *
  4.      * @author  wanshiqiang<wangshiqiang@360.cn>
  5.      * @param integer $integer
  6.      * @param string $base
  7.      */
  8.     private function getShortenedURLFromID ($integer, $base = ALLOWED_CHARS)
  9.     {   
  10.         $length = strlen($base);
  11.         while($integer > $length - 1)
  12.         {   
  13.             $out = $base[fmod($integer, $length)] . $out;
  14.             $integer = floor( $integer / $length );
  15.         }   
  16.         return $base[$integer] . $out;
  17.     }   
  18.     /**
  19.      * 对62进制编码的短链接进行解码
  20.      *
  21.      * @author  wangshiqiang<wangshiqiang@360.cn>
  22.      * @param string $string
  23.      * @param string $base
  24.      */
  25.     private function getIDFromShortenedURL ($string, $base = ALLOWED_CHARS)
  26.     {   
  27.         $length = strlen($base);
  28.         $size = strlen($string) - 1;
  29.         $string = str_split($string);
  30.         $out = strpos($base, array_pop($string));
  31.         foreach($string as $i => $char)
  32.         {   
  33.             $out += strpos($base, $char) * pow($length, $size - $i);
  34.         }   
  35.         return $out;
  36.     }
复制代码
文艺实现

算法描述:使用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实现如下:
  1. function shorten( $long_url )
  2. {
  3.      $base32 = "abcdefghijklmnopqrstuvwxyz012345";
  4.      $hex = md5( $long_url );
  5.      $hexLen = strlen( $hex );
  6.      $subHexLen = $hexLen / 8;
  7.      $output = array();
  8.      for( $i = 0; $i < $subHexLen; $i++ )
  9.      {
  10.           $subHex = substr( $hex, $i * 8, 8 );
  11.           $subHex = 0x3FFFFFFF & ( 1 * ('0x' . $subHex ) );

  12.     $out = '';

  13.           for( $j = 0; $j < 6; $j++ )
  14.           {
  15.                $val = 0x0000001F & $int;
  16.                $out .= $base32[$val];
  17.                $int = $int >> 5;
  18.           }
  19.           $output[] = $out;
  20.      }
  21.      return $output;
  22. }
复制代码
二逼实现

下面这个函数使用了纯随机的方式来生成一个短链接,虽然我们可以通过查询操作来确保不重复使用短链接,可是... 这样真的靠谱吗~~
  1. function random($length, $pool = '') {
  2.      $random = '';
  3.      if (empty($pool)) { $pool    = 'abcdefghkmnpqrstuvwxyz'; $pool   .=
  4.      '23456789'; }
  5.      srand ((double)microtime()*1000000);
  6.      for($i = 0; $i < $length; $i++) { $random .=
  7.      substr($pool,(rand()%(strlen ($pool))), 1); }
  8.      return $random;
  9. }
复制代码
Technorati 标签: 短链接,Short Url,映射,哈希
参考资料:

1、微博短地址原理解析

2、微博短域名原理及作用

3、Yours.org

4、Free PHP URL Shorten script that kicks ass

5、PHP Short Url Algorithm Implementation

6、Implement your own short URL

7、短网址算法初步汇总

8、Short Url 实现方式

论坛徽章:
0
发表于 2012-01-07 16:18 |显示全部楼层
谢谢分享
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP