注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

obsolete

wanna go

 
 
 

日志

 
 

短址(short URL)原理及其实现  

2014-01-10 16:49:04|  分类: 计算机知识 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

前言:

最近看了一些关于短址(short URL)方面的一些博客,有些博客说到一些好的东西,但是,也不是很全,所以,这篇博客算是对其它博客的一个总结吧。


介绍:

短址,顾名思义,就是把长的 URL 转成短的 URL, 现在提供这种服务的有很多公司,我们以google家的 URL shortener 服务: http://goo.gl/ 为例。

首先我们到 http://goo.gl/,然后把本文博客的地址http://blog.csdn.net/beiyeqingteng 输入进去,最后它会返回一个更短的URL,http://goo.gl/Jfs6q 。如下图所示:




URL 解析:

当我们在浏览器里输入 http://goo.gl/Jfs6q 时,DNS首先解析获得http://goo.gl/的IP地址。当DNS获得IP地址以后(比如:74.125.225.72),会向这个地址发送HTTP GET请求,查询 Jfs6q, 这个时候,http://goo.gl/服务器会把请求通过HTTP 301转到对应的长URL http://blog.csdn.net/beiyeqingteng 。后面的解析过程就和平常网址解析是一样的了。


短址本质:

短址本质上是实现了一个映射函数 f: X -> Y 。而这个映射函数必须同时具有两个特点:

1. 如果 x1 != x2, 则 f (x1) != f(x2);

2. 对于每一个 y, 能够找到唯一的一个 x 使得 f(x) = y;

对于任何的线性函数,比如 f(x) = 2x,都满足这样的条件。


好了,如果了解了短址的本质,我们再来看它是如何实现的。

注明:在google URL shortener 服务中,它允许一个长 url 对应多个短的url。这可能是出于安全上的考虑。在本文中,我们不考虑这种情况。


实现:

短址的长度一般设为 6 位,而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的,所以6位的话,总共会有 62^6 ~= 568亿种组合,基本上够用了。在google URL shortener 服务中,短址长度为 5,大概有9亿多种组合.


假设我们用数据库来保存长地址和短地址的映射,那么,在表 LongtoShortURL 中,我们会有三列:

1. ID,int,  自动增长;

2. LURL,varchar,  // 长URL;

3. SURL, varchar,  // 短URL。


现在我们考虑通过如何长URL得到唯一的短URL。


在讲具体算法以前,先提一个问题:10进制数和16进制数之间的转换是否满足刚刚提到的映射函数 f: X -> Y中的两个条件?

答案: 是。


本文的思路也是利用进制之间的转换。因为我们总共有 62 个字母,我们可以自创一种进制,叫做 62 进制。其规则如下:

  1. 0  → a  
  2. 1  → b  
  3. ...  
  4. 25 → z  
  5. ...  
  6. 52 → 0  
  7. 61 → 9  

所以,对于每一个长地址,我们可以根据它的ID,得到一个6位的 62 进制数,这个6位的 62 进制数就是我们的短址。具体实现如下:

  1. public ArrayList<Integer> base62(int id) {  
  2.       
  3.     ArrayList<Integer> value = new ArrayList<Integer>();  
  4.     while (id > 0) {  
  5.         int remainder = id % 62;  
  6.         value.add(remainder);  
  7.         id = id / 62;  
  8.     }  
  9.       
  10.     return value;  
  11. }  

举例:

对于 ID = 138,通过 base62(138), 我们得到 value = [14, 2]。根据上面的对应规则表,我们可以得到其对应的短址为:aaaabn 。(由 value 得到具体的短址,可以通过switch 语句得到,因为代码太长,在此略过。)


当我们想通过短址找到所对应的长地址,方法也很简单,就是把62进制数转成10进制数即可,这样我们就可以得到长地址的ID了。代码如下:

  1. public static int base10(ArrayList<Integer> base62) {  
  2.     //make sure the size of base62 is 6  
  3.     for (int i = 1; i <= 6 - base62.size(); i++) {  
  4.         base62.add(00);  
  5.     }  
  6.       
  7.     int id = 0;  
  8.     int size = base62.size();  
  9.     for (int i = 0; i < size; i++) {  
  10.         int value = base62.get(i);  
  11.         id += (int) (value * Math.pow(62, size - i - 1));  
  12.     }  
  13.       
  14.     return id;  
  15. }  

比如,对于短址aaae9a,其62进制为[0, 0, 0, 4,61,0] ,则其长地址的ID 为[0, 0, 0, 4,61,0] = 0×62^5+ 0×62^4 + 0×62^3 + 4×62^2 + 61×62^1 + 0×62^0 = 1915810。有了ID,我们自然就可以得到长地址了。


参考:http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener (本文算法来源)

http://blog.sina.com.cn/s/blog_65db99840100lg4n.html

转载请注明出处:http://blog.csdn.net/beiyeqingteng

  评论这张
 
阅读(1566)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018