This library provides some iterators (e.g., suffix array, inverse suffix array, longest common perfix array, and etc.) in small working memory using a given Run-Length BWT (RLBWT).
Our iterating algorithms on RLBWT is based on the following paper.
Travis Gagie, Gonzalo Navarro, Nicola Prezza:
Optimal-Time Text Indexing in BWT-runs Bounded Space. SODA 2018: 1459-1477
This library supports the following operations:
- RLBWT
- It uses SIZE(VEC<uint64_t>(r)) + SIZE(VEC(r)) bytes, where VEC<A>(B) is the byte sizes used by vector<A> of size B.
- The construction of the RLBWT of T for a given string T.
- This construction algorithm uses OnlineRLBWT implemented by Tomohiro I.
- The backward iterator for the inverse suffix array(ISA) of T for a given RLBWT of T.
- It runs in O(log r) time per element.
- It uses 2 * SIZE(VEC<uint64_t>(r)) bytes.
- The backward iterator for the text of T for a given RLBWT of T.
- It runs in O(log r) time per element.
- It uses SIZE(VEC(r)) + SIZE(ISA_ITERATOR) bytes.
- The Forward iterator for the suffix array(SA) of T for a given RLBWT of T.
- It runs in O(log r) time per element.
- It uses 2 * SIZE(VEC<uint64_t>(r)) bytes.
- The Forward iterator for the longest common prefix(LCP) of T for a given RLBWT of T.
- It runs in O(log r) time per element.
- It uses 3 * SIZE(VEC<uint64_t>(r)) bytes.
- The postorder iterator for the suffix tree nodes of T for a given RLBWT of T.
- It runs in O(n log r) time.
- It uses SIZE(LCP_ITERATOR) + alpha bytes.
- The postorder iterator for maximal substrings in T for a given RLBWT of T.
- It runs in O(n log r) time.
- It uses SIZE(ST_ITERATOR) + SIZE(VEC<uint64_t>(r)) bytes.
The source codes in 'module' directory are maintained in different repositories. So, to download all the necessary source codes, do the following:
git clone https://github.com/TNishimoto/rlbwt_iterator.git
cd rlbwt_iterator
git submodule init
git submodule update
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE="Release" -DCMAKE_INSTALL_PREFIX="./" ..
make
make install
After you excecute above commands, lib and include directories are created in the build directory.
You can use iterators in this library using the two directories.
See also the sample program in test directory
and the CMakeLists.txt of the file.
This program is released under the MIT licence.