18 citations · 54 across the 16 of their papers we have counts for
23 papers
Efficiency of ANS Entropy Encoders
Dmitry Kosolobov
Asymmetric Numeral Systems (ANS) is a class of entropy encoders that had an immense impact on the data compression, substituting arithmetic and Huffman coding. It was studied by di…
Internal Shortest Absent Word Queries in Constant Time and Linear Space
Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov +1
Given a string of length over an alphabet of size , we are to preprocess so that given a range , we can return a representa…
Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
Dmitry Kosolobov, Nikita Sivukhin
The notions of synchronizing and partitioning sets are recently introduced variants of locally consistent parsings with great potential in problem-solving. In this paper we propose…
Weighted Ancestors in Suffix Trees Revisited
Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi +1
The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require time for queries provided $O(n\mathop{\math…
Optimal Skeleton Huffman Trees Revisited
Dmitry Kosolobov, Oleg Merkurev
A skeleton Huffman tree is a Huffman tree in which all disjoint maximal perfect subtrees are shrunk into leaves. Skeleton Huffman trees, besides saving storage space, are also used…
Lempel-Ziv-like Parsing in Small Space
Dmitry Kosolobov, Daniel Valenzuela, Gonzalo Navarro +1
Lempel-Ziv (LZ77 or, briefly, LZ) is one of the most effective and widely-used compressors for repetitive texts. However, the existing efficient methods computing the exact LZ pars…
Compressed Multiple Pattern Matching
Dmitry Kosolobov, Nikita Sivukhin
Given strings over the alphabet , the classical Aho--Corasick data structure allows us to find all occurrences of the strings in any text in $O(…
Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov +1
Given a threshold and a set of haplotype sequences, each having length , the minimum segmentation problem for founder reconstruction…
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…
Tight Lower Bounds for the Longest Common Extension Problem
Dmitry Kosolobov
The longest common extension problem is to preprocess a given string of length into a data structure that uses bits on top of the input and answers in time the qu…
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 …
Detecting One-variable Patterns
Dmitry Kosolobov, Florin Manea, Dirk Nowotka
Given a pattern such that , where is a variable and $\overset{{}_{\lefta…
Finding the Leftmost Critical Factorization on Unordered Alphabet
Dmitry Kosolobov
We present a linear time and space algorithm computing the leftmost critical factorization of a given string on an unordered alphabet.
Computing Runs on a General Alphabet
Dmitry Kosolobov
We describe a RAM algorithm computing all runs (maximal repetitions) of a given string of length over a general ordered alphabet in time and linear spa…
Faster Lightweight Lempel-Ziv Parsing
Dmitry Kosolobov
We present an algorithm that computes the Lempel-Ziv decomposition in time and bits of space, where is a constant rational parameter, …
Online Detection of Repetitions with Backtracking
Dmitry Kosolobov
In this paper we present two algorithms for the following problem: given a string and a rational , detect in the online fashion the earliest occurrence of a repetition of ex…
Online Square Detection
Dmitry Kosolobov
The online square detection problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. Recall that a square is a string…
Lempel-Ziv Factorization May Be Harder Than Computing All Runs
Dmitry Kosolobov
The complexity of computing the Lempel-Ziv factorization and the set of all runs (= maximal repetitions) is studied in the decision tree model of computation over ordered alphabet.…
Is Linear Recognizable Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur
Given a language that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language ,…
Finding Distinct Subpalindromes Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur
We exhibit an online algorithm finding all distinct palindromes inside a given string in time over an ordered alphabet and in time over an unordered alphabe…