Dynamic RLSLP Index

This repository provides a C++ implementation of DynamicRLSLPIndex, a dynamic compressed self-index based on run-length encoded straight-line programs (RLSLPs). It supports pattern matching queries and text updates (insertion and deletion) directly in compressed space.

It implements the index described in the following paper:

Takaaki Nishimoto and Yasuo Tabei. Dynamic Grammar-Compressed Self-Index in δ-Optimal Space. To appear in the European Symposium on Algorithms (ESA 2026). Full version: arXiv:2604.24080

DynamicRLSLPIndex provides two index modes:

Dynamic RR index (default) — the index proposed in the paper above, with expected δ-optimal asymptotic space bounds for the core data structure.
Dynamic SE index — an earlier index based on signature encoding (Nishimoto et al., 2020), provided mainly as a baseline for comparison.

Note

Status: This is a research implementation accompanying the paper above. The API and the on-disk index format may still change before a first tagged release.

Quick Start

# 1. Clone the repository and initialize submodules
git clone https://github.com/TNishimoto/dynamic-rlslp-index.git
cd dynamic-rlslp-index
git submodule update --init

# 2. Build the project
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release

# 3. Try an example
cat examples/short.txt
build/build -i examples/short.txt -o short.rr.idx -m dynamic_rr_index
cat examples/query.tsv
build/query -i short.rr.idx -q examples/query.tsv -w query.log -o update.idx
cat query.log
cat short.1.txt
cat short.2.txt
cat short.3.txt

Overview

DynamicRLSLPIndex is a dynamic compressed self-index for a string $T[0..n-1]$. It represents $T$ using a run-length encoded straight-line program (RLSLP) and supports both pattern matching queries and text updates directly in compressed space.

DynamicRLSLPIndex supports the following operations.

Operation	Description
`access_substring(i, d)`	Returns $T[i..i+d-1]$.
`lce(i, j)`	Returns the length of the longest common prefix of the two suffixes $T[i..n-1]$ and $T[j..n-1]$.
`decompress(ofs)`	Writes $T$ to the given output file stream `ofs`.
`locate(P)`	Returns all occurrence positions of a given string $P[0..m-1]$ in $T$.
`insert_string(i, P)`	Inserts the string $P[0..m'-1]$ at position $i$.
`delete_string(i, m')`	Deletes $T[i..i+m'-1]$ from $T$.

When constructing an instance of DynamicRLSLPIndex, you can choose either dynamic_rr_index (default) or dynamic_se_index as the index mode.
In either mode, the memory usage of DynamicRLSLPIndex is $O(M \log n)$ bits, where $M$ is the number of explicit nonterminals in the RLSLP.

Note

An explicit nonterminal is a nonterminal corresponding to a leaf or branching node in the derivation tree of the RLSLP.

The details of each mode are as follows.

Dynamic RR index (default)

If dynamic_rr_index is chosen, DynamicRLSLPIndex works as an implementation of the dynamic RR-index proposed in the ESA 2026 paper.
In this case, the expected value of $M$ is bounded by $O(\delta \log ((n \log \sigma)/(\delta \log n)))$.

Note

$\delta$: Substring complexity.
$\sigma$: Alphabet size.

The following table summarizes time complexities for the queries supported by the dynamic RR-index.

Operation	Time complexity
`access_substring(i, d)`	$O(d + \log n)$
`lce(i, j)`	$O(\log n)$
`decompress(ofs)`	$O(n)$
`locate(P)`	Expected $O(m + \log^{3} n + occ \log n / \log \log n)$
`insert_string(i, P)`	Expected amortized $O(m' \log^{2} n + \log^{3} n)$
`delete_string(i, m')`	Expected amortized $O(m' \log^{2} n + \log^{3} n)$

Dynamic SE index (baseline)

If dynamic_se_index is chosen, DynamicRLSLPIndex works as an implementation of the dynamic SE-index proposed in an earlier paper.
This mode is provided mainly as a baseline for experimental comparison with the dynamic RR-index.
In this case, $M$ is bounded by $O(z \log n \log^{*} n)$.

Note

$z$: The number of factors in the LZ77 factorization of $T$.
The original paper proposed the dynamic SE-index using deterministic data structures, but this repository implements the method using randomized data structures.

The following table summarizes time complexities for the queries supported by the dynamic SE-index.

Operation	Time complexity
`access_substring(i, d)`	$O(d + \log n)$
`lce(i, j)`	$O(\log n \log^{*} n)$
`decompress(ofs)`	$O(n)$
`locate(P)`	$O(m + \log^{3} n (\log^{*} n)^{2} + occ \log n)$
`insert_string(i, P)`	Expected amortized $O(m' \log^{2} n (\log^{＊} n)^{2} + \log^{3} n (\log^{＊} n)^{2})$
`delete_string(i, m')`	Expected amortized $O(m' \log^{2} n (\log^{＊} n)^{2} + \log^{3} n (\log^{＊} n)^{2})$

Construction

A DynamicRLSLPIndex instance can be constructed using either DynamicRLSLPIndex::offline_build_from_text or DynamicRLSLPIndex::online_build_from_text_file.
The following table summarizes time complexities and space usage for the two functions.

Operation	Time Complexity	Working Space (bits)
`offline_build_from_text`	$O((n + M H \log M)b)$	$O(n \log n)$
`online_build_from_text_file`	$O((n + M H \log M)b)$	$O(M \log n)$

Note

$H$: The height of the derivation tree of the RLSLP.
$b = O(1)$ if dynamic_rr_index is chosen. Otherwise, $b = O(\log^{*} n)$.

Index construction uses randomized components (see --seed), so M and, in turn, running time and memory usage can vary slightly between runs even for the same input text.

Input Format

The input text given to build is treated as a raw byte string; there is no header or length prefix.
All positions (i, j, ...) used by the API and the CLIs are 0-based.
LOCATE returns occurrence positions in the order the index happens to find them; the result is not guaranteed to be sorted (see the Query example below). LOCATE_SUM returns the sum of those positions and is intended mainly for experiments.

Requirements

C++ compiler: C++17 or later, such as GCC 7+, Clang 5+, or MSVC 2017+
CMake: 3.21 or later
A CMake-supported build tool (e.g., Make, Ninja, or an IDE/MSVC generator)

Installation

Download

git clone https://github.com/TNishimoto/dynamic-rlslp-index.git
cd dynamic-rlslp-index
git submodule update --init

Build

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release

-DCMAKE_BUILD_TYPE is used by single-configuration generators (e.g., Makefiles, Ninja); --config is used by multi-configuration generators (e.g., Visual Studio, Xcode). Passing both covers either case.

Generated Executables

After building, the following executables are generated inside the build/ directory (note: build here is the name of an executable, distinct from the build/ directory it is generated into).

Executable	Description
`build`	Builds a dynamic compressed index from an input text.
`print`	Displays details of a built dynamic compressed index.
`query`	Executes queries from a command file.

Usage

Build Dynamic Compressed Index

Build a dynamic compressed index (DynamicRLSLPIndex) for a given text.

usage: ./build --input_file_path=string [options] ... 
options:
  -i, --input_file_path     Input text file path (string)
  -o, --output_file_path    File path for writing the dynamic compressed index of the input text (string [=])
  -m, --index_mode          Index mode (dynamic_rr_index or dynamic_se_index) (string [=dynamic_rr_index])
  -s, --seed                Seed (unsigned long long [=0])
  -f, --offline_build       Offline build mode (bool [=0])
  -?, --help                print this message

Note

If --offline_build=0, DynamicRLSLPIndex is constructed using dyn_index::DynamicRLSLPIndex::online_build_from_text_file. If --offline_build=1, DynamicRLSLPIndex is constructed using dyn_index::DynamicRLSLPIndex::offline_build_from_text. --seed controls the randomized components used during construction; pass the same seed to reproduce the same index from the same input. Some internal components (e.g., RandomBitDictionary, shown as Seed: ... in the statistics below) draw their own fresh randomness on every run/load and are not controlled by --seed.

Example:

build/build -i examples/short.txt -o short.rr.idx -m dynamic_rr_index

Output

=============RESULT===============
File : examples/short.txt
Output : short.rr.idx
Index mode : dynamic_rr_index
Build mode : Online
Total time for building dynamic RLSLP index:       0 sec (0 ms/MB)
Statistics (DynamicRLSLPIndex)
  Statistics (DynamicRLSLPString)
    Mode: Fast
    Left Short Strings (Cache): 14 * 8 bytes
    Right Short Strings (Cache): 14 * 8 bytes
    Ancestor Cache List (Cache): 14 * 16 bytes
    Statistics (DynamicGrammarForLayeredRLSLP): 
      Statistics (GrammarForLayeredRLSLP): 
        Compression Algorithm:  Restricted Recompression
        Text Length:    41
        The level of the derivation tree: 70
        Statistics (DictionaryForLayeredRLSLP): 
          Number of nonterminals:               229
            Number of explicit nonterminals:            14
            Number of implicit nonterminals:            215
          Number of null nonterminals:          0
        [END]
        Statistics (RandomBitDictionary): 
          Seed: 0
          Number of short random bytes: 56
          Number of middle random bytes: 104
          Number of long random bytes: 40
        [END]
      [END]
      Statistics (FastParentDictionary): 30 pointers
        Number of lightweight Pointers: 19
        Number of middleweight Pointers: 0
        Number of heavyweight Pointers: 0
        Number of null Pointers: 11
      [END]
    [END]
  [END]
[END]
Memory footprint: 1680 KB (1 MB)
==================================

build/build -i examples/short.txt -o short.se.idx -m dynamic_se_index -f 1

Output

=============RESULT===============
File : examples/short.txt
Output : short.se.idx
Index mode : dynamic_se_index
Build mode : Offline
Total time for building dynamic RLSLP index:       0 sec (0 ms/MB)
Statistics (DynamicRLSLPIndex)
  Statistics (DynamicRLSLPString)
    Mode: Standard
    Left Short Strings (Cache): 0 * 8 bytes
    Right Short Strings (Cache): 0 * 8 bytes
    Ancestor Cache List (Cache): 0 * 16 bytes
    Statistics (DynamicGrammarForLayeredRLSLP): 
      Statistics (GrammarForLayeredRLSLP): 
        Compression Algorithm:  Signature Encoding
        Text Length:    41
        The level of the derivation tree: 8
        Statistics (DictionaryForLayeredRLSLP): 
          Number of nonterminals:               36
            Number of explicit nonterminals:            21
            Number of implicit nonterminals:            15
          Number of null nonterminals:          0
        [END]
        Statistics (RandomBitDictionary): 
          Seed: 0
          Number of short random bytes: 24
          Number of middle random bytes: 40
          Number of long random bytes: 40
        [END]
      [END]
      Statistics (FastParentDictionary): 49 pointers
        Number of lightweight Pointers: 33
        Number of middleweight Pointers: 0
        Number of heavyweight Pointers: 0
        Number of null Pointers: 16
      [END]
    [END]
  [END]
[END]
Memory footprint: 1664 KB (1 MB)
==================================

Print Dynamic Compressed Index

Display statistics and a memory breakdown for a given dynamic compressed index (DynamicRLSLPIndex).

This command can also output the following files:

A JSON file representing the input dynamic compressed index.
A JSON file representing the input RLSLP.
A plain text file representing the derivation tree of the input RLSLP.

usage: ./print --input_file_path=string [options] ... 
options:
  -i, --input_file_path                     File path to the dynamic index (string)
  -j, --output_dynamic_index_file_path      File path for writing the given dynamic index in JSON format (string [=])
  -r, --output_rlslp_file_path              File path for writing the RLSLP in JSON format (string [=])
  -d, --output_derivation_tree_file_path    File path for writing the derivation tree of the RLSLP (string [=])
  -?, --help                                print this message

Example:

build/print -i short.rr.idx -j short.rr.j.json -r short.rr.r.json -d short.rr.d.log

Output

=============RESULT===============
File : short.rr.idx
Statistics (DynamicRLSLPIndex)
  Statistics (DynamicRLSLPString)
    Mode: Fast
    Left Short Strings (Cache): 14 * 8 bytes
    Right Short Strings (Cache): 14 * 8 bytes
    Ancestor Cache List (Cache): 14 * 16 bytes
    Statistics (DynamicGrammarForLayeredRLSLP): 
      Statistics (GrammarForLayeredRLSLP): 
        Compression Algorithm:  Restricted Recompression
        Text Length:    41
        The level of the derivation tree: 70
        Statistics (DictionaryForLayeredRLSLP): 
          Number of nonterminals:               229
            Number of explicit nonterminals:            14
            Number of implicit nonterminals:            215
          Number of null nonterminals:          0
        [END]
        Statistics (RandomBitDictionary): 
          Seed: 9498760538596981853
          Number of short random bytes: 52
          Number of middle random bytes: 104
          Number of long random bytes: 40
        [END]
      [END]
      Statistics (FastParentDictionary): 30 pointers
        Number of lightweight Pointers: 19
        Number of middleweight Pointers: 0
        Number of heavyweight Pointers: 0
        Number of null Pointers: 11
      [END]
    [END]
  [END]
[END]

Memory Breakdown (DynamicRLSLPIndex): 3007 bytes
  Memory Breakdown (DynamicRLSLPString): 2335 bytes
    left_short_string_list: 136 bytes
    right_short_string_list: 136 bytes
    ancestor_cache_list: 248 bytes
    dictionary_mode: 1 bytes
    Memory Breakdown (DynamicGrammarForLayeredRLSLP): 1727 bytes
      Memory Breakdown (GrammarForLayeredRLSLP): 912 bytes
        document_counter: 80 bytes
        grammar_parsing_type: 4 bytes
        Memory Breakdown (DictionaryForLayeredRLSLP): 600 bytes
          explicit_nonterminal_rule_list_: 360 bytes
          explicit_nonterminal_level_list_: 52 bytes
          explicit_nonterminal_length_list_: 136 bytes
          relative_max_level_list_: 52 bytes
        [END]
        Memory Breakdown (RandomBitDictionary): 228 bytes
          short_random_bits_: 52 bytes
          middle_random_bits_: 104 bytes
          long_random_bits_: 40 bytes, counts: 0
          Others: 32 bytes
        [END]
      [END]
      unused_nonterminals: 24 bytes
      character_nonterminal_item_map: 216 bytes
      character_id_map: 176 bytes
      Memory Breakdown (FastParentDictionary): 399 bytes
        primaryParents: 136 bytes
        sub_pointer: 136 bytes
        sub_pointer_status_: 38 bytes
        Memory Breakdown (SubParentVector): 80 bytes, count: 2
        Memory Breakdown (FewParentDictionary): 0 bytes, count: 0
        Memory Breakdown (ManyParentDictionary): 0 bytes, count: 0
      [END]
    [END]
  [END]
y_sorted_signatures: [Skipped]
x_sorted_signatures: [Skipped]
wavelet_tree_for_range_search: [Skipped]
[END]
==================================

Note

The Seed shown under RandomBitDictionary is freshly (re-)drawn whenever the index is loaded — it is unrelated to build's --seed, so it will differ between the build output above and this print output even though both describe the same short.rr.idx.

The output files are as follows:

Query

Execute queries on a given dynamic compressed index (DynamicRLSLPIndex) using a TSV query file.

usage: ./query --input_index_path=string --input_query_path=string --output_log_path=string [options] ...
options:
  -i, --input_index_path              Input index file path (.idx) (string)
  -q, --input_query_path              Input query file path (TSV format) (string)
  -w, --output_log_path               Output log file path (string)
  -o, --output_index_path             Save updated index (optional) (string [=])
  -t, --alternative_tab_key           The alternative tab key for the query file (optional) (string [=])
  -n, --alternative_line_break_key    The alternative line break key for the query file (optional) (string [=])
  -?, --help                          print this message

Each line of the query file consists of a query name followed by tab-separated arguments. The required arguments depend on the query type (see the table below; - means the argument is not used). Lines that are blank, name an unrecognized query, or have the wrong number/type of arguments are skipped with a diagnostic message on stdout instead of aborting the run.

Because fields are tab-separated and lines are newline-separated, a field (e.g., the inserted text of an INSERT query) cannot directly contain a literal tab or newline. -t/-n let you specify a placeholder string that is substituted with a real tab/newline before the field is used; by default no substitution is performed.

Supported Queries:

Query	Param 1	Param 2	Description
`ACCESS`	`i`	`m`	Returns $T[i..i+m-1]$.
`DECOMPRESS`	`F`	`-`	Writes the string derived by the RLSLP to the file path `F`.
`LCE`	`i`	`j`	Returns the length of the longest common prefix of the two suffixes $T[i..n-1]$ and $T[j..n-1]$.
`LOCATE`	`P`	`-`	Finds all occurrence positions of pattern $P$ in $T$.
`LOCATE_SUM`	`P`	`-`	Returns the sum of all occurrence positions of pattern $P$ in $T$.
`INSERT`	`i`	`P`	Updates the input data structure by inserting string $P$ into $T$ at position `i`.
`DELETE`	`i`	`m`	Updates the input data structure by deleting substring $T[i..i+m-1]$ from $T$.
`PRINT_TREE`	`F`	`-`	Writes the derivation tree of the current RLSLP to the file path `F`.
`PRINT_CONTENT`	`F`	`-`	Writes the content of the current `DynamicRLSLPIndex` in JSON format to the file path `F`.

Note

LOCATE_SUM is used for experiments.
All positions (i, j) are 0-based.
The occurrence positions returned by LOCATE are not guaranteed to be sorted — see 3 LOCATE ... [6, 12, 18, 24, 30, 36, 0] in the example log below.

Example:

cat examples/query.tsv
build/query -i short.rr.idx -q examples/query.tsv -w query.log -o update.idx
cat query.log

DECOMPRESS      short.1.txt
PRINT_TREE      print.1.txt
ACCESS  5       15
LOCATE  cacao
DELETE  5       30
PRINT_TREE      print.2.txt
DECOMPRESS      short.2.txt
LOCATE  cacao
INSERT  5       _aaa
PRINT_TREE      print.3.txt
DECOMPRESS      short.3.txt
LOCATE  cacao

Output

=============RESULT===============
Index File:                 short.rr.idx
Query File:                 examples/query.tsv
Log File:                   query.log
Output Index File:          update.idx
Alternative Tab Key:        
Alternative Line Break Key: 
Query Time:                 1290 microseconds
==================================

Query Number    Query Name      Time(microseconds)      Result
0       DECOMPRESS      2       short.1.txt
1       PRINT_TREE      417     print.1.txt
2       ACCESS  0       _cacao_cacao_ca
3       LOCATE  64      [6, 12, 18, 24, 30, 36, 0]
4       DELETE  302
5       PRINT_TREE      156     print.2.txt
6       DECOMPRESS      1       short.2.txt
7       LOCATE  10      [6, 0]
8       INSERT  154
9       PRINT_TREE      173     print.3.txt
10      DECOMPRESS      1       short.3.txt
11      LOCATE  10      [0, 10]

The following files are generated:

API Documentation

Doxygen Documentation (in preparation)

Dependencies

This project uses the following libraries:

STool — string utilities (MIT License)
Dynamic RLSLP — a library for dynamic RLSLPs (MIT License)
B-tree plus alpha — a dynamic wavelet-matrix for range reporting queries (MIT License)
cmdline - a simple command line parser (BSD 3-Clause License)

License

This project is licensed under the MIT License. See the LICENSE file for details.

If you use this library, please cite the following paper:

@inproceedings{NishimotoTabei2026,
  author    = {Takaaki Nishimoto and
               Yasuo Tabei},
  title     = {Dynamic Grammar-Compressed Self-Index in {$\delta$}-Optimal Space},
  booktitle = {Proceedings of the European Symposium on Algorithms (ESA 2026)},
  year      = {2026},
  note      = {To appear. Full version: arXiv:2604.24080, https://doi.org/10.48550/arXiv.2604.24080}
}

If you use the dynamic_se_index mode, please also cite the following papers:

@article{DBLP:journals/dam/NishimotoIIBT20,
  author       = {Takaaki Nishimoto and
                  Tomohiro I and
                  Shunsuke Inenaga and
                  Hideo Bannai and
                  Masayuki Takeda},
  title        = {Dynamic index and {LZ} factorization in compressed space},
  journal      = {Discret. Appl. Math.},
  volume       = {274},
  pages        = {116--129},
  year         = {2020},
  url          = {https://doi.org/10.1016/j.dam.2019.01.014},
  doi          = {10.1016/j.dam.2019.01.014},
  biburl       = {https://dblp.org/rec/journals/dam/NishimotoIIBT20.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

Related software

TST-index is a variant of SE-index, but update operations have not been implemented.
dynamic r-index is a dynamic compressed string index based on run-length BWT.

References

T. Nishimoto and Y. Tabei, “Dynamic Grammar-Compressed Self-Index in $\delta$-Optimal Space”, ESA 2026 (to appear). Full version: arXiv:2604.24080.
T. Nishimoto, Y. Takabatake, and Y. Tabei, "A Dynamic Compressed Self-Index for Highly Repetitive Text Collections", Inf. Comput..
T. Nishimoto, T. I, S. Inenaga, H. Bannai, and M. Takeda, "Dynamic index and LZ factorization in compressed space", Discret. Appl. Math., 274, 2020.
T. Kociumaka et al., "Toward a Definitive Compressibility Measure for Repetitive Sequences," IEEE Trans. Inf. Theory, 2023.

Name		Name	Last commit message	Last commit date
.github/workflows		.github/workflows
examples		examples
experiment		experiment
include		include
main		main
modules		modules
scripts/excel		scripts/excel
test		test
.gitignore		.gitignore
.gitmodules		.gitmodules
CMakeLists.txt		CMakeLists.txt
Doxyfile		Doxyfile
LICENSE		LICENSE
README.md		README.md

Navigation Menu

Repository navigation

About

Repository files navigation

Dynamic RLSLP Index

Table of Contents

Quick Start

Overview

Dynamic RR index (default)

Dynamic SE index (baseline)

Construction

Input Format

Requirements

Installation

Download

Build

Generated Executables

Usage

Build Dynamic Compressed Index

Print Dynamic Compressed Index

Query

API Documentation

Dependencies

License

Related software

References

About

Releases

Packages

Contributors

Languages

Latest commit

History

Folders and files

Repository files navigation

Dynamic RLSLP Index

Table of Contents

Quick Start

Overview

Dynamic RR index (default)

Dynamic SE index (baseline)

Construction

Input Format

Requirements

Installation

Download

Build

Generated Executables

Usage

Build Dynamic Compressed Index

Print Dynamic Compressed Index

Query

API Documentation

Dependencies

License

Related software

References

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages