現在、ビットベクトルのエンコードにランレングス エンコーディングを使用しており、現在の実行時間は 2log(i) です。ここで、 はランのサイズです。ログ(i)にダウンさせる別の方法はありますか?ありがとう。
1 に答える
ビット ベクトルをエンコードする最も効率的な方法は、ビット ソースの特定のプロパティを分離することです。完全にランダムな場合、実際に顕著なゲインはありません (実際には、ビットの完全にランダムなストリームはどのような方法でも圧縮できません)。
ビット ストリームでプロパティを見つけることができる場合は、ベクトル スペースのベースを定義するベクトルのコレクションを定義してみてください。そのような場合、結果は非常に効率的になります。
あなたのビットストリームについて、もう少し詳細が必要です。
(編集)
前のステートメントを理解するためのもう少しの詳細:「ビットの完全にランダムなストリームは、どのような方法でも圧縮できません」
「圧縮」が「変換/圧縮されたストリーム」と「ベクトルベース定義」と解凍プログラムを意味する場合、ビットの完全にランダムなベクトルを圧縮することはできません。しかし、ほとんどの場合、解凍プログラム (および多くの場合、ベクター ベースも) はクライアント ソフトウェアに組み込まれています。したがって、「圧縮ストリーム」のみが必要です。
それについての良い説明 (そして面白い話) は、Patrick Craig の 5000$ 圧縮チャレンジです。
より科学的な情報理論、特にエントロピーセクション
そして、最終話、全編。
しかし、解決策が何であれ、圧縮する不明なストリームの数が不明な場合は、何もできません。パターンを見つけなければなりません。