goo.glやjsfiddleなどのサイトでURLコードを生成するにはどうすればよいですか？

Question

goo.glとjsfiddleのウェブサイト（http://jsfiddle.net/XzKvP/）のようなコードを生成したいと思います。

私は私が私のデータベーステーブルの主キーに基づく英数字コードを生成することができるはずと思ってい

など、繰り返し英数字コード、私のGUIDの大きすぎるを与える別のものを試してみました。これは反復されないでしょうか？ PKは1だけ自動的にインクリメントされた整数です。しかし、それがどのように行われるべきかはわかりません。

私はにコードをしたいがランダムに見えるが、それはませはする必要がありません。 例えば、私はませはBCDEとBCDFすべき1235項目であることを私のデータベース内のアイテム1234をしたいです。

例：URL http://jsfiddle.net/XzKvP/はユニークな5文字のコードページに関連したXzKvPを持っているか

注意してください。同じタイプのコードを生成できるようにしたい。

goo.glは、あまりにもそれをしない：http://goo.gl/UEhtgは、これがどのように行われるかUEhtg

を持っていますか？

Answer 1

出力が衝突するため、ランダムな部分文字列に基づいた解は良くありません。それは時期尚早に（不運を伴って）起こる可能性があり、生成された値のリストが大きくなると最終的に発生します。衝突の可能性が高くなるほど大きなものである必要はありません（birthday attack参照）。

この問題には、URLに表示される増分IDと対応するIDの間にpseudo random permutationがあります。この技術は、入力空間と同じくらい小さい出力空間に生成しながら、衝突が不可能であることを保証します。

実装

Iは32ビットブロック、3ラウンドと擬似乱数発生器触発されラウンド関数とFeistel cipherのこのC＃バージョンを示唆しています。

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); 
} 

は、base62文字列に並べ替えIDを発現させるために：

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

Base62機能が同じであることを除いてthe previous answerがそうでなければ、これらの機能は、に書き換えなければならない（uint代わりにintをとるよう負の値を扱う）。アルゴリズム

RoundFunctionをカスタマイズ

は、アルゴリズムの秘密のソースです。秘密鍵を含む非公開のバージョンに変更することができます。 Feistel構造は、2つの非常に素敵なプロパティがあります。

• 供給RoundFunctionがPermuteId()は、数学的な意味（ウィッヒはゼロ衝突を意味する）で置換されることを、アルゴリズムを保証可逆的でない場合であっても。

• ラウンド関数内の式を軽くでも変更すると、最終出力値のリストが大幅に変更されます。

は注意してください、それがまだ各PermuteId出力の独自の観点で働くだろうが、擬似ランダム効果を台無しにラウンド式にあまりにも些細な何かを置きます。また、数学的な意味での関数ではない式はアルゴリズムと互換性がないので、例えばrandom()を含むものは許されません。

Reversability

現在の形で、PermuteId機能があることを意味し、独自の逆数、である：あなたが戻ってそれを変換する場合

PermuteId(PermuteId(id))==id 

だから、プログラムによって生成短い文字列を与えられましたFromBase62関数を持つuintに変換し、対応する初期IDを返すPermuteId()への入力として与えます。 [internal-ID/shortstring]関係を格納するデータベースがない場合、これはかなりクールです。実際には格納する必要はありません！

製造も短いストリング

上記機能の範囲は、0から2^32-1約40億の値であり、32ビットです。その範囲をbase62で表現するには、6文字が必要です。

わずか5文字で、最大で62^5の値を表すことができます（これは10億を少し下回ります）。出力文字列が5つの文字に制限する必要があり、次のように、コードを微調整する必要があります。

• Nは、このようなNが偶数で、2^Nはできるだけ高いが62^5よりも低くなっていることがわかります。それは28だから、62^5に収まる実際の出力範囲は2^28または約2億6800万の値になるでしょう。 PermuteIdに

• 、に注意しては（2^28未満でなければならない）入力の単一のビットを無視していないが、代わりに16ビットでl1とr128/2=14ためのビット値を使用します。

• RoundFunctionの結果に65535の代わりに16383を掛けて、14ビットの範囲内にとどまる。 PermuteIdの終わりに

• 、r1とl1は2^22の出力範囲で、代わりに32と同様の方法で4つの文字に適用することができる

の14+14=28ビット値を形成するために再結合し、又は約400万の価値。

が、それは上記のバージョンでは

のように何を求めず、最初の10は、ID = 1で始まる文字列が生成されます

 
cZ6ahF 
3t5mM 
xGNPN 
dxwUdS 
ej9SyV 
cmbVG3 
cOlRkc 
bfCPOX 
JDr8Q 
eg7iuA 

私はラウンド関数内の些細な変更を加えた場合、それは次のようになります。

 
ey0LlY 
ddy0ak 
dDw3wm 
bVuNbg 
bKGX22 
c0s5GZ 
dfNMSp 
ZySqE 
cxKH4b 
dNqMDA 

Answer 2

5桁のコードをベース62表記の数字と考えることができます。「数字」は26小文字と26大文字、0から9までの数字です（26 + 26 + 10桁）合計で。ここで

private static char Base62Digit(int d) { 
    if (d < 26) { 
     return (char)('a'+d); 
    } else if (d < 52) { 
     return (char)('A'+d-26); 
    } else if (d < 62) { 
     return (char)('0'+d-52); 
    } else { 
     throw new ArgumentException("d"); 
    } 
} 

static string ToBase62(int n) { 
    var res = ""; 
    while (n != 0) { 
     res = Base62Digit(n%62) + res; 
     n /= 62; 
    } 
    return res; 
} 

private static int Base62Decode(char c) { 
    if (c >= '0' && c <= '9') { 
     return 52 + c - '0'; 
    } else if (c >= 'A' && c <= 'Z') { 
     return 26 + c - 'A'; 
    } else if (c >= 'a' && c <= 'z') { 
     return c - 'a'; 
    } else { 
     throw new ArgumentException("c"); 
    } 
} 

static int FromBase62(string s) { 
    return s.Aggregate(0, (current, c) => current*62 + Base62Decode(c)); 
} 

は、暗号強度の高いランダムに生成する方法である：次のように5桁のベース-62への変換を行うことができます（916132832に等しい）0から62^5の数（たとえば、あなたの主キー）を考えます数字（あなたがSystem.Securityへの参照を追加する必要があります）：

private static readonly RNGCryptoServiceProvider crypto = 
    new RNGCryptoServiceProvider(); 

private static int NextRandom() { 
    var buf = new byte[4]; 
    crypto.GetBytes(buf); 
    return buf.Aggregate(0, (p, v) => (p << 8) + v) & 0x3FFFFFFF; 
} 

Answer 3

これは私が

（ダニエル・ベリテの答え以来更新）やってしまったものです：

を3210

class Program 
{ 

    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 char Base62Digit(uint d) 
    { 
     if (d < 26) 
     { 
      return (char)('a' + d); 
     } 
     else if (d < 52) 
     { 
      return (char)('A' + d - 26); 
     } 
     else if (d < 62) 
     { 
      return (char)('0' + d - 52); 
     } 
     else 
     { 
      throw new ArgumentException("d"); 
     } 
    } 
    private static string ToBase62(uint n) 
    { 
     var res = ""; 
     while (n != 0) 
     { 
      res = Base62Digit(n % 62) + res; 
      n /= 62; 
     } 
     return res; 
    } 
    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); 
    } 


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

    static void Main(string[] args) 
    { 

     Console.WriteLine("testing..."); 

      try 
      { 

       for (uint x = 1; x < 1000000; x += 1) 
       { 
        Console.Write(GenerateCode(x) + ","); 

       } 

      } 
      catch (Exception err) 
      { 
       Console.WriteLine("error: " + err.Message); 
      } 

     Console.WriteLine(""); 
     Console.WriteLine("Press 'Enter' to continue..."); 
     Console.Read(); 
    } 
}