Struct SelectSupportMcl

pub struct SelectSupportMcl<'a, BitPattern: BitPattern> { /* private fields */ }

A class supporting constant time select queries.

Space usage

The space usage of the data structure depends on the number of $m$ of ones in the original bitvector $b$. We store the position of every 4096-th set bit (called L1-sampled bits) of $b$. This takes in the worst case $ \frac{m}{4096} \log{n} \leq \frac{n}{64} $ bits.

Next, (1) if the distance of two adjacent L1-sampled bits $b[i]$ and $b[j]$ is greater or equal than $\log^4 n$, then we store each of the 4096 positions of the set $b$ in [i..j-1] with $\log{n}$ bits. This results in at most $ \frac{4096\cdot \log n}{\log^4 n}=\frac{4096}{\log^3 n}$ bits per bit. For a bitvector of 4GB, i.e. $ \log n = 35 $ we get about 0.01 bits per bit. If the $j-i+1 < \log^4 n$ then (2) we store the relative position of every $64$th set bit (called L2-sampled bits) in b[i..j-1] in at most $4\log\log n$ bits per L2-sampled bits. An pessimistic upper bound for the space would be $ \frac{4\log\log n}{64} \leq \frac{24}{64} = 0.375 $ bit per bit (since $\log\log n\leq 6$. It is very pessimistic, since we store the relative position in $\log\log(j-i+1)\leq \log\log n$ bits.

Arguments

• BitPattern - Bit pattern 0,1,10,01 supported by select query.

Example

let bv = sdsl::bit_vector! {0, 1, 0, 1, 0, 0, 0};
let ss = sdsl::select_supports::SelectSupportMcl::<sdsl::BitPatterns::P1>::new(&bv)?;
let result = ss.select(2);
let expected = 3;
assert_eq!(result, expected);

For further examples see here.

References

• David Clark: PhD Thesis: Compact Pat Trees University of Waterloo, 1996 (Section 2.2.2). http://www.nlc-bnc.ca/obj/s4/f2/dsk3/ftp04/nq21335.pdf

Implementations

impl<'a, BitPattern: BitPattern> SelectSupportMcl<'a, BitPattern>

pub fn new(bit_vector: &'a BitVector) -> Result<Self>

Construct a new select support structure.

Arguments

• bit_vector - Bit vector.

pub fn from_file(path: &PathBuf) -> Result<Self>

Load from file.

Arguments

• path - File path.

pub fn select(&self, index: usize) -> usize

Returns the position of the i-th bit pattern instance in the bit vector.

Arguments

• index - An index within the range of the supported bit vector.

Trait Implementations

impl<'a, BitPattern: BitPattern> Drop for SelectSupportMcl<'a, BitPattern>

fn drop(&mut self)

Executes the destructor for this type.