Repository navigation
Support rank and select operations? #3
Description
Activity
This should be doable based on my reading of this description of the operations.
I'll explore whether an auxiliary data structure will need to be added to the
BitVectortype and then maintained after each mutable operation, or if the auxiliary structure can be created as needed whenrankorselectare called on theBitVector.I won't have a lot of free time to implement this for a while. If you're interested in implementing a pull request, it would be welcomed.
Reacted by Vaibhav SagarI think the current state of the art is http://www.cs.cmu.edu/~./dongz/papers/poppy.pdf. There's an implementation of this at https://github.com/Gabriel439/Haskell-Succinct-Vector-Library.
I apologize for the delay @vaibhavsagar , I've had other priorities the last few months. I have implemented the
rank&selectfunctions on therank-selectbranch. Please take a look at the new functionality.The functions currently have the following type signatures:
rank :: BitVector -> Word -> Word select :: BitVector -> Word -> Maybe WordBoth employ "broadword programming" for their implementation and do not allocate any additional memory structures within the
BitVectordata type. The advantage of this technique is that there is no additional memory overhead for users that do not require theBitVectorto be a succinct data structure. The downside is thatrankandselectare not as efficient as possible (O(1) time). It's important for me and our use-case at AMNH that theBitVectortype not allocate any more memory than required for our functionality.I did consider the following functions instead:
succinctDictionary :: BitVector -> SuccinctDictionary rank :: Maybe SuccinctDictionary -> BitVector -> Word -> Word select :: Maybe SuccinctDictionary -> BitVector -> Word -> Maybe WordWith this interface, a
Nothing :: Maybe SuccinctDictionaryvalue indicates to use the "broadword programming" technique for efficiency reason. AJust v :: Maybe SuccinctDictionaryvalue indicates using the pre-computedSuccinctDictionaryfor theBitVectorbecause either theBitVectoris so long it requires the dictionary for efficiency, or enoughrank/selectoperations will be performed on thisBitVectorthat pre-computing the dictionary is worth the time and space investment.There are advantages of this "interface." Notably, it allows for the creation of a
SuccinctDictionaryfor users who require theBitVectortype to be a succinct data structure in an "opt-in" manner. Additionally, this "interface" would allow for the implementation ofrank&selectthat are truly O(1). The downside is that theSuccinctDictionaryfor a givenBitVectorwill have to be manually tracked by the user. A second "downside" is that the algorithms described for constructing the succinct dictionaries are quite finicky, so it would require more time to implement than what I have done currently with the "broadword programming" technique. Finally literature has references that for small succinct data structures, "broadword programming" tends to outperform the use of succinct dictionaries until the size of theBitVectorscales very large.I'm open to merging and uploading what I have now to
hackage. However, if you're interested in creating a pull request for an implementation along the lines of the second interface I just described, I'm open to the contribution.Let me know what you think about the current implementation and the possible pull request.
This looks great, thank you for implementing it! I'm not sure I'll have time to contribute a pull request using succinct dictionaries anytime soon, unfortunately 😦.
I'm not sure I'll have time to contribute a pull request using succinct dictionaries anytime soon, unfortunately frowning.
@vaibhavsagar you and me both!
I'll merge this branch into
master, tag a new release, and upload to hackage tomorrow.Thank you!
It would be wonderful to use these bitvectors as rank/select dictionaries.