7

現在、ビットベクトルのエンコードにランレングス エンコーディングを使用しており、現在の実行時間は 2log(i) です。ここで、 はランのサイズです。ログ(i)にダウンさせる別の方法はありますか?ありがとう。

4

1 に答える 1

6

ビット ベクトルをエンコードする最も効率的な方法は、ビット ソースの特定のプロパティを分離することです。完全にランダムな場合、実際に顕著なゲインはありません (実際には、ビットの完全にランダムなストリームはどのような方法でも圧縮できません)。

ビット ストリームでプロパティを見つけることができる場合は、ベクトル スペースのベースを定義するベクトルのコレクションを定義してみてください。そのような場合、結果は非常に効率的になります。

あなたのビットストリームについて、もう少し詳細が必要です。


(編集)

前のステートメントを理解するためのもう少しの詳細:「ビットの完全にランダムなストリームは、どのような方法でも圧縮できません」

「圧縮」が「変換/圧縮されたストリーム」「ベクトルベース定義」解凍プログラムを意味する場合、ビットの完全にランダムなベクトルを圧縮することはできません。しかし、ほとんどの場合、解凍プログラム (および多くの場合、ベクター ベースも) はクライアント ソフトウェアに組み込まれています。したがって、「圧縮ストリーム」のみが必要です。

それについての良い説明 (そして面白い話) は、Patrick Craig の 5000$ 圧縮チャレンジです。

より科学的な情報理論、特にエントロピーセクション

そして、最終話、全編

しかし、解決策が何であれ、圧縮する不明なストリームの数が不明な場合は、何もできません。パターンを見つけなければなりません。

于 2012-10-13T22:31:54.247 に答える