7

可能な文字の限られたセットを含む、正確に 53 文字の長さの文字列があります。

[A-Za-z0-9\.\-~_+]{53}

情報を失うことなく、同じ文字セットを使用して、これを長さ 50 に減らす必要があります。

ほとんどの文字列を 50 の長さまで圧縮できるはずですが、考えられるすべての長さの 53 の文字列を圧縮することは可能ですか? 最悪の場合、可能なセットから 14 文字が使用されないことがわかっています。この情報をまったく使用できますか?

読んでくれてありがとう。

4

5 に答える 5

11

あなたが述べたように、出力文字列が入力文字列と同じ文字セットを使用する必要があり、入力文字列の要件について特別なことを何も知らない場合、いいえ、すべての可能な53を圧縮することはできません・50文字までの文字列。これは、ピジョンホールの原理を単純に応用したものです。

  • 入力文字列は、base 67 の 53 桁の数値、つまり 0 ～ 67 53 - 1 ≅ 6*10 96の整数として表すことができます。
  • これらの数値を 0 から 67 50 - 1 ≅ 2*10 91の整数にマップします。
  • したがって、鳩の巣の原理により、67 3 = 300,763 の異なる入力がそれぞれの可能な出力にマッピングされることが保証されます。にマップします。

これを機能させるには、要件を変更する必要があります。より大きな文字セットを使用して出力をエンコードできます (入力の 67 ではなく、それぞれに 87 の可能な値がある場合は、50 文字に減らすことができます)。または、入力の冗長性を特定することもできます。おそらく、最初の文字は「3」または「5」のみであり、19 番目と 20 番目は州の略語であり、62 の異なる可能な値しか持てません。

これらのいずれかを実行できない場合は、ハフマン コーディングなどの圧縮アルゴリズムを使用し、一部の文字列は圧縮可能 (および短くなる) で、他の文字列は圧縮できない (および長くなる)という事実を受け入れる必要があります。 .

于 2012-11-20T21:41:39.060 に答える
5

非常に簡単に証明できる最も一般的なケースでは、あなたが求めることは不可能です。

同じセット内の任意の53文字の文字列を50文字にエンコードできたとします。次に、エンコードされた文字列に3つのランダムな文字を追加します。次に、別の任意の53文字の文字列があります。それをどのように圧縮しますか？

したがって、必要なものが可能なデータに対して機能することを保証することはできません。ただし、すべての実際のデータのエントロピーが十分に低いため、機能するスキームを考案できる可能性があります。

その場合、ハフマンコーディングの変形を実行することをお勧めします。これは、基本的に、最も一般的に使用される文字に最短のエンコーディングを使用して、セット内の文字に可変ビット長のエンコーディングを割り当てます。すべてのデータを分析して、一連のエンコーディングを考え出すことができます。ハフマン符号化後、文字列は（できれば短い）ビットストリームになり、1文字あたり6ビットで文字セットにエンコードします。すべての実際のデータに対して十分に短い場合があります。

Smaz（別の回答で参照されている）のようなライブラリベースのエンコーディングも機能する可能性があります。繰り返しますが、すべての可能なデータに対して機能することを保証することは不可能です。

于 2012-11-20T21:16:55.473 に答える
5

1 バイト (文字) は 256 の値 (0-255) をエンコードできますが、有効な文字のセットは 67 の値しか使用せず、7 ビットで表すことができます (悲しいかな、6 ビットでは 64 しか取得できません)。バイトのビット。

その場合、上位ビットを破棄して 7 ビットのみを格納し、次の文字の最初のビットを最初の文字の「予備」スペースに入れることができます。これは、保存するために 47 バイトのスペースしか必要としません。(53 x 7 = 371 ビット、371 / 8 = 46.4 == 47)

これは実際には圧縮とは見なされませんが、エンコーディングの変更と見なされます。

たとえば、「ABC」は 0x41 0x42 0x43 です。

     0x41        0x42        0x43  // hex values
0100 0001   0100 0010   0100 0011  // binary
 100 0001    100 0010    100 0011  // drop high bit
// run it all together
100000110000101000011
// split as 8 bits (and pad to 8)
10000011   00001010   00011[000]
    0x83       0x0A        0x18

例として、これらの 3 文字はスペースを節約しませんが、53 文字は常に47 文字として表示されます。

ただし、重要な場合は、出力が元の文字セットに含まれないことに注意してください。

プロセスは次のようになります。

original-text --> encode --> store output-text (in database?)
retrieve --> decode --> original-text restored
于 2012-11-20T21:34:09.747 に答える
3

私の記憶が正しければ、ハフマン符号化はデータを保存するための最もコンパクトな方法になるでしょう。アルゴリズムをすばやく作成するために使用してから時間がかかりすぎましたが、一般的な考え方はここで説明されていますが、正しく覚えていれば、次のようになります。

  1. 使用されている各文字のカウントを取得します
  2. それらが発生した頻度に基づいて優先順位を付けます
  3. 優先順位に基づいてツリーを構築する
  4. ツリーをトラバースして、各文字の圧縮ビット表現を取得します（ルートから開始、左= 0、右= 1）
  5. 各文字をツリーのビットに置き換えます
于 2012-11-20T21:01:57.790 に答える
2

Smazは、非常に短い文字列を圧縮するのに適した単純な圧縮ライブラリです。

于 2012-11-20T20:59:20.477 に答える