Dominik Köppl

activity

20152026

most citedCompression with the tudocomp Framework

11 citations · 20 across the 20 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.DS2015

Lempel-Ziv Computation In Compressed Space (LZ-CICS)

Dominik Köppl, Kunihiko Sadakane

We show that both the Lempel Ziv 77- and the 78-factorization of a text of length $n$ on an integer alphabet of size $σ$ can be computed in $O (n l g l g σ)$ time (linear time if we…

cs.DS2015

Efficiently Finding All Maximal $α$ -gapped Repeats

Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga +2

For $α \geq 1$ , an $α$ -gapped repeat in a word $w$ is a factor $uv u$ of $w$ such that $∣ uv ∣ \leq α ∣ u ∣$ ; the two factors $u$ in such a repeat are called arms, while the factor $v$ is…

cs.DS2015

Deterministic Sparse Suffix Sorting in the Restore Model

Johannes Fischer, Tomohiro I, Dominik Köppl

Given a text $T$ of length $n$ , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of $T$ in $O(c \sqrt{\lg n}…

Lempel-Ziv Computation In Compressed Space (LZ-CICS)

Efficiently Finding All Maximal α-gapped Repeats

Deterministic Sparse Suffix Sorting in the Restore Model

Efficiently Finding All Maximal $α$ -gapped Repeats