最新消息:

短网址服务的构建

技术 admin 1415浏览 0评论

转自:http://www.biaodianfu.com/url-shorter.html

随着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进行加密。相关的算法:

def dehydrate(integer,bit):
    digits =['1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','H','K','P','Q','S','T','U','V','W','X','Y','Z'] 
    if integer == 0:
        return '0'
    string = ""
    base = len(digits)
    while integer > 0 :
        remainder = integer % base
        string = digits[remainder] + string
        integer /= base
    if len(string) < bit:
        string = digits[0] * (bit - len(string)) + string
        return string
    else:
        return string

方案二: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地址。

算法内容:

#-*- coding:utf-8 -*-
import hashlib
def shorten(LURL):
    base32 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
              'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
              'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
              'y', 'z',
              '0', '1', '2', '3', '4', '5'
    ]
    output = []
    hex = hashlib.md5(LURL).hexdigest()
    for i in range(4):
        subHex = hex[i*8:(i+1)*8]
        hexint = 0x3FFFFFFF & eval("0x"+subHex)
        out = ""
        for j in range(6):
            index =  0x0000001F & hexint
            out +=  base32[index]
            hexint = hexint >> 5
        output.append(out)
    return output

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

参考地址:

 

 

 

 

转载请注明:jinglingshu的博客 » 短网址服务的构建


Warning: Use of undefined constant PRC - assumed 'PRC' (this will throw an Error in a future version of PHP) in /usr/share/nginx/html/wp-content/themes/d8/comments.php on line 17
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. @@@ Cory Hardrict, is a talented actor known for his roles in American Sniper, Transcendence, and Battle: Los Angeles聽just to name a few. He will now join the cast of the Sony Pictures crime drama November Criminals about a聽teenager who takes on his own investigation of a murder in Washington D.C. Plus check out his interview with Blogxilla below where he talks about making it in Hollywood, losing his mother and brother, and raising his son with his wife Tia Mowry. More about November Criminals, according to : 鈥婼teven Knight adapted the script from Sam Munson鈥檚 2011 novel about two teenagers who venture into the underbelly of Washington, D.C., to investigate a friend鈥檚 murder while falling in love for the first time. SPWA acquired distribution rights for the film in January; production is under way in D.C., and Beth O鈥橬eil (鈥淛ack Goes Boating鈥? is producing alongside Erika Olde of Black Bicycle Entertainment and Lotus. Black Bicycle Entertainment is also co-financing the film with Lotus, which is handling remaining international sales.
    wotoadgi4年前 (2015-08-27)回复