6 papers
NP-Completeness for the Space-Optimality of Double-Array Tries
Hideo Bannai, Keisuke Goto, Shunsuke Kanda +1
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract…
Acceleration of FM-index Queries Through Prefix-free Parsing
Aaron Hong, Marco Oliva, Dominik Köppl +3
FM-indexes are a crucial data structure in DNA alignment, for example, but searching with them usually takes at least one random access per character in the query pattern. Ferragin…
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…
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…