4 papers
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
Dominik Köppl, Gonzalo Navarro, Nicola Prezza
We propose a new representation of the offsets of the Lempel-Ziv (LZ) factorization based on the co-lexicographic order of the processed prefixes. The selected offsets tend to appr…
FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
Jin Jie Deng, Wing-Kai Hon, Dominik Köppl +1
The run-length compressed Burrows-Wheeler transform (RLBWT) used in conjunction with the backward search introduced in the FM index is the centerpiece of most compressed indexes wo…
On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
Jacqueline W. Daykin, Dominik Köppl, David Kübel +1
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries…
Space-Efficient Algorithms for Computing Minimal/Shortest Unique Substrings
Takuya Mieno, Dominik Köppl, Yuto Nakashima +3
Given a string of length , a substring of is called a shortest unique substring (SUS) for an interval if (a) occurs exactly once in , (b) $u…