如何网站如goo.gl或的jsfiddle生成的URL codeS？ [英] How do sites like goo.gl or jsfiddle generate their URL codes?

问题描述

我想生成一个code如 goo.gl 和的的jsfiddle 网站（ http://jsfiddle.net/XzKvP/ ）。

I would like to generate a code like goo.gl and jsfiddle websites (http://jsfiddle.net/XzKvP/).

我想，给我太大的GUID，重复的字母数字code等。

I tried different things that give me too large of a guid, a repeating alphanumeric code, etc.

我想我应该能够根据我的数据库表的主键生成的字母数字code。这种方式，将是非重复？的PK是一个自增整数1。不过，不知道这是它应该怎么做。

I'm thinking I should be able to generate an alphanumeric code based on the Primary Key in my database table. This way it will be non-repeating? The PK is an auto-incremented integer by 1. But not sure that's how it should be done.

我要的code为的查找的随机的，但它的的不是的必须。 比如，我做的的不是的要项 1234 在我的数据库是 BCDE 和 1235 项是 BCDF 。

I want the code to look random, but it does NOT have to be. For example, I do NOT want item 1234 in my database to be BCDE and the 1235 item to be BCDF.

例如：

请注意网址 http://jsfiddle.net/XzKvP/ 有一个独特的5个字符code XzKvP 相关联的网页。我希望能够产生相同类型的code。

Notice how the url http://jsfiddle.net/XzKvP/ has a unique 5 character code XzKvP associated to the page. I want to be able to generate the same type of code.

goo.gl确实太： http://goo.gl/UEhtg 具有 UEhtg

goo.gl does it too: http://goo.gl/UEhtg has UEhtg

如何做到这一点？

推荐答案

基于随机子的解决方案都没有好，因为输出将发生碰撞。它可能发生prematurely（坏运气），它最终会发生时所产生的值列表变大。它甚至没有被这种大碰撞的概率变高（见生日攻击）。

The solutions based on a random substring are no good because the outputs will collide. It may happen prematurely (with bad luck), and it will eventually happen when the list of generated values grows large. It doesn't even have to be that large for the probability of collisions to become high (see birthday attack).

什么是好的这个问题是一个伪随机置换递增ID和其对应的，将在显示出来网址。这个方法保证在一个碰撞是不可能的，同时仍产生成输出空间小，为输入空间

What's good for this problem is a pseudo random permutation between the incrementing ID and its counterpart that will be shown in the URL. This technique guarantees that a collision is impossible, while still generating into an output space that is as small as the input space.

执行

我建议这个C＃版本 Feistel密码，提供32位的数据块，3个回合，一个全面的功能由伪随机生成的启发。

I suggest this C# version of a Feistel cipher with 32 bits blocks, 3 rounds and a round function that is inspired by pseudo-random generators.

private static double RoundFunction(uint input)
{
    // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
    // but it doesn't have to be reversible.
    // Must return a value between 0 and 1
    return ((1369 * input + 150889) % 714025) / 714025.0;
}

private static uint PermuteId(uint id)
{
    uint l1=(id>>16)&65535;
    uint r1=id&65535;
    uint l2, r2;
    for (int i = 0; i < 3; i++)
    {
        l2 = r1;
        r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
        l1 = l2;
        r1 = r2;
    }
    return ((r1 << 16) + l1);
}

要EX preSS的base62字符串排列的ID：

To express the permuted ID in a base62 string:

private static string GenerateCode(uint id)
{
    return ToBase62(PermuteId(id));
}

在 Base62 的功能是一样的的previous答案只不过是采用 UINT 而不是 INT （否则，这些功能都必须重写，以应对负面值）。

The Base62 function is the same as the previous answer except that is takes uint instead of int (otherwise these functions would have to be rewritten to deal with negative values).

自定义算法

RoundFunction 是算法的秘密武器。你可以将它更改为非公版，其中可能包括一个密钥。该型Feistel网络有两个非常漂亮的特性：

RoundFunction is the secret sauce of the algorithm. You may change it to a non-public version, possibly including a secret key. The Feistel network has two very nice properties:

• 就算供给 RoundFunction 是不可逆的，该算法保证了 PermuteId（）将在数学意义上的置换（至极意味着零碰撞）。

• even if the supplied RoundFunction is not reversible, the algorithm guarantees that PermuteId() will be a permutation in the mathematical sense (wich implies zero collision).

改变EX pression轮函数里面甚至轻轻将发生急剧变化的最终输出值列表。

changing the expression inside the round function even lightly will change drastically the list of final output values.

要注意的是把事情太琐碎全面EX pression会破坏伪随机效应，虽然它仍然工作在每一个独特的角度 PermuteId 输出。此外，一名前pression那会不会是在数学意义上的功能将与算法不兼容，因此如任何涉及随机（）是不允许的

Beware that putting something too trivial in the round expression would ruin the pseudo-random effect, although it would still work in terms of uniqueness of each PermuteId output. Also, an expression that wouldn't be a function in the mathematical sense would be incompatible with the algorithm, so for instance anything involving random() is not allowed.

Reversability

在目前的形式下， PermuteId 的功能是它自己的逆，这意味着：

In its current form, the PermuteId function is its own inverse, which means that:

PermuteId(PermuteId(id))==id

所以，给出该程序所产生的短字符串，如果你将其转换回 UINT 与 FromBase62 功能，并给出了输入到 PermuteId（），将返回相应的初始ID。这是pretty的冷静，如果你没有一个数据库来存储[内部ID / ShortString短]的关系：他们实际上并不需要存储

So given a short string produced by the program, if you convert it back to uint with a FromBase62 function, and give that as input to PermuteId(), that will return the corresponding initial ID. That's pretty cool if you don't have a database to store the [internal-ID / shortstring] relationships: they don't actually need to be stored!

生产甚至更短的字符串

以上功能的范围是32位，也就是从0约4十亿值 2 ^ 32-1 。为了EX preSS，范围在base62，需要6个字符。

The range of the above function is 32 bits, that is about 4 billion values from 0 to 2^32-1. To express that range in base62, 6 characters are needed.

由于只有5个字，我们可以希望重新present最多 62 ^ 5 值，这是一个有点不足1十亿。如果输出字符串被限制为5个字符，在code，应调整如下：

With only 5 characters, we could hope to represent at most 62^5 values, which is a bit under 1 billion. Should the output string be limited to 5 characters, the code should be tweaked as follows:

• 找到 N ，使得 N 均匀， 2 ^ N 是尽可能高，但低于 62 ^ 5 。这是28日，所以我们的，适合在实际输出范围 62 ^ 5 将是 2 ^ 28 或约268百万值。

• find N such that N is even and 2^N is as high as possible but lower than 62^5. That's 28, so our real output range that fits in 62^5 is going to be 2^28 or about 268 million values.

在 PermuteId ，使用 28 / = 14 位值 L1 和 R1 ，而不是16位，同时小心不要忽略输入的单个位（其中必须小于2 ^ 28）

in PermuteId, use 28/2=14 bits values for l1 and r1 instead of 16 bits, while being careful to not ignore a single bit of the input (which must be less than 2^28).

通过16383，而不是65535繁衍 RoundFunction 的结果，留在了14位不等。

multiply the result of RoundFunction by 16383 instead of 65535, to stay within the 14 bits range.

在 PermuteId 年底，重组 R1 和 L1 来形成 14 + 14 = 28 位值而不是32。

at the end of PermuteId, recombine r1 and l1 to form a 14+14=28 bits value instead of 32.

同样的方法可以适用于4个字符，用的输出范围 2 ^ 22 ，或大约400万的值。

The same method could be applied for 4 characters, with an output range of 2^22, or about 4 million values.

它看起来像没有

在上面的版本中，第一10产生起始ID为字符串= 1是：

In the version above, the first 10 produced strings starting with id=1 are:

cZ6ahF
3t5mM
xGNPN
dxwUdS
ej9SyV
cmbVG3
cOlRkc
bfCPOX
JDr8Q
eg7iuA

如果我做全面的功能一个微不足道的变化，即变为：

If I make a trivial change in the round function, that becomes:

ey0LlY
ddy0ak
dDw3wm
bVuNbg
bKGX22
c0s5GZ
dfNMSp
ZySqE
cxKH4b
dNqMDA

这篇关于如何网站如goo.gl或的jsfiddle生成的URL codeS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！