短链接算法收集与分析

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

新浪微博     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、微博短域名原理及作用

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 条评论
登录 后参与评论

相关文章

来自专栏python3

习题18:命名,变量,代码,函数

1. 首先告诉python创建一个函数,使用的命令是def,也就是定义(define)的意思

8620
来自专栏java一日一条

Java类的生命周期详解

最近有位细心的朋友在阅读笔者的文章时,对java类的生命周期问题有一些疑惑,笔者打开百度搜了一下相关的问题,看到网上的资料很少有把这个问题 讲明白的,主要是因为...

15530
来自专栏轮子工厂

Java多线程学习

提醒一下大家:main方法其实也是一个线程。在java中所以的线程都是同时启动的,至于什么时候,哪个先执行,完全看谁先得到CPU的资源。

14820
来自专栏老九学堂

原来C语言和其他高级语言的最大的区别是这个...

我们需要知道——变量,其实是内存地址的一个抽像名字罢了。在静态编译的程序中,所有的变量名都会在编译时被转成内存地址。机器是不知道我们取的名字的,只知道地址。

15630
来自专栏测试开发架构之路

堆和栈的区别

一、预备知识—程序的内存分配          一个由C/C++编译的程序占用的内存分为以下几个部分     1、栈区(stack)— 由编译器自动分配释放,存...

29180
来自专栏陈满iOS

iOS基础:全局变量·静态变量·局部变量·自动变量(static、extern、全局静态区、堆区、栈区)

区分三种变量的特点,如果只看声明位置和访问范围,肯定不够深刻的,需要进一步理解在内存中的不同。所以,这里我们来复习总结一下三种变量的特点,区分巩固基础知识。

26430
来自专栏微信公众号:Java团长

详解Java类的生命周期

最近有位细心的朋友在阅读笔者的文章时,对java类的生命周期问题有一些疑惑,笔者打开百度搜了一下相关的问题,看到网上的资料很少有把这个问题讲明白的,主要是因为目...

10820
来自专栏章鱼的慢慢技术路

Go语言相关练习_选择题(2)

go语言中字符串是UTF-8编码并存储的,它语言不定长的字节,所以它不支持下标操作,因为没一个下标操作代表的是固定长度的字节,所以不能对字符串中某个字符单独赋值...

11820
来自专栏架构师小秘圈

shell脚本极简教程

一,shell题记 不懂shell的程序员不是好程序员,学习shell是为了自动化,使用自动化可以非常有效的提高工作效率。没有一个大公司不要求linux的基本技...

44360
来自专栏架构师之路

一分钟sed入门(一分钟系列)

1.简介 sed是一种行编辑器,它一次处理一行内容。 2.sed调用方式 sed [options] 'command' file(s) sed [option...

400110

扫码关注云+社区

领取腾讯云代金券