24 July 2014
关于网址压缩的调研和自己的理解。

现在新浪、谷歌都提供了网址压缩服务,访问被压缩的网址,可以自动跳转到目标网址。对于访问者来说,除了网址节约了一些存储空间,别的也没啥好处吧,不过确实越来越火。

要开发短网址,一般有两种思路。第一种,就是生成个码,把码和原始网址的对应关系放到数据库里面,压缩的时候存进去,读取的时候去库里找;还有一种方式是把原始网址按照一定方式压缩,压成比较短的。

先开始肯定是想着用第二种方式,不用数据库,只用算法就能实现压缩,听着就很牛逼。有人说可以用gzip压缩,用Python试了一下,压出来的比原始的还长。。。要是用AES这种去压,估计也短不了。看来必须要借助数据库了。

用数据库,肯定要存一个原始网址,问题就是解决短码(就是短网址后面跟着的那个乱码)的问题。比较传统的方法,就是用整数来存,从1开始,这样。先开始出来的就是00001、00002这种,而且短码都是递增的,随机不起来,看着也不好看。

压缩文本还有一种思路,将文本视为数字,增加这些数字的底数。如果原本的底数是10进制,升到100进制,长度肯定缩短。进制越高越好。下面就是要看HTTP自身URL支持多少字符。HTTP的URL支持0到9十个数字,52个字母(包括大小写),还有一些其它字符,如下表所示。但是这些特殊字符在URL里面都是用用途的,所以不能用来编码。那么,显而易见,只能使用数字和大小写字母,也就是62个。将URL压缩成62进制,是最短的压缩方式了。

除了普通的字母,数字,中文,还有特殊字符,但是规范的使用应该是使用字符转义。
“+” URL 中+号表示空格 %2B
“空格” URL中的空格可以用+号或者编码 %20
“/” 分隔目录和子目录 %2F
“?” 分隔实际的 URL 和参数 %3F
“%” 指定特殊字符 %25
“#” 表示书签 %23
“&” URL 中指定的参数间的分隔符 %26
“=” URL 中指定参数的值 %3D
“" 表示目录路径 %5C
“.” 句号 %2E
“:” 冒号 %3A

MD5加密,可以将任意文本生成一个32位的数字,每一位用16进制表示。然后转成上面提到的62进制数字,这样既不会发生碰撞,又能够起到压缩效果。试了一下,压缩完长度是12。去查了一下,谷歌提供的短网址提供5位压缩码,而新浪提供的是7位编码。看来这样还是不行。

最后,短码就只能是用ID来表示了,从0算起,这样可以保证长度不会太长,并且不会碰撞。5位62进制数字,可以表示62^5个短网址,算下来是9亿多个。我觉得妥妥够用了。

最后还有一个问题,就是上面提到的,ID是连续分配的,短网址也无法打散。去Github找了一个用Python写的打散算法,设定一个区间,将区间内的数字反转。比如,设定区间位8,要打散的ID是100000001,共9位,那么,反转之后就是110000000。这样,下一个数字100000010,打散之后是101000000。再对其进行62进制压缩之后,两个连续的URL也可以保证短网址完全打散,并且不会发生碰撞。


######参考文献

原文链接:网址压缩的调研分析,转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;