A string attractor of a string T[1..|T|] is a set of positions Γ of T such that any substring w of T has an occurrence that crosses a position in Γ, i.e., there is a position i such that w = T[i..i+|w|-1] and the intersection [i,i+|w|-1]∩ Γ is nonempty. The size of the smallest string attractor of Fibonacci words is known to be 2. We completely characterize the set of all smallest string attractors of Fibonacci words, and show a recursive formula describing the 2^{n-4} + 2^{⌈n/2⌉ - 2} distinct position pairs that are the smallest string attractors of the nth Fibonacci word for n ≥ 7. Similarly, the size of the smallest string attractor of period-doubling words is known to be 2. We also completely characterize the set of all smallest string attractors of period-doubling words, and show a formula describing the two distinct position pairs that are the smallest string attractors of the nth period-doubling word for n ≥ 2. Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors.

A string S is called a square if it can be written as the concatenation of two identical strings. Two strings P and Q of the same length are said to square match if, for every substring of P, it is a square if and only if the corresponding substring of Q is also a square. The square pattern matching problem asks for locating all substrings of a given text T of length n that square match a query pattern P of length m. This notion captures similarity in repetition structures and is motivated by applications in areas such as bioinformatics and music structure analysis. In this paper, we introduce a novel technique, called the longest prefix square (LPS) encoding, which represents the square structure of a string as an integer array of the same length. We show that two strings square match if and only if they have identical LPS encodings. Based on this result, we construct an index solving the square pattern matching problem in time O(m lg m + occ) using O(nlg²n) bits of space, where occ denotes the number of occurrences of substrings in T that square match P. If the LPS encoding of P is precomputed, the query time improves to O(m + occ).

We study the problem of matching a determinate pattern against an indeterminate text of the same length n, where each text position is a set of possible characters drawn from an alphabet Σ of size σ. We study this matching problem under the order-preserving and parameterized matching setting. For that, we encode character sets by bit expressions using sum-free sequences. This encoding enables constant-time character comparisons and avoids explicit set operations. We present an optimal 𝒪(n) time algorithm for order-preserving matching and an 𝒪(n+(σ_p^x ⋅ σ_p^y) √{σ_p^x + σ_p^y}) time algorithm for parameterized matching, where σ_p^x and σ_p^y denote the number of distinct parameterized symbols in the pattern and the text, respectively. The proposed techniques significantly reduce overhead while maintaining exactness, offering practical performance improvements for pattern matching under uncertainty. Additionally, we extend the parameterized matching framework to allow mismatches, for which we present an algorithm with time complexity 𝒪(σ² n log n + n σ² √σ log(n σ)).

Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-time algorithms for several classical problems on strings, including the computation of the longest repeating suffix array, the (reversed) Lempel-Ziv 77 factorization, and the maintenance of minimal unique substrings, all in an online manner. Our solutions improve over the best known running times for these problems in terms of the worst-case time per letter, for which we achieve a poly-log-logarithmic time complexity, within a linear space. Best known results for these problems require a poly-logarithmic time complexity per letter or only provide amortized complexity bounds. As a result of independent interest, we give conversions between the longest previous factor array and the longest repeating suffix array in space and time bounds based on their irreducible representations, which can have sizes sublinear in the length of the input string.

Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al.,2022]. In that light, we wonder about other types of queries, which are of particular interest to bioinformatics: the search for the longest repeating factor, unique substrings, absent words, anti-powers, and longest previous factors. While we obtain a polynomial time algorithm for the first problem on ED strings, we show that all others are NP-hard to compute, some of them even under the restriction that the input can be modelled as an indeterminate or GD string.

Elastic-degenerate (ED) strings generalize classic strings by allowing each position to store a set of up to$h$strings of arbitrary lengths [2]. An ED string is a restricted version of a regular expression whose expressiveness still causes a combinatorial explosion of possible resolutions (i.e., the members of its language), making classical pattern matching and indexing techniques either inefficient or inapplicable. A position in an ED string is called solid if it stores a single symbol, otherwise elastic. We introduce the Min/Max wavelet tree (MM-WT), a variant of the wavelet tree supporting semantics-aware rank and select on ED strings. Each leaf stores two arrays per symbol$c, \min _{c}$and$\max _{c}$, giving for each position the minimum and maximum symbol count across all alternatives. Prefix sums bound the number of occurrences in any resolution of a prefix, so sm-rank$(c, i)$returns an interval$\left[r_{\min}, r_{\max}\right]$of possible ranks, and sm-select$(c, j)$returns an interval for the$j$-th occurrence of$c$. On classic strings, min and max collapse to the same counts and the structure becomes a standard wavelet tree. The structure uses the same space as a subset wavelet tree [1] internally, plus$\mathcal{O}(n \sigma \log h)$bits for the min/max arrays, and supports both queries in$\mathcal{O}(\log \sigma)$time.

We introduce Attractor Matching, a new framework for structural string comparison built upon the theory of string attractors. Given a pattern$x$of length$m$and one of its attractors$\Gamma_{x}$, the problem asks for all substrings$y[i. . i+m-1]$of a text$y$such that$\Gamma_{x}$is also an attractor of$y[i. . i+m-1]$. Unlike classical notions of string matching, which rely on character equality or distance measures, attractor matching focuses on the structural properties that govern repetitiveness and compressibility. Our contribution is fourfold. First, we adapt the IsAttractor algorithm of Béal et al. by combining the DAWG with the slidingwindow technique of Blumer, enabling online attractor verification as the window advances over the text. Second, we reformulate the verification procedure on the Compressed DAWG (CDAWG), obtaining a more compact representation that preserves correctness. Third, we employ the sliding-window CDAWG method of Inenaga et al., which allows efficient attractor matching on sliding-window maintained CDAWGs with incremental updates. Finally, we introduce a relaxed variant, Attractor Matching with Mismatches, where the pattern attractor may be extended by at most$\rho$additional positions, enabling structurally tolerant matching. This paradigm bridges compression and similarity, opening new directions for structure-aware pattern matching.

We develop an Answer Set Programming (ASP)-based approach for computing the smallest bidirectional macro schemes (BMSs), a fundamental NP-hard optimization problem in dictionary-based compression. Our approach relies on high-level ASP encodings and delegates both the grounding and solving tasks to an off-the-shelf ASP solver. The proposed encoding is compact and extensible, and leverages advanced ASP techniques to improve scalability, including ASP modulo acyclicity and refined declarative encodings of acyclicity constraints. We further show that our ASP encoding can be naturally extended to compute the smallest straight-line programs (SLPs), another important NP-hard measure of repetitiveness. Furthermore, we establish the competitiveness of our approach by empirically contrasting it with a more dedicated MaxSAT-based approach.

The size of the smallest suffixient set of positions of a string recently emerged as a new measure of string repetitiveness - a measure reflecting how much of repetitive content the string contains. We study how to maintain the smallest suffixient set online in near-real-time, that is with small (in our case, polyloglog) worst-case time for processing each letter. Two frameworks are considered: when the text is given letter-by-letter in either right-to-left or left-to-right order. Our central algorithmic tool is Weiner’s suffix tree algorithm and associated algorithmic primitives for its efficient implementation.

Abstract We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string w , a bidirectional macro scheme of size $$ O ( r_B{} )$$ O ( r B ) can be induced from the BBWT of w , where $$ r_B{} $$ r B is the number of maximal same-symbol runs in the BBWT. We also show that $$ r_B{} = O ( z \, \log ^{ 2 }\, n ) $$ r B = O ( z log 2 n ) , where n is the length of w and z is the number of Lempel-Ziv 77 factors of w . Then, we show a separation between BBWT and BWT by a family of strings with $$ r_B{} = \Omega ( \log \, n ) $$ r B = Ω ( log n ) but having only $$ r= 2 $$ r = 2 , where $${r}$$ r is the maximal same-symbol runs in the standard Burrows–Wheeler transform (BWT). However, we observe that the smallest $$ r_B{} $$ r B among all cyclic rotations of w is always at most $$ r{} $$ r . While computing an optimal rotation yielding the smallest $$ r_B$$ r B in $$ o ( n ^ {2} ) $$ o ( n 2 ) time remains an open problem, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O ( n ) time using right and left Lyndon trees. We also show that the optimal rotations can be computed in $$ \tilde{O} (nh) $$ O ~ ( n h ) time, where

Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation of some of these measures is NP-hard, and straight-forward computation is infeasible for datasets of even small sizes. Three such measures are the smallest size of a string attractor, the smallest size of a bidirectional macro scheme, and the smallest size of a straight-line program. While a vast variety of implementations for heuristically computing approximations exist, exact computation of these measures has received little to no attention. In this article, we present MAX-SAT formulations that provide the first non-trivial implementations for exact computation of smallest string attractors, smallest bidirectional macro schemes, and smallest straight-line programs. Computational experiments show that our implementations work for texts of length up to a few hundred for straight-line programs and bidirectional macro schemes, and texts even over a million for string attractors.

Cartesian tree matching is a form of generalized pattern matching where a substring of the text matches with the pattern if they share the same Cartesian tree. This form of matching finds application for time series of stock prices and can be of interest for melody matching between musical scores. For the indexing problem, the state-of-the-art data structure is a Burrows-Wheeler transform based solution due to [Kim and Cho, CPM'21], which uses nearly succinct space and can count the number of substrings that Cartesian tree match with a pattern in time linear in the pattern length. The authors address the construction of their data structure with a straight-forward solution that, however, requires pointer-based data structures, resulting in O(n lg n) bits of space, where n is the text length [Kim and Cho, CPM'21, Section A.4]. We address this bottleneck by a construction that requires O(n lg σ) bits of space and has a time complexity of O(n (lg σ lg n)/(lg lg n)), where σ is alphabet size. Additionally, we can extend this index for indexing multiple circular texts in the spirit of the extended Burrows-Wheeler transform without sacrificing the time and space complexities. We present this index in a dynamic variant, where we pay a logarithmic slowdown and need space linear in the input texts in bits for the extra functionality that we can incrementally add texts. Our extended setting is of interest for finding repetitive motifs common in the aforementioned applications, independent of offsets and scaling.

Abstract We study succinct variants of B trees in the word RAM model that require $$s + o(s)$$ bits of space, where s is the number of bits essentially needed for storing keys and possibly other satellite values. Assuming that elements are sorted by keys (not necessarily in the order of their integer representations), our B trees support standard operations such as searching, insertion and deletion of elements. In some applications it is useful to associate a satellite value to each element, and to support aggregate operations such as computing the sum of values, the minimum/maximum value in a given range, or search operations based on those values. We propose a B tree representation storing n elements in $$s + \mathcal {O}(s / \lg n)$$ bits of space and supporting all mentioned operations in $$\mathcal {O}(\lg n)$$ time. Operations on integer-ordered keys and satellite values can be accelerated to $$\mathcal {O}(\lg n / \lg \lg n)$$ time if we use $$s + \mathcal {O}(s \lg \lg n / \lg n)$$ bits of space. The time is retained for special kind of aggregate functions that can be computed bit-parallel in constant time. For integer-ordered keys, we can also compress the space s to match compression measures using difference encoding of the keys while retaining the operational time complexities. For the last enhancement, we allow us to pre-compute tables of $$o(n)$$ bits.

We show that computing the smallest run-length straight line program (RLSLP) and the smallest collage system is NP-hard. For computing the smallest RLSLP, we give an encoding in MAX-SAT.

We propose algorithms computing the semi-greedy Lempel–Ziv 78 (LZ78), the Lempel–Ziv Double (LZD), and the Lempel–Ziv–Miller–Wegman (LZMW) factorizations in linear time for integer alphabets. For LZD and LZMW, we additionally propose data structures that can be constructed in linear time, which can solve the substring compression problems for these factorizations in time linear in the output size.

The Burrows–Wheeler transform (BWT) provides a succinct way to index text for pattern matching queries. Notable variants are (a) the extended BWT (eBWT) capable to index multiple input texts for circular pattern matching, or (b) the parameterized BWT (pBWT) for parameterized pattern matching. A natural extension is the combination of the virtues of both variants into a new data structure, whose name we coin with extended parameterized BWT (epBWT). We show that the epBWT supports circular pattern matching in context of parameterized pattern matching on multiple texts, within the same complexities as known solutions presented for the pBWT [Kim and Cho, IPL’21] for patterns shorter than the shortest indexed text.

A parameterized string (p-string) is a string over an alphabet (Σ_s ∪ Σ_p), where Σ_s and Σ_p are disjoint alphabets for static symbols (s-symbols) and for parameter symbols (p-symbols), respectively. Two p-strings x and y are said to parameterized match (p-match) if and only if x can be transformed into y by applying a bijection on Σ_p to every occurrence of p-symbols in x. The indexing problem for p-matching is to preprocess a p-string T of length n so that we can efficiently find the occurrences of substrings of T that p-match with a given pattern. Let σ_s and respectively σ_p be the numbers of distinct s-symbols and p-symbols that appear in T and σ = σ_s + σ_p. Extending the Burrows-Wheeler Transform (BWT) based index for exact string pattern matching, Ganguly et al. [SODA 2017] proposed parameterized BWTs (pBWTs) to design the first compact index for p-matching, and posed an open problem on how to construct the pBWT-based index in compact space, i.e., in O(n lg |Σ_s ∪ Σ_p|) bits of space. Hashimoto et al. [SPIRE 2022] showed how to construct the pBWT for T, under the assumption that Σ_s ∪ Σ_p = [0..O(σ)], in O(n lg σ) bits of space and O(n (σ_p lg n)/(lg lg n)) time in an online manner while reading the symbols of T from right to left. In this paper, we refine Hashimoto et al.’s algorithm to work in O(n lg σ) bits of space and O(n (lg σ_p lg n)/(lg lg n)) time in a more general assumption that Σ_s ∪ Σ_p = [0..n^{O(1)}]. Our result has an immediate application to constructing parameterized suffix arrays in O(n (lg σ_p lg n)/(lg lg n)) time and O(n lg σ) bits of working space. We also show that our data structure can support backward search, a core procedure of BWT-based indexes, at any stage of the online construction, making it the first compact index for p-matching that can be constructed in compact space and even in an online manner.

We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphabet ordering, and give tight upper and lower bounds for both operations. For both lower bounds, we use the family of Fibonacci words. For the bounds on edit operations, our analysis makes heavy use of properties of the Lyndon factorization of Fibonacci words to characterize the structure of lex-parse.

Abstract Given a string T of length n whose characters are drawn from an ordered alphabet of size $$\sigma $$ σ , its longest Lyndon subsequence is a maximum-length subsequence of T that is a Lyndon word. We propose algorithms for finding such a subsequence in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$ O ( n 3 ) time with $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n)$$ O ( n ) space, or online in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$ O ( n 3 ) space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length at most n in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^4 \sigma )$$ O ( n 4 σ ) time using $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^2)$$ O ( n 2 ) space.

We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows–Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.

MONI (Rossi et al., 2022) can store a pangenomic dataset T in small space and later, given a pattern P, quickly find the maximal exact matches (MEMs) of P with respect to T. In this paper we consider its one-pass version (Boucher et al., 2021), whose query times are dominated in our experiments by longest common extension (LCE) queries. We show how a small modification lets us avoid most of these queries which significantly speeds up MONI in practice while only slightly increasing its size.

FM-indexes are a crucial data structure in DNA alignment, for example, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [5] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus support faster searches. Since DNA lacks natural word-boundaries, however, it is necessary to parse it somehow before applying word-based FM-indexing. Last year, Deng et al. [3] proposed parsing genomic data by induced suffix sorting, and showed the resulting word-based FM-indexes support faster counting queries than standard FM-indexes when patterns are a few thousand characters or longer. In this paper we show that using prefix-free parsing-which takes parameters that let us tune the average length of the phrases-instead of induced suffix sorting, gives a significant speedup for patterns of only a few hundred characters. We implement our method and demonstrate it is between 3 and 18 times faster than competing methods on queries to GRCh38. And was consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it is very clear that our method accelerates the performance of count over all state-of-the-art methods with a minor increase in the memory. The source code for PFP-FM is available at https://github.com/marco-oliva/afm.

MOTIVATION: The Positional Burrows-Wheeler Transform (PBWT) is a data structure that indexes haplotype sequences in a manner that enables finding maximal haplotype matches in h sequences containing w variation sites in O(hw) time. This represents a significant improvement over classical quadratic-time approaches. However, the original PBWT data structure does not allow for queries over Biobank panels that consist of several millions of haplotypes, if an index of the haplotypes must be kept entirely in memory. RESULTS: In this article, we leverage the notion of r-index proposed for the BWT to present a memory-efficient method for constructing and storing the run-length encoded PBWT, and computing set maximal matches (SMEMs) queries in haplotype sequences. We implement our method, which we refer to as μ-PBWT, and evaluate it on datasets of 1000 Genome Project and UK Biobank data. Our experiments demonstrate that the μ-PBWT reduces the memory usage up to a factor of 20% compared to the best current PBWT-based indexing. In particular, μ-PBWT produces an index that stores high-coverage whole genome sequencing data of chromosome 20 in about a third of the space of its BCF file. μ-PBWT is an adaptation of techniques for the run-length compressed BWT for the PBWT (RLPBWT) and it is based on keeping in memory only a succinct representation of the RLPBWT that still allows the efficient computation of set maximal matches (SMEMs) over the original panel. AVAILABILITY AND IMPLEMENTATION: Our implementation is open source and available at https://github.com/dlcgold/muPBWT. The binary is available at https://bioconda.github.io/recipes/mupbwt/README.html.

We present an algorithm computing the longest periodic subsequence of a string of length n in O(n7) time with O(n3) space. We obtain improvements when restricting the exponents or extending the search allowing the reported subsequence to be subperiodic down to O(n2) time and O(n) space. By allowing subperiodic subsequences in the output, the task becomes finding the longest bordered subsequence, for which we devise a conditional lower bound.

A canonical Huffman code is an optimal prefix-free compression code whose codewords enumerated in the lexicographical order form a list of binary words in non-decreasing lengths. Gagie et al. (2015) gave a representation of this coding capable of encoding and decoding a symbol in constant worst-case time. It uses σlg⁡ℓmax+o(σ)+O(ℓmax2) bits of space, where σ and ℓmax are the alphabet size and maximum codeword length, respectively. We refine their representation to reduce the space complexity to σlg⁡ℓmax(1+o(1)) bits while preserving the constant encode and decode times. Our algorithmic idea can be applied to any canonical code.

The run-length compressed Burrows-Wheeler transform (RLBWT) used in conjunction with the backward search introduced in the FM index is the centerpiece of most com-pressed indexes working on highly-repetitive data sets like biological sequences. Compared to grammar indexes, the size of the RLBWT is often much bigger, but queries like counting the occurrences of long patterns can be done much faster than on any existing grammar index so far. In this paper, we combine the virtues of a grammar with the RLBWT by building the RLBWT on top of a special grammar based on induced suffix sorting. Our experiments reveal that our hybrid approach outperforms the classic RLBWT with respect to the index sizes, and with respect to query times on biological data sets for sufficiently long patterns, which could be interesting for aligning long reads in bioinformatics.

We give memory-friendly algorithms computing the compression schemes plcpcomp or lexparse in linear or near-linear time, and give upper and lower bounds on the space requirements of our algorithm computing plcpcomp.

We propose a new representation of the offsets of the Lempel-Ziv (LZ) factorization based on the co-lexicographic order of the text's prefixes. The selected offsets tend to approach the k-th order empirical entropy. Our evaluations show that this choice is superior to the rightmost and bit-optimal LZ parsings on datasets with small high-order entropy.

Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation of some of these measures is NP-hard, and straight-forward computation is infeasible for datasets of even small sizes. Three such measures are the smallest size of a string attractor, the smallest size of a bidirectional macro scheme, and the smallest size of a straight-line program. While a vast variety of implementations for heuristically computing approximations exist, exact computation of these measures has received little to no attention. In this paper, we present MAX-SAT formulations that provide the first non-trivial implementations for exact computation of smallest string attractors, smallest bidirectional macro schemes, and smallest straight-line programs. Computational experiments show that our implementations work for texts of length up to a few hundred for straight-line programs and bidirectional macro schemes, and texts even over a million for string attractors.

Abstract Compact hash tables store a set S of n key-value pairs, where the keys are from the universe $$U = \{0,\ldots ,u-1\}$$ U = { 0 , … , u - 1 } , and the values are $$v$$ v -bit integers, in close to $${{\mathcal {B}}(u, n)} + nv$$ B ( u , n ) + n v bits of space, where $${{\mathcal {B}}(u, n)} = \log _2 {{u} \atopwithdelims (){n}}$$ B ( u , n ) = log 2 u n is the information-theoretic lower bound for representing the set of keys in S , and support operations insert, delete and lookup on S . Compact hash tables have received significant attention in recent years, and approaches dating back to Cleary [IEEE T. Comput, 1984], as well as more recent ones have been implemented and used in a number of applications. However, the wins on space usage of these approaches are outweighed by their slowness relative to conventional hash tables. In this paper, we demonstrate that compact hash tables based upon a simple idea of bucketing practically outperform existing compact hash table implementations in terms of memory usage and construction time, and existing fast hash table implementations in terms of memory usage (and sometimes also in terms of construction time), while having competitive query times. A related notion is that of a compact hash ID map , which stores a set $${\hat{S}}$$ S ^ of n keys from U , and implicitly associates each key in $${\hat{S}}$$ S ^ with a unique value (its ID), chosen by the data structure itself, which is an integer of magnitude O ( n ), and supports inserts and lookups on $${\hat{S}}$$ S ^ , while using space close to $${{\mathcal {B}}(u,n)}$$ B ( u , n ) bits. One of our approaches is suitable for use as a compact hash ID map.

Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ , a keyword dictionary is a data structure built on K that provides lookup, prefix search, and update operations on K . Under the assumption that α = w / lg ⁡ σ characters fit into a single machine word of w bits, we propose a keyword dictionary that represents K in either n lg ⁡ σ + Θ ( k lg ⁡ n ) or | T | lg ⁡ σ + Θ ( k w ) bits of space, where | T | is the number of nodes of a trie representing K . It supports all operations in O ( m / α + lg ⁡ α ) expected time on an input string of length m in the word RAM model. An evaluation of our implementation highlights the practical usefulness of the proposed data structure, especially for prefix searches — one of the most essential keyword dictionary operations.

As nowadays Machine Learning (ML) techniques are generating huge data collections, the problem of how to efficiently engineer their storage and operations is becoming of paramount importance. In this article we propose a new lossless compression scheme for real-valued matrices which achieves efficient performance in terms of compression ratio and time for linear-algebra operations. Experiments show that, as a compressor, our tool is clearly superior to gzip and it is usually within 20% of xz in terms of compression ratio. In addition, our compressed format supports matrix-vector multiplications in time and space proportional to the size of the compressed representation, unlike gzip and xz that require the full decompression of the compressed matrix. To our knowledge our lossless compressor is the first one achieving time and space complexities which match the theoretical limit expressed by the k -th order statistical entropy of the input. To achieve further time/space reductions, we propose column-reordering algorithms hinging on a novel column-similarity score. Our experiments on various data sets of ML matrices show that our column reordering can yield a further reduction of up to 16% in the peak memory usage during matrix-vector multiplication. Finally, we compare our proposal against the state-of-the-art Compressed Linear Algebra (CLA) approach showing that ours runs always at least twice faster (in a multi-thread setting), and achieves better compressed space occupancy and peak memory usage. This experimentally confirms the provably effective theoretical bounds we show for our compressed-matrix approach.

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. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture in the word RAM model by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n / lg lg n) time to linear. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.

Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database. Our code is available at https://github.com/koeppl/phoni.

One of the most well-known variants of the Burrows-Wheeler transform (BWT) [Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv 2012], which applies the extended BWT (EBWT) [Mantaci et al., TCS 2007] to the multiset of Lyndon factors of a given text. Since the EBWT is invertible, the BBWT is a bijective transform in the sense that the inverse image of the EBWT restores this multiset of Lyndon factors such that the original text can be obtained by sorting these factors in non-increasing order. In this paper, we present algorithms constructing or inverting the BBWT in-place using quadratic time. We also present conversions from the BBWT to the BWT, or vice versa, either (a) in-place using quadratic time, or (b) in the run-length compressed setting using $O(n \lg r / \lg \lg r)$ time with $O(r \lg n)$ bits of words, where $r$ is the sum of character runs in the BWT and the BBWT.

Re-Pair is a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large scale data sets. As a solution for this problem we present, given a text of length n whose characters are drawn from an integer alphabet, an O(n2) time algorithm computing Re-Pair in n lg max(n, τ) bits of working space including the text space, where τ is the number of terminals and non-terminals.

Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ, a keyword dictionary is a data structure built on K that provides locate, prefix search, and update operations on K. Under the assumption that α = w / lg σ characters fit into a single machine word w, we propose a keyword dictionary that represents K in n lg σ + Θ(k lg n) bits of space, supporting all operations in Θ(m / α + lg α) expected time on an input string of length m in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.

Compact hash tables store a set S of n key-value pairs, where the keys are from the universe U = {0,…,u-1}, and the values are v-bit integers, in close to B(u, n) + nv bits of space, where {b(u, n)} = log₂ binom(u,n) is the information-theoretic lower bound for representing the set of keys in S, and support operations insert, delete and lookup on S. Compact hash tables have received significant attention in recent years, and approaches dating back to Cleary [IEEE T. Comput, 1984], as well as more recent ones have been implemented and used in a number of applications. However, the wins on space usage of these approaches are outweighed by their slowness relative to conventional hash tables. In this paper, we demonstrate that compact hash tables based upon a simple idea of bucketing practically outperform existing compact hash table implementations in terms of memory usage and construction time, and existing fast hash table implementations in terms of memory usage (and sometimes also in terms of construction time). A related notion is that of a compact Hash ID map, which stores a set Ŝ of n keys from U, and implicitly associates each key in Ŝ with a unique value (its ID), chosen by the data structure itself, which is an integer of magnitude O(n), and supports inserts and lookups on Ŝ, while using close to B(u,n) bits. One of our approaches is suitable for use as a compact Hash ID map.

Given a text T of length n , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O( c √ lg n + m lg m lg n lg * n ) time with O( m ) words of space under the premise that the space of T is rewritable, where m ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m ≤ c ≤ n that must be compared for distinguishing the designated suffixes.

The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT is a bijective variant of it that has not yet been studied for text indexing applications. We fill this gap by proposing a self-index built on the bijective BWT . The self-index applies the backward search technique of the FM-index to find a pattern P with O(|P| lg|P|) backward search steps.

Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such an algorithm that is particularly suited for an external memory implementation. We evaluate it experimentally on large data sets of size up to 128 GiB (using only 16 GiB of RAM) and show that it is significantly faster than all known LZ77 compressors, while producing a roughly similar number of factors. We also introduce an external memory decompressor for texts compressed with any uni- or bidirectional compression scheme.

An α-gapped repeat (α ≥ 1) in a word w is a factor uvu of w such that |u v| ≤ α|u|; the two occurrences of u are called arms of this α-gapped repeat. An α-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18α n. In the case of α-gapped palindromes, i.e., factors $uv{{u}^{\intercal }}$ with |u v|≤ α|u|, we show that the number of all maximal α-gapped palindromes occurring in words of length n is upper bounded by 28α n + 7n. Both upper bounds allow us to construct algorithms finding all maximal α-gapped repeats and/or all maximal α-gapped palindromes of a word of length n on an integer alphabet of size $n^{\mathcal {O}(1)}$ in ${\mathcal {O}(\alpha n)}$ time. The presented running times are optimal since there are words that have Θ(α n) maximal α-gapped repeats/palindromes.

Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear to the string length. As an application, we show how to compute the tree topology of the minimal augmented suffix tree in linear time. Asides from that, we elaborate an algorithm computing the longest previous table in a succinct representation using compressed working space.

We present a framework facilitating the implementation and comparison of text compression algorithms. We evaluate its features by a case study on two novel compression algorithms based on the Lempel-Ziv compression schemes that perform well on highly repetitive texts.

We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with $p$ processors. Given a static text of length $n$, we first show how to compute the suffix array interval of a given pattern of length $m$ in $O(\frac{m}{p}+ \lg p + \lg\lg p\cdot\lg\lg n)$ time for $p \le m$. For approximate pattern matching with $k$ differences or mismatches, we show how to compute all occurrences of a given pattern in $O(\frac{m^kσ^k}{p}\max\left(k,\lg\lg n\right)\!+\!(1+\frac{m}{p}) \lg p\cdot \lg\lg n + \text{occ})$ time, where $σ$ is the size of the alphabet and $p \le σ^k m^k$. The workhorse of our algorithms is a data structure for merging suffix array intervals quickly: Given the suffix array intervals for two patterns $P$ and $P'$, we present a data structure for computing the interval of $PP'$ in $O(\lg\lg n)$ sequential time, or in $O(1+\lg_p\lg n)$ parallel time. All our data structures are of size $O(n)$ bits (in addition to the suffix array).

We show that both the Lempel-Ziv-77 and the Lempel-Ziv-78 factorization of a text of length n on an integer alphabet of size σ can be computed in O(n lg lg σ) time (linear time if we allow randomization) using O(n lg σ) bits of working space. Given that a compressed representation of the suffix tree is loaded into RAM, we can compute both factorizations in linear time using O(n) space.

For alpha >=1, an alpha-gapped repeat in a word w is a factor uvu of w such that |uv| <= alpha * |u|; the two occurrences of a factor u in such a repeat are called arms. Such a repeat is called maximal if its arms cannot be extended simultaneously with the same symbol to the right nor to the left. We show that the number of all maximal alpha-gapped repeats occurring in words of length n is upper bounded by 18 * alpha * n, allowing us to construct an algorithm finding all maximal alpha-gapped repeats of a word on an integer alphabet of size n^{O}(1)} in {O}(alpha * n) time. This result is optimal as there are words that have Theta(alpha * n) maximal alpha-gapped repeats. Our techniques can be extended to get comparable results in the case of alpha-gapped palindromes, i.e., factors uvu^{T} with |uv| <= alpha |u|.

Given a sequential input connection, we tackle parallel skyline computation of the read data by means of a spatial tree structure for indexing fine-grained feature vectors. For this purpose, multiple local split decision trees are simultaneously filled before the actual computation starts. We exploit the special tree structure to clip parts of the tree without depth-first search. The split of the data allows us to do this step in a divide and conquer manner. With this schedule we seek to provide an algorithm robust against the "dimension curse" and different data distributions.