3 papers
cs.DS2026
Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets
Jonas Ellert, Lukas Nalbach
The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number of phrases that each refer to an earlier occurrence. It is this phrase count, rather than t…
cs.DS2026
Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching
Johannes Fischer, Lukas Nalbach
Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics. Bi-directional r-indexes support left- and right-extension of a pattern and there…
cs.DS2025
RLZ-r and LZ-End-r: Enhancing Move-r
Patrick Dinklage, Johannes Fischer, Lukas Nalbach +1
In pattern matching on strings, a locate query asks for an enumeration of all the occurrences of a given pattern in a given text. The r-index [Gagie et al., 2018] is a recently pre…