Skip to content

rank andselect on WaveletTree #1

@somethingelseentirely

Description

@somethingelseentirely

Most wavelet tree implementations extend the definition for rank, select, and access over bit-sequences to the wavelet tree itself.

An example of the extension from the following paper.

  • The WaveletTree::lookupoperation seems to be equivalent to a select with some additional caching done to accelerate subsequent queries.
  • The WaveletTree::decode_one operation seems to be equivalent to an access operation.
  • rank doesn't seem to have a corresponding method.

Since the implementation of this project appears to be an independent invention of the wavelet matrix it probably makes sense to just implement the rank from the paper. (Doing a comparison of the other operations is probably also interesting.)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions