Reputation: 56
Looking through literature on advanced data structures and some implementations of balanced parenthesis representations I have stumbled upon proofs making use of rank and select operations on bit vectors, but not for single characters but for the sequences of constant size (eg. '10').
The authors does not describe how such data structure could be implemented, besides stating the space complexity for indexes O((n * log_2(log_2(n)))/ log_2(n)) which is equal to the implementation of standard rank and select with constant time access on bit vectors.
Can somebody explain or link me the publication where could I find the explanation for that?
I have browsed through suggested literature on the topic of succinct representation of BP and static trees, went through over 20 papers and found no answer.
I am aware of the implementation for standard rank and select, but still I cannot understand how to adjust it for the constant size pattern. Eventually I have drifted to pattern search on binary alphabets (eg. Knuth–Morris–Pratt), but it does not solve my problem.
Upvotes: 0
Views: 33