当前位置:Gxlcms > Python > Python实现短网址ShortUrl的Hash运算实例讲解

Python实现短网址ShortUrl的Hash运算实例讲解

时间:2021-07-01 10:21:17 帮助过:72人阅读

本文实例讲述了Python实现短网址ShortUrl的Hash运算方法。分享给大家供大家参考。具体如下:

shorturl实现常见的做法都是将原始Url存储到数据库,由数据库返回一个对应ID。

以下要实现的是不用数据库支持就对原始URL进行shorturl hash。说到这里我们很容易想到MD5,固定长度,冲突概率小,但是32个字符,太长?我们以MD5为基础,将其字符缩短,同时要保证一定数量范围内hash不会冲突。

我们分成两个步骤来实现。

第一步算法:

① 将长网址用md5算法生成32位签名串,分为4段,,每段8个字符;
② 对这4段循环处理,取每段的8个字符, 将他看成16进制字符串与0x3fffffff(30位1)的位与操作,超过30位的忽略处理;
③ 将每段得到的这30位又分成6段,每5位的数字作为字母表的索引取得特定字符,依次进行获得6位字符串;
④ 这样一个md5字符串可以获得4个6位串,取里面的任意一个就可作为这个长url的短url地址。
(出现重复的几率大约是n/(32^6) 也就是n/1,073,741,824,其中n是数据库中记录的条数)

我们就得到了4个6位串,可是选哪个作为最终的hash结果呢,随机选肯定是不行的,同样的url两次hash就会得出不同的结果。接下来根据原始url的特征进行选择,并且将hash冲突的可能性控制在同一个domain内:

第二步算法:

①从原始url中提取域名,提取数字(最多后6位);
②将所得的数字与4取模,根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个;
③从域名中提取特征串:一级域名中的第一个字符和后面二个辅音(如果辅音不足2个取任意前两个);
④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl;
(后两个步骤是将冲突控制在一个domain内)

ShortUrl.py

  1. #encoding:utf-8
  2. __author__ = 'James Lau'
  3. import hashlib
  4. import re
  5. def __original_shorturl(url):
  6. '''
  7. 算法:
  8. ① 将长网址用md5算法生成32位签名串,分为4段,,每段8个字符;
  9. ② 对这4段循环处理,取每段的8个字符, 将他看成16进制字符串与0x3fffffff(30位1)的位与操作,超过30位的忽略处理;
  10. ③ 将每段得到的这30位又分成6段,每5位的数字作为字母表的索引取得特定字符,依次进行获得6位字符串;
  11. ④ 这样一个md5字符串可以获得4个6位串,取里面的任意一个就可作为这个长url的短url地址。
  12. (出现重复的几率大约是n/(32^6) 也就是n/1,073,741,824,其中n是数据库中记录的条数)
  13. '''
  14. base32 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
  15. 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
  16. 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
  17. 'y', 'z',
  18. '0', '1', '2', '3', '4', '5'
  19. ]
  20. m = hashlib.md5()
  21. m.update(url)
  22. hexStr = m.hexdigest()
  23. hexStrLen = len(hexStr)
  24. subHexLen = hexStrLen / 8
  25. output = []
  26. for i in range(0,subHexLen):
  27. subHex = '0x'+hexStr[i*8:(i+1)*8]
  28. res = 0x3FFFFFFF & int(subHex,16)
  29. out = ''
  30. for j in range(6):
  31. val = 0x0000001F & res
  32. out += (base32[val])
  33. res = res >> 5
  34. output.append(out)
  35. return output
  36. def shorturl(url):
  37. '''
  38. 算法:
  39. ①从原始url中提取域名,提取数字(最多后6位);
  40. ②将所得的数字与4取模,根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个;
  41. ③从域名中提取特征串:一级域名中的第一个字符和后面二个辅音(如果辅音不足2个取任意前两个);
  42. ④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl;
  43. (后两个步骤是将冲突控制在一个domain内)
  44. '''
  45. match_full_domain_regex = re.compile(u'^https?:\/\/(([a-zA-Z0-9_\-\.]+[a-zA-Z0-9_\-]+\.[a-zA-Z]+)|([a-zA-Z0-9_\-]+\.[a-zA-Z]+)).*$')
  46. match_full_domain = match_full_domain_regex.match(url)
  47. if match_full_domain is not None:
  48. full_domain = match_full_domain.group(1)
  49. else:
  50. return None
  51. not_numeric_regex = re.compile(u'[^\d]+')
  52. numeric_string = not_numeric_regex.sub(r'',url)
  53. if numeric_string is None or numeric_string=='':
  54. numeric_string = '0'
  55. else:
  56. numeric_string = numeric_string[-6:]
  57. domainArr = full_domain.split('.')
  58. domain = domainArr[1] if len(domainArr)==3 else domainArr[0]
  59. vowels = 'aeiou0-9'
  60. if len(domain)<=3:
  61. prefix = domain
  62. else:
  63. prefix = re.compile(u'[%s]+'%vowels).sub(r'',domain[1:])
  64. prefix = '%s%s'%(domain[0],prefix[:2]) if len(prefix)>=2 else domain[0:3]
  65. t_shorturl = __original_shorturl(url)
  66. t_choose = int(numeric_string)%4
  67. result = '%s%s'%(prefix,t_shorturl[t_choose])
  68. return result

希望本文所述对大家的Python程序设计有所帮助。

人气教程排行