ShortUrl Hash 의 실현

shorturl 에서 흔히 볼 수 있 는 방법 은 원본 Url 을 데이터베이스 에 저장 하고 데이터베이스 에서 대응 하 는 ID 를 되 돌려 주 는 것 입 니 다.
다음은 데이터베이스 지원 없 이 원본 URL 에 shorturl hash 를 진행 하 는 것 입 니 다.여기까지 말 하면 우 리 는 MD5 를 쉽게 생각 할 수 있 습 니 다. 고정 길이, 충돌 확률 이 낮 지만 32 글자, 너무 깁 니까?우 리 는 MD5 를 바탕 으로 그 문 자 를 단축 시 키 는 동시에 일정한 수량의 범위 내 에서 hash 가 충돌 하지 않도록 해 야 한다.
우 리 는 두 단계 로 나 누 어 실현 한다.
첫 번 째 알고리즘:    ① 긴 주 소 를 md5 알고리즘 으로 32 비트 서명 문자열 을 만 들 고 4 단 으로 나 누 어 8 글자 로 나눈다.    ② 이 4 단 순환 처리 에 대해 서 는 단락 당 8 개의 문 자 를 가 져 와 16 진 문자열 과 0x3ffffff f (30 비트 1) 의 위치 와 작업 으로 보고 30 비트 가 넘 는 무시 처리 로 봅 니 다.    ③ 각 단락 에서 얻 은 이 30 자 리 를 6 단 으로 나 누고 5 자리 의 숫자 를 자모표 의 색인 으로 특정 문 자 를 얻어 6 자리 문자열 을 순서대로 얻는다.    ④ 이러한 md5 문자열 은 6 개의 문자열 4 개 를 얻 을 수 있 으 며, 그 중 하 나 를 가 져 오 면 이 긴 url 의 짧 은 url 주소 로 사용 할 수 있 습 니 다.    (중복 이 발생 할 확률 은 n / (32 ^ 6) 즉 n / 1, 073, 741, 824 이 며, 그 중 n 은 데이터베이스 에 기 록 된 개수 이다)
우 리 는 4 개의 6 개의 꼬치 를 얻 었 습 니 다. 그러나 어떤 것 을 최종 hash 결과 로 선택 하 시 겠 습 니까? 무 작위 로 선택 하면 안 됩 니 다. 같은 url 에서 두 번 hash 를 선택 하면 서로 다른 결 과 를 얻 을 수 있 습 니 다.다음은 원본 url 의 특징 에 따라 선택 하고 hash 충돌 가능성 을 같은 domain 에서 제어 합 니 다.
두 번 째 알고리즘:
    ① 원본 url 에서 도 메 인 이름 을 추출 하고 숫자 (최대 6 자리) 를 추출 합 니 다.    ② 얻 은 숫자 와 4 를 모델 로 하고 얻 은 나머지 에 따라 첫 번 째 알고리즘 에서 얻 은 4 개의 shorturl 중 어느 것 을 선택 할 지 결정 한다.    ③ 도 메 인 이름 에서 특징 문자열 추출: 1 급 도 메 인 이름 의 첫 번 째 문자 와 뒤의 두 자음 (자음 이 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