107 citations · 409 across the 18 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.DS2013★ 17 cited
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…
cs.DS2013★ 39 cited
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…