Struct sdsl::select_supports::SelectSupportMcl
source · [−]pub struct SelectSupportMcl<'a, BitPattern: BitPattern> { /* private fields */ }Expand description
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 pattern0,1,10,01supported 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