短网址具有独特但随机生成的字符串？

Question

所以我一直在尝试建立一个URL shortner，但我无法生成唯一但随机的字符串。random 字符串。我到处寻找解决方案，但没有找到，因此在这里发帖。

我有一个表，其中我得到自动生成的顺序主键（ID）对插入的记录。现在，我把这个ID，并运行一个双项函数，它变成了

0  → a
1  → b
...
25 → z
...
52 → 0
61 → 9

现在的问题是，生成的字符串不是随机的。比如说:

63 --> b1
64 --> b2
...
1836 --> bpa
1836 --> bpb

这是很容易猜到的。我甚至尝试将ID编码为Base64，但结果字符串又是可猜测的，如果我使用GUID代替并将其编码为Base64，那么结果字符串非常大。最大的字符串应该是7,8个字符--最好是3,4个字符。

我想知道bit.ly是怎么做的，他们生成的短网址总是独一无二的，而且是随机的。

Answer 1

你要做的是生成顺序键。第一个URL是1，下一个是2，等等。但你通过将每个键唯一地映射到不同的数字来混淆这些键。所以1可能变成76839427，2可能变成9935。然后你对这个数字进行base64编码。

好的事情是，你所要跟踪的是下一个连续的数字。这个过程是可逆的，所以你可以把9935变回2。

我给出了一个关于映射的例子 生成唯一（不重复）随机数的高效算法.

另一种可能性是使用 线性反馈移位寄存器 有很长的周期。你可以创建一个周期为2^64的。保证不重复，直到你生成2^64个数字。

请注意，这两种方法都不是真正的 "随机"。它们都是混淆方法 但只要付出足够的努力 有人就能破解这个算法 但他们也可以破解一个伪随机数生成器 But then, they could crack a pseudo -random number generator, too.

Answer 2

将顺序整数转化为非顺序的4字符令牌是相当容易的。如果你使用可逆算法，那么你也可以很容易地将这些令牌转换回可用于从数据库中检索URL的顺序整数。

注意事项 如果你打算开辟一个公共的URL缩短服务，那么只有4个字母数字字符的令牌可能很快就会被用完。但对于个人或公司网站来说，它们应该是绰绰有余的。下面描述的方法也适用于较长的标记，但如果你真的需要一个可以存储数十亿（或数万亿）URL的系统，那么你就需要更仔细地考虑如何组织所有这些数据。

A 线性同余发生器 是混淆数字的好方法。如果你的工作范围是从0到62⁴-1，那么显然你的模数 m 将是62⁴. 而由于原生因素的 m 是2和31，乘数 a 将必须是124的倍数以上的一个(如上所述). 的值。c 可以是任何相对质数的非零值，对 m. 例如，反函数相当相似。

function lcg($n) {
    # (10345073 - 1) % 124 == 0
    $m = 14776336; # = 62**4
    $a = 10345073;
    $c = 8912423;
    $n = ($n * $a + $c) % $m;
    return $n;
}

反函数是相当相似的。取而代之的是 a它使用其 模块化乘法逆 (模数 m)，而不是 c它使用 m−c:

function lcg_inv($n) {
    # (10345073 * 5661345) % (62**4) == 1
    $m = 14776336; # = 62**4
    $a_ = 5661345;
    $c_ = 5863913; # = $m-8912423
    $n = (($n + $c_) * $a_) % $m;
    return $n;
}

由于LCG很容易从几个输出值中预测出来，你可以通过随机调整符号的顺序来增加另一层混淆，以62为基数来表示这些数字(例如。W3qVL... 例如，用 abcde...)

function int_2_token($n) {
    $alf = 'W3qVLpEKDxn8vzG0SQPfIX2yO51JsHBYCRbouTatZ4hMdlmF67UcNiAgwke9jr';
    $tok = '';
    if ($n < 0 || $n >= 62**4) return ''; # Value out of range
    $n = lcg($n);
    for ($i=0; $i<4; $i++) {
        $r = $n % 62;
        $tok .= $alf[$r];
        $n = ($n - $r) / 62;
    }
    return $tok;
}

function token_2_int($tok) {
    $t = [ '0'=>15, '1'=>26, '2'=>22, '3'=>1,  '4'=>41, '5'=>25, '6'=>48, '7'=>49,
           '8'=>11, '9'=>59, 'A'=>54, 'B'=>30, 'C'=>32, 'D'=>8,  'E'=>6,  'F'=>47,
           'G'=>14, 'H'=>29, 'I'=>20, 'J'=>27, 'K'=>7,  'L'=>4,  'M'=>43, 'N'=>52,
           'O'=>24, 'P'=>18, 'Q'=>17, 'R'=>33, 'S'=>16, 'T'=>37, 'U'=>50, 'V'=>3, 
           'W'=>0,  'X'=>21, 'Y'=>31, 'Z'=>40, 'a'=>38, 'b'=>34, 'c'=>51, 'd'=>44,
           'e'=>58, 'f'=>19, 'g'=>55, 'h'=>42, 'i'=>53, 'j'=>60, 'k'=>57, 'l'=>45,
           'm'=>46, 'n'=>10, 'o'=>35, 'p'=>5,  'q'=>2,  'r'=>61, 's'=>28, 't'=>39,
           'u'=>36, 'v'=>12, 'w'=>56, 'x'=>9,  'y'=>23, 'z'=>13 ];
    $n = 0;
    if (!preg_match('/^[a-z0-9]{4}$/i', $tok)) return -1; # Invalid token
    for ($i=3; $i>=0; --$i) {
        $n = $n * 62 + $t[$tok[$i]];
    }
    return lcg_inv($n);
}

所以，当你得到一个新的要缩短的URL时，将它插入到你的数据库中，并赋予它一个自动递增的ID值，然后将这个ID值传递到 int_2_token() 以获得一个四字符的标记，用于缩短的URL。当请求这个缩短的URL时，将标记传递给 token_2_int() 来恢复这个ID，这样你就可以取回原来的URL。

---

请注意。 不要忘了，所有四字符号的集合包括了所有的 四字词语. 你可能要确保你的URL缩短器不会输出任何粗俗或攻击性的东西。