4

URLで使用するために短くしたい数字の文字列があります。この文字列は常に数字のみで構成されます。例:9587661771112

理論的には、数値文字列を英数字(0-9a-zA-Z)文字列に暗号化すると、常に短い結果が返されるはずです。これが私が望むものです。

次のことを行うアルゴリズムを作成しました。

暗号化(string1 =数値入力文字列、string2 =英数字戻り文字列)

  • string1から次の2文字を取得し、それらを数値に変換します。たとえば、上記の例では95です。
  • 数値が52(azとAZの合計の長さ)未満であるかどうかを確認します
    • その場合、string2に( "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")[Number]を追加し、2文字前にジャンプします
    • それ以外の場合は、string2に( "0123456789)[数値の最初の桁)を追加して、1文字前にジャンプします

次のステップでは、番号は58などになります。

私が得ることができた最短の結果を微調整すると、次のようになりました:9587661771112> j9UQpjva

私の問題は、この手法では結果が劇的に変化する可能性があることです。また、これは私の問題に対するクリーンな解決策ではないと感じています。

したがって、数字の文字列を大文字、小文字、数字の短い文字列に変換する暗号化アルゴリズムが必要です。復号化可能で、多かれ少なかれ一貫した結果が得られる必要があります。

これを達成する方法はありますか?


解決:

string Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

string Base10To62(long N)
{
    string R = "";
    while (N != 0)
    {
        R += Chars[(int)(N % 62)];
        N /= 62;
    }
    return R;
}

long Base62To10(string N)
{
    long R = 0;
    int L = N.Length;
    for (int i = 0; i < L; i++)
    {
        R += Chars.IndexOf(N[i]) * (long)Math.Pow(62, i);
    }
    return R;
}

魅力のように機能します:)

4

3 に答える 3

2

解決:

string Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    private static string Base10To62(string S) 
    {
        string R = "";
        var N = long.Parse(S);
        do { R += Chars[(int)(N % 0x3E)]; } while ((N /= 0x3E) != 0);
        return R;
    }

    private static string Base62To10(string S) 
    {
        long R = 0;
        int L = S.Length;
        for (int i = 0; i < L; i++) R += Chars.IndexOf(S[i]) * (long)(System.Math.Pow(0x3E, i));
        return R.ToString();
    }
于 2012-08-02T09:36:49.163 に答える
1

セットにさらに 2 文字を追加して 64 文字にすることができる場合は、ここで説明できるシンプルで高速なアルゴリズムがあります。

次のように、数字を 3 ビットまたは 4 ビットのコードにエンコードします。

0: 000
1: 001
2: 010
3: 011
4: 100
5: 101
6: 1100
7: 1101
8: 1110
9: 1111

これはプレフィックス コードです。つまり、最初の 3 ビットを見て、4 番目のビットを使用する必要があるかどうかを判断できます。整数としての最初の 3 ビットが 5 より大きい場合は、別のビットを取得します。したがって、デコードは次のようになります。

get three bits as n
if n < 6
     the result is n + '0'
else
     n = (n << 1) + one more bit
     the result is n - 6 + '0'

ビットは、64 個の許可された文字の 1 つに一度に 6 つずつ単純に格納されます。

最後の文字で 4 ビットまたは 5 ビットを未使用のままにしておくとあいまいになるため、事前に桁数がわからない場合、これには問題があります。その場合、コードは次のように簡単に変更できます。

0: 000
1: 001
2: 010
3: 011
4: 100
5: 1010
6: 1011
7: 1100
8: 1101
9: 1110
eom: 1111

これにはさらに数ビットかかりますが、明確なメッセージ終了マーカーを提供します。

最初の例では、1 文字あたり平均 1.76 桁を格納します。2 番目の例では、1 文字あたり 1.71 桁であり、一度にエンコードする桁数に応じて eom マーカーの量が少なくなります。

本当に62文字しか使えないなら、もう少し考えないと。

アップデート:

RFC 1738をざっと見てみると、URL にはさらに多くの文字を使用できることが示されています。

lowalpha       = "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"
hialpha        = "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"
alpha          = lowalpha | hialpha
digit          = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" |
                 "8" | "9"
safe           = "$" | "-" | "_" | "." | "+"
extra          = "!" | "*" | "'" | "(" | ")" | ","
unreserved     = alpha | digit | safe | extra

たとえば、セットに $ と _ を追加すると、64 になります。

于 2012-08-01T21:16:26.887 に答える
1

楽しみのために、62から10のLinqバージョン:

long Base62To10(string N)
{
    return N.Select((t, i) => Chars.IndexOf(t)*(long) Math.Pow(62, i)).Sum();
}
于 2012-08-01T10:29:48.847 に答える