标点符(钱魏 Way)

短网址服务的构建

随着twitter和微博等服务的流行,短网址服务也流行了起来。目前提供短网址服务的网站也非常多。比如:

而短网址服务做得最好的应该就是:bit.ly(包括支持数据统计等) 了。使用短网址最多的场景主要是那些有字符数限制或者需要人工输入的场景。比如手机短信或者是印刷在出版物上的链接。

短网址服务说白了就是URL映射,将较长的URL映射成短字符串。短址本质上是实现了一个映射函数 f(x)-> y 。对于每一个 y, 能够找到唯一的一个 x 使得 f(x) = y。即不能产生一短URL地址对应多个长URL。可能的数据库存储格式为:

  • ID,int,  自动增长;
  • LURL,varchar,  // 长URL;
  • SURL, varchar,  // 短URL。

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

方案一:数据库自增长ID转换进制

使用自增长ID首先是不会产生重复,但是由于自增长ID由于是10进制,就会使URl变得很长,可以采用进制压缩的方式将URL变短。为了更好的提升URL的可读性,需要在制作URL的时候考虑到:

  • 考虑到大小写的字母读音相同,所以暂定都使用大写字母。这样便于口头传播。
  • 考虑到发音相近,可以将字母中的L,R,I,M,N,G,J都去除。(或者再加上B,P)
  • 考虑到字形相同,可以将0和O都去除。便于识别。

于是可用字符为26+10-7-2=2。然后需要确定最小需要的位数:

  • 27^3=19683
  • 27^4=531441
  • 27^5=14348907
  • 27^6=387420489

从上面的数据可以看到,使用了六位就可足以对我们的URL进行加密。相关的算法:

方案二:URL hash计算

对URL进行处理的时候很容易想到MD5,MD5长度固定、冲突概率小等特性都是优势,但是由于MD5长度为32个字符,所以用来做短网址可能不太合适,那么能不能以MD5为基础,将其字符进行缩短呢。以下为这个方案的具体实现:

  1. 将长网址用md5算法生成32位签名串,分为4段,,每段8个字符;
  2. 对这4段循环处理,取每段的8个字符, 将他看成16进制字符串与0x3fffffff(30位1)的位与操作,超过30位的忽略处理;
  3. 将每段得到的这30位又分成6段,每5位的数字作为字母表的索引取得特定字符,依次进行获得6位字符串;
  4. 这样一个md5字符串可以获得4个6位串,取里面的任意一个就可作为这个长url的短url地址。

算法内容:

由于上述算法对Md5进行了处理和截取,所以算法的重复的几率大约是n/(32^6) 也就是n/1,073,741,824(n是数据库中记录的条数),所以不建议使用。

参考地址:
码字很辛苦,转载请注明来自标点符《短网址服务的构建》

评论

  1. 三断笛 #1

    可以试试这样:
    短网址不要求可读性,所以短网址可以区分大小写,包括特殊字符。这样下来至少可以有26+26+10个字符,还不够的话,可以限制短网址有效期。
    短网址不重复可以这样做,不管源网址是什么,只要注册一个就按顺序生成一个短网址,和一个顺序ID,短网址为1位至~6位长度,从0~zzzzzz递增,(每1位按ascii码递增)可以从ID号得到这短网址,也可以从这短网址得到ID号。然后根据ID号读取原网址进行转换,这种Hash简单精确也不失效率。

    回复
    2014-08-26