107 citations · 409 across the 18 of their papers we have counts for
18 papers
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string from left to right into blocks (called phrases) so that each ph…
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Dominik Kempa, Tomasz Kociumaka
In the last decades, the necessity to process massive amounts of textual data fueled the development of compressed text indexes: data structures efficiently answering queries on a…
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
Rajat De, Dominik Kempa
Grammar compression is a general compression framework in which a string of length is represented as a context-free grammar of size whose language contains only . In…
Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa, Tomasz Kociumaka
The suffix array of a text of length is a permutation of describing the lexicographical ordering of suffixes of , and it is considered to be…
Breaking the -Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
Dominik Kempa, Tomasz Kociumaka
The suffix array and the suffix tree are the two most fundamental data structures for string processing. For a length- text, however, they use bits of space, which…
Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
Dominik Kempa, Ben Langmead
Grammar compression is, next to Lempel-Ziv (LZ77) and run-length Burrows-Wheeler transform (RLBWT), one of the most flexible approaches to representing and processing highly compre…
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa, Tomasz Kociumaka
Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text of length , permutes its symbols according to the lexicographic order of suffixes of…
String Attractors: Verification and Optimization
Dominik Kempa, Alberto Policriti, Nicola Prezza +1
String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set is a…
Optimal Construction of Compressed Indexes for Highly Repetitive Texts
Dominik Kempa
We propose algorithms that, given the input string of length over integer alphabet of size , construct the Burrows-Wheeler transform (BWT), the permuted longest-common-prefi…
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa, Nicola Prezza
A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this, decades of resea…
On the Size of Lempel-Ziv and Lyndon Factorizations
Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima +2
Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing the structure and complexity of strings, but their combinatorial structure is very dif…
LZ-End Parsing in Compressed Space
Dominik Kempa, Dmitry Kosolobov
We present an algorithm that constructs the LZ-End parsing (a variation of LZ77) of a given string of length in expected time and space, where …
Lempel-Ziv Decoding in External Memory
Djamal Belazzougui, Juha Kärkkäinen, Dominik Kempa +1
Simple and fast decoding is one of the main advantages of LZ77-type text encoding used in many popular file compressors such as gzip and 7zip. With the recent introduction of exter…
Diverse Palindromic Factorization is NP-Complete
Hideo Bannai, Travis Gagie, Shunsuke Inenaga +5
We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.
A Subquadratic Algorithm for Minimum Palindromic Factorization
Gabriele Fici, Travis Gagie, Juha Kärkkäinen +1
We give an -time, -space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S [1..n…
Lempel-Ziv Parsing in External Memory
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
For decades, computing the LZ factorization (or LZ77 parsing) of a string has been a requisite and computationally intensive step in many diverse applications, including text index…
Lightweight Lempel-Ziv Parsing
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
We introduce a new approach to LZ77 factorization that uses O(n/d) words of working space and O(dn) time for any d >= 1 (for polylogarithmic alphabet sizes). We also describe caref…
Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
Computing the LZ factorization (or LZ77 parsing) of a string is a computational bottleneck in many diverse applications, including data compression, text indexing, and pattern disc…