1

私のプロジェクトは文字列sを受け取り、すべて小文字のバージョンs.toLowerCase()をロスレス エンコーダーに渡します。小文字の文字列をうまくエンコード/デコードできますが、これは明らかに実用的ではないため、元の文字列の大文字と小文字を何らかの方法で保持できるようにする必要があります。

のすべての大文字の位置を表すCharacter.isUpperCase()整数の配列を取得するために使用することを考えていました。次に、この配列を使用して、エンコードされた文字列のすべての場所に a を配置します。文字列をデコードすると、a の前のすべての文字が大文字であることがわかります。(ちなみに、このエンコーダーはエンコード時に生成されません)。UpperCaseLetters[]s^UpperCaseLettes[i] + 1^^

しかし、この方法は私にはずさんなようです。大文字と小文字を区別するためにビット文字列を使用することも考えていましたが、アプリケーションの全体的な目標は圧縮であるため、あまり効率的ではありません。

文字列の大文字化マスクを取得して適用する簡単な方法はありますか? ある場合、どのくらいの「ストレージ」が必要ですか?

4

1 に答える 1

1

オプション:

自動大文字化:

大文字化には一般的なアルゴリズムを使用し、以下の手法のいずれかを使用して、生成された大文字と実際の大文字とで異なる文字のみを記録します。再生成するには、アルゴリズムをもう一度実行して、記録されたすべての文字の大文字と小文字を反転させます。大文字があるべき場所 (文頭など) があると仮定すると、これによりアルゴリズムがわずかに遅くなり (n の小さな定数係数だけであり、適切な圧縮は一般にそれよりもはるかに遅くなります)、常にストレージの量が減少します。少数が必要とするスペース。

資本位置のビットマップ:

これについてはすでに説明しましたが、特に効率的ではありません。

大文字に識別文字を付けます:

postfix について説明したことを除いて、既に説明しましたが、一般的には prefix の方が優れており、より一般的な解決策として、^with をエスケープすることもできます^^。悪くないアイデア。圧縮によっては、データセットに既に表示されている文字を代わりに使用することをお勧めします。最も一般的な文字または最も一般的でない文字のいずれか、または圧縮アルゴリズムを調べて、使用する理想的な文字を決定するためにかなりの処理を行う必要がある場合があります。

先頭からの首都の距離を任意の形式で保存します。

次の首都 (下記) までの距離に対して利点はありません。

次の大文字までの距離 - 非ビット文字列表現:

一般に、ビット文字列を使用するよりも効率的ではありません。

ビット文字列 = 次の大文字までの距離:

長さのシーケンスがあり、それぞれが大文字間の距離を順番に示しています。したがって、距離がある場合、0,3,1,0,5大文字化は次のようになります: AbcdEfGHijklmNo(0 文字を最初に、3 文字を 2 番目に、1 文字を 3 番目にスキップするなど)。これを保存するために利用できるオプションがいくつかあります。

  • 固定長:可能な限り最長の距離である必要があるため、お勧めできません。明らかな代替手段は、次の長さへのある種のオーバーフローを持たせることですが、それでもスペースを使いすぎます。

  • 固定長、異なる設定:例で最もよく説明されています。最初の 4 ビットは長さ00を示し、距離を示すために 2 ビットが続くことを01意味し、4 ビットを10意味し、8 ビットを11意味し、16ビットを意味します。 -110は 16 ビットを1110意味し、32 ビットを11110意味し、64 ビットを意味します (これは、IPv4 アドレスのクラスを決定することに似ているように聞こえるかもしれません)。したがって、0001010100に分割されます00- 01、01-0100したがって、距離は 1、4 です。長さは 2 のべき乗で増加する必要がないことに注意してください。16 ビット = 65535 文字は多く、2 ビット = 3 は非常に少ないため、おそらく 4、6、 8、(16?)、(32?)、??? (行にいくつかの大文字がない限り、おそらく 2 ビットも必要です)。

  • エスケープ シーケンスを使用した可変長:エスケープ シーケンスが00であるとします。 を含まないすべての文字列を使用したい00ので、ビット値テーブルは次のようになります。

    Bits Value
1    1
10   2
11   3
101  4 // skipped 100
110  5
111  6
1010 7 // skipped 1000 and 1001

    10100101010010101000101000010101、10101、101010、101、 0 、に分割され10ます。...1001..just は、左 1 で終了する分割と右 1 で開始する分割を...10001...引き起こし、最初の 0 で終了する分割と右 1 で開始する分割を引き起こし、...100001...その間の値が 0 の距離を示すことに注意してください。擬似コードは次のようなものです。

    if (current value == 1 && zeroCount < 2)
  add to current split
  zeroCount = 0
else if (current value == 1) // after 00...
  if (zeroCount % 2 == 1) { add zero to current split; zeroCount--; }
  record current split, clear current split
  while (zeroCount > 2) { record 0-distance split; zeroCount -= 2; }
else zeroCount++

    これは短い距離には良い解決策のように見えますが、距離が大きくなると、あまりにも多くの値をスキップし始め、長さが急速に増加すると思われます。

理想的な解決策はありません。データに大きく依存します。典型的なデータセットに最適なものを確認するには、先頭に大文字を付けたり、ビット文字列の距離のさまざまなオプションを試したりする必要があります。

于 2013-01-03T20:15:35.053 に答える