18 citations · 54 across the 16 of their papers we have counts for
4 papers · 1 filter
Run Compressed Rank/Select for Large Alphabets
José Fuentes-Sepúlveda, Juha Kärkkäinen, Dmitry Kosolobov +1
Given a string of length that is composed of runs of letters from the alphabet such that , we describe a data structure that, provided…
Comparison of LZ77-type Parsings
Dmitry Kosolobov, Arseny M. Shur
We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of them are defined as greedily constructed parsings encoding each phras…
Relations Between Greedy and Bit-Optimal LZ77 Encodings
Dmitry Kosolobov
This paper investigates the size in bits of the LZ77 encoding, which is the most popular and efficient variant of the Lempel-Ziv encodings used in data compression. We prove that,…
On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga +3
We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally…