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

本文实例讲述了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

#encoding:utf-8
__author__ = 'James Lau'
import hashlib
import re
def __original_shorturl(url):
  '''
  算法:
  ① 将长网址用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是数据库中记录的条数)
  '''
  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'
  ]
  m = hashlib.md5()
  m.update(url)
  hexStr = m.hexdigest()
  hexStrLen = len(hexStr)
  subHexLen = hexStrLen / 8
  output = []
  for i in range(0,subHexLen):
    subHex = '0x'+hexStr[i*8:(i+1)*8]
    res = 0x3FFFFFFF & int(subHex,16)
    out = ''
    for j in range(6):
      val = 0x0000001F & res
      out += (base32[val])
      res = res >> 5
    output.append(out)
  return output
def shorturl(url):
  '''
  算法:
  ①从原始url中提取域名,提取数字(最多后6位);
  ②将所得的数字与4取模,根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个;
  ③从域名中提取特征串:一级域名中的第一个字符和后面二个辅音(如果辅音不足2个取任意前两个);
  ④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl;
  (后两个步骤是将冲突控制在一个domain内)
  '''
  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]+)).*$')
  match_full_domain = match_full_domain_regex.match(url)
  if match_full_domain is not None:
    full_domain = match_full_domain.group(1)
  else:
    return None
  not_numeric_regex = re.compile(u'[^\d]+')
  numeric_string = not_numeric_regex.sub(r'',url)
  if numeric_string is None or numeric_string=='':
    numeric_string = '0'
  else:
    numeric_string = numeric_string[-6:]
  domainArr = full_domain.split('.')
  domain = domainArr[1] if len(domainArr)==3 else domainArr[0]
  vowels = 'aeiou0-9'
  if len(domain)<=3:
    prefix = domain
  else:
    prefix = re.compile(u'[%s]+'%vowels).sub(r'',domain[1:])
    prefix = '%s%s'%(domain[0],prefix[:2]) if len(prefix)>=2 else domain[0:3]
  t_shorturl = __original_shorturl(url)
  t_choose = int(numeric_string)%4
  result = '%s%s'%(prefix,t_shorturl[t_choose])
  return result

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

(0)

相关推荐

  • Python中使用hashlib模块处理算法的教程

    Python的hashlib提供了常见的摘要算法,如MD5,SHA1等等. 什么是摘要算法呢?摘要算法又称哈希算法.散列算法.它通过一个函数,把任意长度的数据转换为一个长度固定的数据串(通常用16进制的字符串表示). 举个例子,你写了一篇文章,内容是一个字符串'how to use python hashlib - by Michael',并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'.如果有人篡改了你的文章,并发表为'how to use pytho

  • python中os操作文件及文件路径实例汇总

    本文实例讲述了python中os操作文件及文件路径的方法.分享给大家供大家参考.具体分析如下: python获取文件上一级目录:取文件所在目录的上一级目录 复制代码 代码如下: os.path.abspath(os.path.join(os.path.dirname('settings.py'),os.path.pardir)) os.path.pardir是父目录,os.path.abspath是绝对路径 举例具体看一下输出: 复制代码 代码如下: print os.path.dirname(

  • Python实现通过文件路径获取文件hash值的方法

    本文实例讲述了Python实现通过文件路径获取文件hash值的方法.分享给大家供大家参考,具体如下: import hashlib import os,sys def CalcSha1(filepath): with open(filepath,'rb') as f: sha1obj = hashlib.sha1() sha1obj.update(f.read()) hash = sha1obj.hexdigest() print(hash) return hash def CalcMD5(fi

  • python 文件和路径操作函数小结

    1: os.listdir(path) //path为目录 功能相当于在path目录下执行dir命令,返回为list类型 print os.listdir('..') 2: os.path.walk(path,visit,arg) path :是将要遍历的目录 visit :是一个函数指针,函数圆形为: callback(arg,dir,fileList) 其中arg为为传给walk的arg , dir是path下的一个目录,fileList为dir下的文件和目录组成的list, arg:传给v

  • python实现simhash算法实例

    Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空间换时间,系统内存吃不消. 复制代码 代码如下: #!/usr/bin/python# coding=utf-8class simhash: #构造函数    def __

  • python中的hashlib和base64加密模块使用实例

    看到好几位博主通过对模块的各个击破学习python,我也效法一下,本篇说一下python中加密涉及到的模块. hashlib hashlib模块支持的加密算法有md5 sha1 sha224 sha256 sha384 sha512(加密原理请参考此处),使用起来也很简单. 以md5加密为例,有两种方法: 一. 追加模式 代码示例: 复制代码 代码如下: import hashlib #引入hashlib模块    mm = hashlib.md5() #创建一个md5对象  mm.update

  • Python文件读取的3种方法及路径转义

    1.文件的读取和显示 方法1: 复制代码 代码如下: f=open(r'G:\2.txt')  print f.read()  f.close() 方法2:   复制代码 代码如下: try:      t=open(r'G:\2.txt')      print t.read()  finally:      if t:         t.close() 方法3: 复制代码 代码如下: with open(r'g:\2.txt') as g:      for line in g:     

  • 用Python实现通过哈希算法检测图片重复的教程

    Iconfinder 是一个图标搜索引擎,为设计师.开发者和其他创意工作者提供精美图标,目前托管超过 34 万枚图标,是全球最大的付费图标库.用户也可以在 Iconfinder 的交易板块上传出售原创作品.每个月都有成千上万的图标上传到Iconfinder,同时也伴随而来大量的盗版图.Iconfinder 工程师 Silviu Tantos 在本文中提出一个新颖巧妙的图像查重技术,以杜绝盗版. 我们将在未来几周之内推出一个检测上传图标是否重复的功能.例如,如果用户下载了一个图标然后又试图通过上传

  • Python3实现从指定路径查找文件的方法

    本文实例讲述了Python3实现从指定路径查找文件的方法.分享给大家供大家参考.具体实现方法如下: 这里给定一个搜索路径,根据这个路径请求和请求的文件名,找到第一个符合要求的文件 import os def search_file(file_name, search_path, pathsep = os.pathsep): for path in search_path.split(pathsep): candidate = os.path.join(path, file_name) if os

  • python实现哈希表

    复制代码 代码如下: #! /usr/bin/env python#coding=utf-8#实现哈希表(线性地址再散列) def ChangeKey(key,m,di):    key01=(key+di) % m    return key01 a=raw_input("Please entry the numbers:\n").split()m=len(a)dict01={}for i in a:    key=int(i)%m    if "%s"%key

随机推荐