data-structures - ビットアレイの一般的な使用法は何ですか？

Question

初心者向けマニュアルのビットアレイを使用して例を示しました。それらが何に使用できるのか、そしてそれらのいくつかの一般的なデータ構造が何であるのかを知りたいです（「配列」はかなり緩い用語であると仮定します）。

ありがとう。

Answer 1

ビット配列ウィキペディアの記事の「アプリケーション」セクションにいくつかリストされています。

ビット配列はコンパクトであるため、スペースや効率が重要視される分野で多くの用途があります。最も一般的には、ブールフラグの単純なグループまたはブール値の順序付けられたシーケンスを表すために使用されます。

ビット配列は優先度付きキューに使用されることを前述しました。ここで、インデックスkのビットは、kがキューにある場合にのみ設定されます。このデータ構造は、たとえばLinuxカーネルによって使用され、ハードウェアでの最初のゼロの検索操作から大きな恩恵を受けます。

ビット配列は、メモリページ、iノード、ディスクセクターなどの割り当てに使用できます。このような場合、ビットマップという用語を使用できます。ただし、この用語は、ピクセルごとに複数のビットを使用する可能性があるラスターイメージを指すために頻繁に使用されます。

ビット配列のもう1つのアプリケーションは、ブルームフィルターです。これは、小さなエラーの可能性と引き換えに、小さなスペースに大きなセットを格納できる確率的なセットデータ構造です。誤検知または誤検知のいずれかを受け入れるビット配列に基づいて確率的ハッシュテーブルを作成することもできます。

ビット配列とその操作は、可能な限り最小限のスペースを使用する簡潔データ構造を構築するためにも重要です。このコンテキストでは、n番目の1ビットを見つける、または特定の位置までの1ビットの数をカウントするなどの操作が重要になります。

ビット配列は、圧縮データのストリームを調べるための便利な抽象化でもあります。圧縮データのストリームには、バイトの一部を占める要素やバイト整列されていない要素が含まれていることがよくあります。たとえば、単一の8ビット文字の圧縮されたハフマンコーディング表現は、1〜255ビットの長さにすることができます。

情報検索では、ビット配列は非常に頻繁な用語の投稿リストの適切な表現です。厳密に増加する整数のリスト内の隣接する値間のギャップを計算し、それらを単一符号化を使用してエンコードすると、nがリスト内にある場合に限り、結果はn番目の位置に1ビットのビット配列になります。nのギャップの暗黙の確率は1/2nです。これは、パラメータMが1であるゴロムコーディングの特殊なケースでもあります。このパラメーターは通常、-log（2-p）/ log（1-p）≤1の場合にのみ選択されます。または、この用語は、ドキュメントの少なくとも38％で発生します。