ビットアレーの一般的な用途は何ですか？

Question

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

ありがとう。 Bit array Wikipediaの記事のApplicationsセクションに記載されているいくつかあります

Answer 1

：ので、そのコンパクトさの

は、ビット配列は、スペースや効率が重視される分野でのアプリケーションの数を持っています。最も一般的には、ブール値の単純なグループまたはブール値の順序付けられたシーケンスを表すために使用されます。

上記では、優先順位キューにビット配列が使用されていると述べました。ここでは、インデックスkのビットは、kがキュー内にある場合にのみ設定されます。このデータ構造は、例えば、Linuxカーネルによって使用され、ハードウェアでのファースト・ゼロ・ゼロ操作から強く恩恵を受けます。

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

ビットアレイの別のアプリケーションは、小さなエラーの代わりに小さなスペースに大きなセットを格納できる確率的なセットデータ構造であるBloomフィルタです。偽陽性または偽陰性のいずれかを受け入れるビット配列に基づいて確率的ハッシュテーブルを構築することも可能である。

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

ビット配列は、圧縮データのストリームを調べるときにも便利です。圧縮データのストリームを調べるには、ビット配列が便利です。この要素には、バイトの一部を占める要素やバイトアライメントされない要素が含まれます。例えば、単一の8ビット文字の圧縮されたハフマン符号化表現は、1から255ビットの長さの任意のものとすることができる。

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