The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance? To address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected.

Given a string S over an alphabet Σ, the string indexing problem is to preprocess S to subsequently support efficient pattern matching queries, that is, given a pattern string P report all the occurrences of P in S. In this paper we study the streaming sliding window string indexing problem. Here the string S arrives as a stream, one character at a time, and the goal is to maintain an index of the last w characters, called the window, for a specified parameter w. At any point in time a pattern matching query for a pattern P may arrive, also streamed one character at a time, and all occurrences of P within the current window must be returned. The streaming sliding window string indexing problem naturally captures scenarios where we want to index the most recent data (i.e. the window) of a stream while supporting efficient pattern matching. Our main result is a simple O(w) space data structure that uses O(log w) time with high probability to process each character from both the input string S and any pattern string P. Reporting each occurrence of P uses additional constant time per reported occurrence. Compared to previous work in similar scenarios this result is the first to achieve an efficient worst-case time per character from the input stream with high probability. We also consider a delayed variant of the problem, where a query may be answered at any point within the next δ characters that arrive from either stream. We present an O(w + δ) space data structure for this problem that improves the above time bounds to O(log (w/δ)). In particular, for a delay of δ = ε w we obtain an O(w) space data structure with constant time processing per character. The key idea to achieve our result is a novel and simple hierarchical structure of suffix trees of independent interest, inspired by the classic log-structured merge trees.

The wavelet tree is a data structure that indexes a text over an integer alphabet for efficient rank and select queries. Using the Huffman encoding, it can be stored in zero-order entropycompressed space. We present a highly engineered open source implementation of an efficient sequential construction algorithm that makes use of bit parallelism via vector instructions. On hardware featuring ultrawide registers of up to 512 bits, it outperforms the currently fastest known practical sequential construction algorithms by a factor of up to 2.5.

Suffix sorting is arguably the most fundamental building block in string algorithmics, like regular sorting in the broader field of algorithms. It is thus not surprising that the literature is full of algorithms for suffix sorting, in particular focusing on their practicality. However, the advances on practical suffix sorting stalled with the emergence of the DivSufSort algorithm more than 10 years ago, which, up to date, has remained the fastest suffix sorter. This article shows how properties of Lyndon words can be exploited algorithmically to accelerate suffix sorting again. Our new algorithm is 6-19% faster than DivSufSort on real-world texts, and up to three times as fast on artificial repetitive texts. It can also be parallelized, where similar speedups can be observed. Thus, we make the first advances in practical suffix sorting after more than a decade of standstill.

A run in a string is a maximal periodic substring. For example, the string bananatree contains the runs anana = (an)^{5/2} and ee = e². There are less than n runs in any length-n string, and computing all runs for a string over a linearly-sortable alphabet takes 𝒪(n) time (Bannai et al., SIAM J. Comput. 2017). Kosolobov conjectured that there also exists a linear time runs algorithm for general ordered alphabets (Inf. Process. Lett. 2016). The conjecture was almost proven by Crochemore et al., who presented an 𝒪(nα(n)) time algorithm (where α(n) is the extremely slowly growing inverse Ackermann function). We show how to achieve 𝒪(n) time by exploiting combinatorial properties of the Lyndon array, thus proving Kosolobov’s conjecture. This also positively answers the at least 29-year-old question whether square-freeness can be tested in linear time over general ordered alphabets (Breslauer, PhD thesis, Columbia University 1992).

We present highly optimized data structures for the dynamic predecessor problem, where the task is to maintain a set $S$ of $w$-bit numbers under insertions, deletions, and predecessor queries (return the largest element in $S$ no larger than a given key). The problem of finding predecessors can be viewed as a generalized form of the membership problem, or as a simple version of the nearest neighbour problem. It lies at the core of various real-world problems such as internet routing. In this work, we engineer (1) a simple implementation of the idea of universe reduction, similar to van-Emde-Boas trees (2) variants of y-fast tries [Willard, IPL'83], and (3) B-trees with different strategies for organizing the keys contained in the nodes, including an implementation of dynamic fusion nodes [Pǎtraşcu and Thorup, FOCS'14]. We implement our data structures for $w=32,40,64$, which covers most typical scenarios. Our data structures finish workloads faster than previous approaches while being significantly more space-efficient, e.g., they clearly outperform standard implementations of the STL by finishing up to four times as fast using less than a third of the memory. Our tests also provide more general insights on data structure design, such as how small sets should be stored and handled and if and when new CPU instructions such as advanced vector extensions pay off.

The wavelet tree (Grossi et al. [SODA, 2003]) is a compact index for texts that provides rank, select, and access operations. This leads to many applications in text indexing, computational geometry, and compression. We present the first distributed memory wavelet tree construction algorithms, which allow us to process inputs that are orders of magnitude larger than what current shared memory construction algorithms can work with. In addition, our algorithms can easily be adapted to compute the wavelet matrix (Claude et al. [Inf. Syst., 47:15–32,2015]), an alternative representation of the wavelet tree. In practice, one of our distributed memory wavelet matrix construction algorithms is the first parallel algorithm that can compute the wavelet matrix for alphabets of arbitrary size.

For a text T[1,n], a Longest Common Extension (LCE) query lce_T(i,j) asks for the length of the longest common prefix of the suffixes T[i,n] and T[j,n] identified by their starting positions 1 ≤ i,j ≤ n. A classic problem in stringology asks to preprocess a static text T[1,n] over an alphabet of size σ so that LCE queries can be efficiently answered on-line. Since its introduction in the 1980’s, this problem has found numerous applications: in suffix sorting, edit distance computation, approximate pattern matching, regularities finding, string mining, and many more. Text-book solutions offer O(n) preprocessing time and O(1) query time, but they employ memory-heavy data structures, such as suffix arrays, in practice several times bigger than the text itself. Very recently, more space efficient solutions using O(nlogσ) bits of total space or even only O(log n) bits of extra space have been proposed: string synchronizing sets [Kempa and Kociumaka, STOC'19, and Birenzwige et al., SODA'20] and in-place fingerprinting [Prezza, SODA'18]. The goal of this article is to present well-engineered implementations of these new solutions and study their practicality on a commonly agreed text corpus. We show that both perform extremely well in practice, with space consumption of only around 10% of the input size for string synchronizing sets (around 20% for highly repetitive texts), and essentially no extra space for fingerprinting. Interestingly, our experiments also show that both solutions become much faster than naive scanning even for finding common prefixes of moderate length, contradicting a common belief that sophisticated data structures for LCE queries are not competitive with naive approaches [Ilie and Tinta, SPIRE'09].

Given a string S of length n, its Lyndon array identifies for each suffix S[i..n] the next lexicographically smaller suffix S[j..n], i.e. the minimal index j > i with S[i..n] ≻ S[j..n]. Apart from its plain (n log₂ n)-bit array representation, the Lyndon array can also be encoded as a succinct parentheses sequence that requires only 2n bits of space. While linear time construction algorithms for both representations exist, it has previously been unknown if the same time bound can be achieved with less than Ω(n lg n) bits of additional working space. We show that, in fact, o(n) additional bits are sufficient to compute the succinct 2n-bit version of the Lyndon array in linear time. For the plain (n log₂ n)-bit version, we only need 𝒪(1) additional words to achieve linear time. Our space efficient construction algorithm makes the Lyndon array more accessible as a fundamental data structure in applications like full-text indexing.

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.

We present two new distributed suffix array construction algorithms. One of our algorithms requires only half as much memory as its competitor (PSAC) [Flick & Aluru, SC 2015], while achieving similar speed. In practice, we can compute on the same hardware suffix arrays for text twice as large as PSAC. The other algorithm still requires less memory than PSAC but is faster on some instances. As a by-product, we also engineered the first distributed string sorting algorithm. All of our algorithms are tested on text collections of up to 115 GB and running on 1280 cores.

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.

The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 47:15–32, 2015]) are compact indices for texts over an alphabet [0, σ) that support rank, select and access queries in O(lg σ) time. We first present new practical sequential and parallel algorithms for wavelet tree construction. Their unifying characteristics is that they construct the wavelet tree bottom-up, i.e., they compute the last level first. We also show that this bottom-up construction can easily be adapted to wavelet matrices. In practice, our best sequential algorithm is up to twice as fast as the currently fastest sequential wavelet tree construction algorithm (Shun [DCC, 2015]), simultaneously saving a factor of 2 in space. This scales up to 32 cores, where we are about equally fast as the currently fastest parallel wavelet tree construction algorithm (Labeit et al. [DCC, 2016]), but still use only about 75% of the space. An additional theoretical result shows how to adapt any wavelet tree construction algorithm to the wavelet matrix in the same (asymptotic) time, using only little extra space.

We present a distributed full-text index for big data applications in a distributed environment. Our index can answer different types of pattern matching queries (existential, counting and enumeration). We perform experiments on inputs up to 100 GiB using up to 512 processors, and compare our index with the distributed suffix array by Arroyuelo et al. [Parall. Comput. 40(9): 471–495, 2014]. The result is that our index answers counting queries up to 5:5 times faster than the distributed suffix array, while using about the same space. We also provide a succinct variant of our index that uses only one third of the memory compared with our non-succinct variant, at the expense of only 20% slower query times.

We present new algorithms for the sliding window Lempel-Ziv (LZ77) problem and the approximate rightmost LZ77 parsing problem. Our main result is a new and surprisingly simple algorithm that computes the sliding window LZ77 parse in O(w) space and either O(n) expected time or O(n log log w+z log log s) deterministic time. Here, w is the window size, n is the size of the input string, z is the number of phrases in the parse, and s is the size of the alphabet. This matches the space and time bounds of previous results while removing constant size restrictions on the alphabet size. To achieve our result, we combine a simple modification and augmentation of the suffix tree with periodicity properties of sliding windows. We also apply this new technique to obtain an algorithm for the approximate rightmost LZ77 problem that uses O(n(log z + log log n)) time and O(n) space and produces a (1+e)-approximation of the rightmost parsing (any constant e>0). While this does not improve the best known time-space trade-offs for exact rightmost parsing, our algorithm is significantly simpler and exposes a direct connection between sliding window parsing and the approximate rightmost matching problem.

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).

In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O ( b ) words of space during the construction. Attempts at breaking the naïve bound of Ω( nb ) time for constructing sparse suffix trees in O ( b ) space can be traced back to the origins of string indexing in 1968. First results were not obtained until 1996, but only for the case in which the b suffixes were evenly spaced in T . In this article, there is no constraint on the locations of the suffixes. Our main contribution is to show that the sparse suffix tree (and array) can be constructed in O ( n log 2 b ) time. To achieve this, we develop a technique that allows one to efficiently answer b longest common prefix queries on suffixes of T , using only O ( b ) space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Our first solution is Monte Carlo, and outputs the correct tree with high probability. We then give a Las Vegas algorithm, which also uses O ( b ) space and runs in the same time bounds with high probability when b = O (√ n). Additional trade-offs between space usage and construction time for the Monte Carlo algorithm are given. Finally, we show that, at the expense of slower pattern queries, it is possible to construct sparse position heaps in O ( n + b log b ) time and O ( b ) space.

We show how to compress string dictionaries using Lempel-Ziv (LZ78) data compression. Our approach is validated experimentally on dictionaries of up to 1.5 GB of uncompressed text. We achieve compression ratios often outperforming the existing alternatives, especially on dictionaries containing many repeated substrings. Our query times remain competitive.

We consider text index construction in external memory (EM). Our first contribution is an inducing algorithm for suffix arrays in external memory. Practical tests show that this outperforms the previous best EM suffix sorter [Dementiev et al., ALENEX 2005] by a factor of about two in time and I/O-volume. Our second contribution is to augment the first algorithm to also construct the array of longest common prefixes (LCPs). This yields the first EM construction algorithm for LCP arrays. The overhead in time and I/O volume for this extended algorithm over plain suffix array construction is roughly two. Our algorithms scale far beyond problem sizes previously considered in the literature (text size of 80 GiB using only 4 GiB of RAM in our experiments).

Given a static array of n totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form “what is the position of a minimum element in the subarray ranging from i to j?”. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size $\frac{2n}{c(n)}-\Theta\bigl(\frac{n\lg\lg n}{c(n)\lg n}\bigr)$ bits and query time $O(c(n))$ for any positive integer function $c(n)\in O\bigl(n^\varepsilon\bigr)$ for an arbitrary constant $0<\varepsilon<1$, or (b) with $O(nH_k)+o(n)$ bits and $O(1)$ query time, where $H_k$ denotes the empirical entropy of kth order of the input array. In setting (2), we give a data structure of size $2n+o(n)$ bits and query time $O(1)$. All data structures can be constructed in linear time and almost in-place.

We propose new data structures for navigation in sequences of balanced parentheses, a standard tool for representing compressed trees. The most striking property of our approach is that it shares most of its internal data structures for all operations. This is reflected in a large reduction of space, and also in faster navigation times. We exhibit these advantages on two examples: succinct range minimum queries and compressed suffix trees. Our data structures are incorporated into a ready-to-use C++-library for succinct data structures.

The Range Minimum Query (RMQ) Problem is to preprocess an array A of length n in 0(n) time such that subsequent on-line queries asking for the position of a minimal element between two specified indices can be obtained in constant time. Several solutions to this problem have been proposed, starting with Berkman and Vishkin's linear-space solution [6], and leading to a succinct solution using only 2n + o(n) bits in addition to the input array [12]. The theoretical contribution of this article is to push this latter approach one step further and show that for compressible input arrays the RMQ-information can be compressed as well. In particular, we show that information for 0(l)-RMQs can be stored within the same entropy bounds that are achieved by the currently best schemes for storing A itself in compressed form, while still being able to access O(logn) contiguous bits in O(l) time [10]. Two such entropy- bounded schemes for 0(l)-RMQs are developed, each with its own practical advantage. We test these two methods extensively and compare them to three other schemes for RMQs: the currently best non-succinct solution [2], and two succinct approaches: Sadakane's 4n + o(n)-bit solution [22], and our own 2n + o(n)-bit solution. The results of this practical evaluation are (1) the practical space consumptions of the non-compressed schemes scale surprisingly well with their theoretical guarantees, and (2) for compressible input arrays our new compressed schemes can indeed reduce the space, with little or no slowdown in query time.

Let $\db_1$ and $\db_2$ be two databases (i.e. multisets) of $d$ strings, over an alphabet $\Sigma$, with overall length $n$. We study the problem of mining discriminative patterns between $\db_1$ and $\db_2$ --- e.g., patterns that are frequent in one database but not in the other, emerging patterns, or patterns satisfying other frequency-related constraints. Using the algorithmic framework by Hui (CPM 1992), one can solve several variants of this problem in the optimal linear time with the aid of suffix trees or suffix arrays. This stands in high contrast to other pattern domains such as itemsets or subgraphs, where super-linear lower bounds are known. However, the space requirement of existing solutions is $O(n \log n)$ bits, which is not optimal for $|\Sigma

MOTIVATION: An important quantity that arises in NMR spectroscopy experiments is the chemical shift. The interpretation of these data is mostly done by human experts; to our knowledge there are no algorithms that predict protein structure from chemical shift sequences alone. One approach to facilitate this process could be to compare two such sequences, where the structure of one protein has already been resolved. Our claim is that similarity of chemical shifts thereby found implies structural similarity of the respective proteins. RESULTS: We present an algorithm to identify structural similarities of proteins by aligning their associated chemical shift sequences. To evaluate the correctness of our predictions, we propose a benchmark set of protein pairs that have high structural similarity, but low sequence similarity (because with high sequence similarity the structural similarities could easily be detected by a sequence alignment algorithm). We compare our results with those of HHsearch and SSEA and show that our method outperforms both in >50% of all cases.

We present a method to mine strings that are frequent in one database and infrequent in another. The method uses suffix- and lcp-arrays that can be computed extremely fast and space efficiently, and further exhibit a good locality behavior. Experiments with several biologically relevant data sets show that our approach outperforms existing methods in terms of time and space.