Dynamic rank/select structures with applications to run-length encoded texts
- Lee, Sunho
- Park, Kunsoo
DOIAbstract
AbstractGiven an n-length text over a σ-size alphabet, we propose a framework for dynamic rank/select structures on the text and some of its applications. For a small alphabet with σ≤logn, we propose a two-level structure consisting of a counting scheme and a storing scheme that supports O(logn) worst-case time rank/select operations and O(logn) amortized time insert/delete operations. For a large alphabet with logn<σ≤n, we extend it to obtain O((1+logσloglogn)logn) worst-case time rank/select and O((1+logσloglogn)logn) amortized time insert/delete. Our structure provides a simple representation of an index for a collection of texts. In addition, we present rank/select structures on run-length encoding (RLE) of a text. For the n′-length RLE...
Add to ORKG