-
AFE
-
Lehre
-
Algorithmische Grundlagen
Theses
of elements, type of element). Looking at the previous example, RLE( B ) = (1,0), (1,1), (3,0), (2,1), (1,0), (1,1), (1,0), (4,1). Combining compressed and dynamic bitvectors supporting rank/select operations [...] example, if the reference is R = abab , then the text T=abbababababa can be compressed to T'=(1,2)(2,3)(1,4)(1,3) , where each tuple (i, m) consists of the position i in the reference R at which a pattern [...] specific bit. Formally, select b (k) = min{j : 1 <= j <= |B|, rank b (j) = k} . For example, given a bitvector B = 01000110101111, we have that query rank 1 (5) = 1 and select 0 (6) = 10 . There exist numerous …
