Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections

DOI10.1007/978-3-540-89097-3_17zbMath1345.68124OpenAlexW1577336816MaRDI QIDQ5505395

Niko Välimäki, Jouni Sirén, Veli Mäkinen, Gonzalo Navarro

Publication date: 27 January 2009

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-89097-3_17

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (23)

FM-index of alignment: a compressed index for similar strings ⋮ An improved algorithm for the all-pairs suffix-prefix problem ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Composite Repetition-Aware Data Structures ⋮ Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis ⋮ On compressing and indexing repetitive sequences ⋮ String Indexing with Compressed Patterns ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ FM-index of alignment with gaps ⋮ A faster implementation of online RLBWT and its application to LZ77 parsing ⋮ Wavelet trees for all ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Fast Label Extraction in the CDAWG ⋮ Self-indexing Based on LZ77 ⋮ Flexible indexing of repetitive collections ⋮ Unnamed Item ⋮ Unnamed Item ⋮ LZ77 computation based on the run-length encoded BWT ⋮ Unnamed Item ⋮ Top tree compression of tries ⋮ LZ-End Parsing in Linear Time ⋮ Lazy Lempel-Ziv Factorization Algorithms

This page was built for publication: Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections