7

Base64で短い表現を生成したいコンテンツのWebフォームがあります。このフォームには、特に264個のバイナリ値のリストが含まれています。その大部分はいつでも0になります。（地理マップ上の地域を表します）。Base64でも、この264ビットの数値は長くて威圧的な文字列を生成します。可能な限り効率的にランレングスエンコーディングを実装したいと思います。これを手伝ってくれませんか。バイナリRLEをグーグルで検索しましたが、何の役にも立ちません。

私がこれまでに試したことは、10進数のカウントと0と1の間の変化を示す区切り文字として「A」を使用してバイナリ文字列でRLEを実行し、結果をbase11からbase64に変換することです。例：

00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100

になります

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A

これは次のようになります

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o

または、ベース62では、

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK

それは良いことですが、それでも私が何か間違ったことをしているのかどうか疑問に思うしかありません-数字「A」を区切り文字として使用するのがこれを行うための最良の方法ですか？

そして別の更新：

@comingstormのおかげで、圧縮された文字列をもう少し短くしました。

ILHHASCAASBYwwccDASYgAEgWDI=

コメントで述べたように、実際の使用例では、通常、文字列がさらに短くなります。

4

3 に答える 3

9

ビットをコーディングしているので、バイトベースのRLEではなくビットベースのRLEを使用することをお勧めします。このコンテキストでは、ランレングスを効率的にエンコードするために、エリアスガンマコーディング（またはそのバリアント）を検討する必要があります。

エンコーディング形式の妥当な最初の概算は次のとおりです。

  • 最初のビット=非圧縮文字列の最初のビットと同じ（初期極性を設定するため）
  • 残りのビット：連続するビット実行のエリアスコード化された長さ（1と0を交互に）

非圧縮文字列のビット数がわかっているので、終了コードは必要ありません。必要なバイナリパディングを任意のビットとして追加できます。

ランレングスの「圧縮」によってビット文字列が拡張される可能性があることに注意してください。これが気になる場合は、別の初期ビットを追加して、データが圧縮形式か非圧縮形式かを示し、圧縮オーバーヘッドを1ビットに制限できます。

于 2011-09-29T22:13:19.233 に答える
1

264ビット、これは33バイトで、base64では44バイトです。この（非常に少量の）情報はほとんど圧縮できないと思います。スパース表現nulvingeは、ゼロ以外の要素とその値（0/1しかないため）、つまり、ゼロ以外のビットのインデックスのみを格納します。ただし、可能なビット数は264であるため、インデックスには9ビットが必要です。つまり、ゼロ以外のエントリが29を超える場合は、元のビットよりも多くのビットが必要になります。

おそらくあなたの質問は間違って定式化されていますが、264ビットがどのように恐ろしいbase64文字列につながるのかわかりません（どのように生成しますか-おそらく264ビットではなく264のASCII文字（値0と1）を変換します-それは説明しますあなたの長い結果文字列？）。

于 2011-09-29T14:38:55.847 に答える
0

私が思うに、もっと欲しいのはスパース行列です：http: //en.wikipedia.org/wiki/Sparse_matrix

于 2011-09-29T14:26:28.197 に答える