我想创建一个URL缩短服务,你可以写一个长URL到输入字段和服务缩短URL为“http://www.example.org/abcdef”。

可以用包含a-z, a-z和0-9的6个字符的字符串代替"abcdef"。这样就有560 ~ 570亿个可能的字符串。

我的方法:

我有一个有三列的数据库表:

Id,整数,自动递增 long, string,用户输入的长URL 短,字符串,缩短的URL(或只有六个字符)

然后将长URL插入到表中。然后,我将为“id”选择自动递增的值,并构建它的散列。这个散列应该作为“short”插入。但是我应该构建什么样的哈希呢?像MD5这样的哈希算法会创建太长的字符串。我认为我不用这些算法。一个自建的算法也可以。

我的想法:

对于“http://www.google.de/”,我得到了自动增量id 239472。然后我执行以下步骤:

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

可以不断重复,直到这个数不能被整除为止。你认为这是一个好方法吗?你有更好的主意吗?

由于对这个主题的持续兴趣,我已经发布了一个高效的GitHub解决方案,包括JavaScript、PHP、Python和Java的实现。如果你喜欢,添加你的解决方案:)


当前回答

我将继续您的“将数字转换为字符串”方法。但是,如果您的ID是质数且大于52,您将意识到您提出的算法将失败。

理论背景

你需要一个双射函数f。这是必要的,这样你就可以为你的f(123) = 'abc'函数找到一个逆函数g('abc') = 123。这意味着:

一定不存在x1 x2 (x1≠x2)使得f(x1) = f(x2) 对于每一个y,你必须能找到一个x,使f(x) = y。

如何将ID转换为缩短的URL

Think of an alphabet we want to use. In your case, that's [a-zA-Z0-9]. It contains 62 letters. Take an auto-generated, unique numerical key (the auto-incremented id of a MySQL table for example). For this example, I will use 12510 (125 with a base of 10). Now you have to convert 12510 to X62 (base 62). 12510 = 2×621 + 1×620 = [2,1] This requires the use of integer division and modulo. A pseudo-code example: digits = [] while num > 0 remainder = modulo(num, 62) digits.push(remainder) num = divide(num, 62) digits = digits.reverse Now map the indices 2 and 1 to your alphabet. This is how your mapping (with an array for example) could look like: 0 → a 1 → b ... 25 → z ... 52 → 0 61 → 9 With 2 → c and 1 → b, you will receive cb62 as the shortened URL. http://shor.ty/cb

如何将缩短的URL解析为初始ID

反过来就更容易了。你只需要在字母表中反向查找。

E9a62将被解析为“字母表中的第4、61和0个字母”。 E9a62 = [4,61,0] = 4×622 + 61×621 + 0×620 = 1915810 现在找到WHERE id = 19158的数据库记录并执行重定向。

示例实现(由评论者提供)

c++ Python Ruby Haskell c# CoffeeScript Perl

其他回答

alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10))

def lookup(k, a=alphabet):
    if type(k) == int:
        return a[k]
    elif type(k) == str:
        return a.index(k)


def encode(i, a=alphabet):
    '''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.'''
    try:
        i = int(i)
    except Exception:
        raise TypeError("Input must be an integer.")

    def incode(i=i, p=1, a=a):
        # Here to protect p.                                                                                                                                                                                                                
        if i <= 61:
            return lookup(i)

        else:
            pval = pow(62,p)
            nval = i/pval
            remainder = i % pval
            if nval <= 61:
                return lookup(nval) + incode(i % pval)
            else:
                return incode(i, p+1)

    return incode()



def decode(s, a=alphabet):
    '''Takes a base 62 string in our alphabet and returns it in base10.'''
    try:
        s = str(s)
    except Exception:
        raise TypeError("Input must be a string.")

    return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a

这是我的版本,给任何需要的人。

这是一个不错的PHP URL编码函数…

// From http://snipplr.com/view/22246/base62-encode--decode/
private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') {
    $str = '';
    do {
        $i = fmod($val, $base);
        $str = $chars[$i] . $str;
        $val = ($val - $i) / $base;
    } while($val > 0);
    return $str;
}

看看https://hashids.org/,它是开源的,有多种语言版本。

他们的页面概述了其他方法的一些陷阱。

基于Xeoncross类的函数

function shortly($input){
$dictionary = ['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','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','6','7','8','9'];
if($input===0)
    return $dictionary[0];
$base = count($dictionary);
if(is_numeric($input)){
    $result = [];
    while($input > 0){
        $result[] = $dictionary[($input % $base)];
        $input = floor($input / $base);
    }
    return join("", array_reverse($result));
}
$i = 0;
$input = str_split($input);
foreach($input as $char){
    $pos = array_search($char, $dictionary);
    $i = $i * $base + $pos;
}
return $i;
}

这是我所使用的:

# Generate a [0-9a-zA-Z] string
ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91))

def encode_id(id_number, alphabet=ALPHABET):
    """Convert an integer to a string."""
    if id_number == 0:
        return alphabet[0]

    alphabet_len = len(alphabet) # Cache

    result = ''
    while id_number > 0:
        id_number, mod = divmod(id_number, alphabet_len)
        result = alphabet[mod] + result

    return result

def decode_id(id_string, alphabet=ALPHABET):
    """Convert a string to an integer."""
    alphabet_len = len(alphabet) # Cache
    return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))])

它非常快,可以取很长的整数。