0

所以我一直在尝试构建一个更短的 URL，但我无法生成唯一但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 是如何做到的？他们生成的短 URL 始终是唯一且随机的。

4

2 回答 2

3

将顺序整数转换为非顺序的 4 字符标记相当容易。如果您使用可逆算法，那么您还可以轻松地将这些令牌转换回可用于从数据库中检索 URL 的连续整数。

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

线性同余生成器是混淆数字的好方法。如果您正在使用从 0 到 62 4 -1 的范围，那么显然您的模数m将是 62 4。并且由于m的质因数是 2 和 31，因此乘数a必须比 124 的倍数多 1（如此处所述）。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，它使用它的模乘逆（mod 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 缩短器不会输出任何粗俗或令人反感的内容。

于 2020-04-28T15:39:58.547 回答
2

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

好消息是您只需要跟踪下一个序列号。该过程是可逆的，因此您可以将 9935 变回 2。

我在Efficient algorithm for generate unique (non-repeating) random numbers中给出了一个映射示例。

另一种可能性是使用长周期的线性反馈移位寄存器。您可以创建一个周期为 2^64 的周期。保证在您生成 2^64 个数字之前不会重复。

请注意，这些都不是真正的“随机”。它们是混淆的方法，但只要付出足够的努力，就会有人破解算法。但是，他们也可以破解一个伪随机数生成器。

于 2020-04-28T13:46:43.770 回答