research
∙
08/11/2023
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
A parameterized string (p-string) is a string over an alphabet (Σ_s∪Σ_p)...
share
research
∙
06/09/2023
Space-time Trade-offs for the LCP Array of Wheeler DFAs
Recently, Conte et al. generalized the longest-common prefix (LCP) array...
research
∙
05/10/2023
Acceleration of FM-index Queries Through Prefix-free Parsing
FM-indexes are a crucial data structure in DNA alignment, for example, b...
research
∙
11/14/2022
Augmented Thresholds for MONI
MONI (Rossi et al., 2022) can store a pangenomic dataset T in small spac...
research
∙
07/06/2022
Computing NP-hard Repetitiveness Measures via MAX-SAT
Repetitiveness measures reveal profound characteristics of datasets, and...
research
∙
06/30/2022
Computing the Parameterized Burrows–Wheeler Transform Online
Parameterized strings are a generalization of strings in that their char...
research
∙
03/28/2022
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
As nowadays Machine Learning (ML) techniques are generating huge data co...
research
∙
02/15/2022
Longest (Sub-)Periodic Subsequence
We present an algorithm computing the longest periodic subsequence of a ...
research
∙
01/18/2022
Computing Longest (Common) Lyndon Subsequences
Given a string T with length n whose characters are drawn from an ordere...
research
∙
11/03/2021
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
We propose a new representation of the offsets of the Lempel-Ziv (LZ) fa...
research
∙
10/04/2021
FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
The run-length compressed Burrows-Wheeler transform (RLBWT) used in conj...
research
∙
08/12/2021
Space-Efficient Huffman Codes Revisited
Canonical Huffman code is an optimal prefix-free compression code whose ...
research
∙
07/06/2021
On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
We characterize those strings whose suffix arrays are based on arithmeti...
research
∙
05/28/2021
Grammar Index By Induced Suffix Sorting
Pattern matching is the most central task for text indices. Most recent ...
research
∙
04/18/2021
Load-Balancing Succinct B Trees
We propose a B tree representation storing n keys, each of k bits, in ei...
research
∙
11/11/2020
PHONI: Streamed Matching Statistics with Multi-Genome References
Computing the matching statistics of patterns with respect to a text is ...
research
∙
04/27/2020
In-Place Bijective Burrows-Wheeler Transforms
One of the most well-known variants of the Burrows-Wheeler transform (BW...
research
∙
04/11/2020
Grammar-compressed Self-index with Lyndon Words
We introduce a new class of straight-line programs (SLPs), named the Lyn...
research
∙
11/16/2019
Constructing the Bijective BWT
The Burrows-Wheeler transform (BWT) is a permutation whose applications ...
research
∙
08/14/2019
Re-Pair In-Place
Re-Pair is a grammar compression scheme with favorably good compression ...
research
∙
07/07/2019
Bidirectional Text Compression in External Memory
Bidirectional compression algorithms work by substituting repeated subst...
research
∙
06/14/2019
Dynamic Path-Decomposed Tries
A keyword dictionary is an associative array whose keys are strings. Rec...
research
∙
05/30/2019
Compact Data Structures for Shortest Unique Substring Queries
Given a string T of length n, a substring u = T[i.. j] of T is called a ...
research
∙
05/01/2019
Separate Chaining Meets Compact Hashing
While separate chaining is a common strategy for resolving collisions in...
research
∙
04/16/2019