.png){kind=icon}
.png){kind=icon}
Return
Faster Wavelet Tree Queries
.png){kind=icon}
PRE
AI
DOI：10.1002/spe.70013.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a text, rank and select queries return the number of occurrences of a character up to a position (rank) or the position of a character with a given rank (select). These queries have applications in compression, computational geometry, and most notably pattern matching in the form of the backward search, which is the backbone of many compressed full-text indices. Currently, in practice, for text over non-binary alphabets, the wavelet tree is probably the most used data structure for rank and select queries.
Keywords:
algorithm optimization
cache efficiency
compressed data structures
rank/select queries
succinct data structures
wavelet trees
Journal
S
IF:
0
Papers:
31
Citations:
0