performance - ビットベクトルをエンコードする効率的な方法は?

Question

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

Answer 1

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

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

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

---

（編集）

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

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

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

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

そして、最終話、全編。

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