65 citations · 220 across the 15 of their papers we have counts for
19 papers
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…
Document Retrieval on Repetitive String Collections
Travis Gagie, Aleksi Hartikainen, Kalle Karhu +4
Most of the fastest-growing string collections today are repetitive, that is, most of the constituent documents are similar to many others. As these collections keep growing, a key…