2

他の情報を詰め込むために、20 文字の長さの base62 (0-9a-zA-Z) でエンコードされた文字列を 15 ～ 16 文字の文字列に圧縮する必要があります。注意が必要なのは、圧縮された出力も base62 にする必要があることです。エンコードされます。これはできますか？どんな提案でも大歓迎です。

ありがとう！

4

1 に答える 1

3

ピジョンホールの原理を参照してください。100 匹のハトを 10 個の穴に入れようとすると、いくつかの穴には複数のハトが入ります。同様に、あなたの問題では、2 つの文字列が同じ文字列に圧縮される必要があります。このような場合、圧縮された文字列をどの文字列に解凍すればよいかわかりません。

いいえ、可能なすべての入力に対して同じエンコーディングで 20 文字を 16 文字 (または 20 ～ 19 文字) に可逆圧縮することはできません。

大文字のみが最初の文字であり、最後の 3 文字は数字が表示される場所であるなど、入力にいくつかの定義的な特性がある場合は、より圧縮可能になり、可能になる可能性があります。

このような特性がある場合 (または、十分なスペースがある別のエンコーディングに変換する場合)、任意のエンコーディングの文字列を一意の数値に簡単に変換してから、この数値を別のエンコーディングの文字列に変換できます。これを行う方法は次のとおりです。

  • 文字位置ごとに、その位置で使用できる各文字に 0 から始まる番号を割り当てます。

    したがって、最初の位置で "A" から "Z" および "a" から "z" を使用できる場合、0 から 25 を "A" から "Z" に、26 から 51 を "a" から "z" に割り当てることができます。 . たとえば、「B」は 1 になります。

  • 文字列を反復処理し、合計に現在の位置の許容値の数を掛けてから、その位置の文字に割り当てられた数を合計に加算します。

別のエンコーディングを取得するには、繰り返します。

  • 合計を現在の位置の許容値の数で割った結果 (切り捨て) を合計に設定します。
  • 上記除算の余りに対応する文字に現在位置を設定します。

上記のいずれの場合でも、左から右に行くか、右から左に行くかは問題ではありません。

また、各エンコーディングの最大可能値を計算することにより (各文字の最大値を取得することにより)、そのような変換が可能かどうかを簡単に判断できます。ターゲットの最大可能値が小さい場合、変換は不可能です。

上記は、特定の位置に固定値がある場合のみであることに注意してください。ただし、これをある程度拡張して、他のエンコーディング (文字列に最大で 1 つの数値を含めるなど) で機能するようにすることもできますが、これはもう少し複雑になります。

例：

入力形式: 1 つの大文字 (AZ)、次に 2 つの数字 (0-9)
出力形式: 1 つの小文字 (az)、次に 2 つの大文字/小文字 (AZ または az)
入力: "Z35"
数値: 10*( 10*(26*0 + 25) + 3) + 5 = 2535
説明:「Z」から始めます。合計は 0 です。これに大文字の数 (26) を掛けてから、 「Z」（25）。次に、「3」に進みます。ここで、この合計に桁数 (10) を掛けて、「3」の値 (3) を加算します。
出力計算:
2535 / 26 = 97
2535 % 26 = 13 なので、1 文字目 = "n" (13+1 = アルファベットの 14 文字目)
97 / 52 = 1
97 % 52 = 45 なので、2 文字目 = "t" (45-26+1 = アルファベットの 20 文字目)
1 % 52 = 1 なので、3 文字目 = "B"
出力: "ntB"

入力形式の可能な最大値: 10*(10*(26*0 + 25) + 9) + 9 = 2599
出力形式の可能な最大値: 52*(52*(26*0 + 25) + 51) + 51 = 70303
変換は可能ですか? はい、70303 >= 2599 なので。

于 2013-07-16T13:27:53.037 に答える