65 citations · 220 across the 15 of their papers we have counts for
17 papers · 1 filter
Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl +1
The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it.…
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…
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…
Linear-time string indexing and analysis in small space
Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen +1
The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Fe…
String Inference from the LCP Array
Juha Kärkkäinen, Marcin Piątkowski, Simon J. Puglisi
The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of t…
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…
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
Document Counting in Practice
Travis Gagie, Aleksi Hartikainen, Juha Kärkkäinen +3
We address the problem of counting the number of strings in a collection where a given pattern appears, which has applications in information retrieval and data mining. Existing so…
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…
A Compressed Self-Index for Genomic Databases
Travis Gagie, Juha Kärkkäinen, Yakov Nekrich +1
Advances in DNA sequencing technology will soon result in databases of thousands of genomes. Within a species, individuals' genomes are almost exact copies of each other; e.g., any…
A Faster Grammar-Based Self-Index
Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen +2
To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on grammars. In this paper we show how, given a straight…
Fixed Block Compression Boosting in FM-Indexes
Juha Kärkkäinen, Simon J. Puglisi
A compressed full-text self-index occupies space close to that of the compressed text and simultaneously allows fast pattern matching and random access to the underlying text. Amon…
Counting Colours in Compressed Strings
Travis Gagie, Juha Kärkkäinen
Suppose we are asked to preprocess a string \(s [1..n]\) such that later, given a substring's endpoints, we can quickly count how many distinct characters it contains. In this pape…
Pattern Kits
Travis Gagie, Kalle Karhu, Juha Kärkkäinen +2
Suppose we have just performed searches in a self-index for two patterns and and now we want to search for their concatenation \A B); how can we best make use of our previo…