8 papers
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…
Time-Optimal Construction of String Synchronizing Sets
Jonas Ellert, Tomasz Kociumaka
A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka;…
Approximate Cartesian Tree Matching with Substitutions
Panagiotis Charalampopoulos, Jonas Ellert, Manal Mohamed
The Cartesian tree of a sequence captures the relative order of the sequence's elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly…
Optimal Square Detection Over General Alphabets
Jonas Ellert, Paweł Gawrychowski, Garance Gourdel
Squares (fragments of the form , for some string ) are arguably the most natural type of repetition in strings. The basic algorithmic question concerning squares is to check…
Linear Time Runs over General Ordered Alphabets
Jonas Ellert, Johannes Fischer
A run in a string is a maximal periodic substring. For example, the string contains the runs and $\texttt{ee} = \texttt…
LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank of "europar" amongst the strings "eureka", "eurasia…
Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer +4
We present the first linear time algorithm to construct the -bit version of the Lyndon array for a string of length using only bits of working space. A simpler varia…
Bidirectional Text Compression in External Memory
Patrick Dinklage, Jonas Ellert, Johannes Fischer +2
Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such a…