Word Break is a prototypical factorization problem in string processing: Given a word$w$of length$N$and a dictionary$\mathcal{D}=\{d_{1},\ d_{2},\ \ldots,\ d_{K}\}$of$K$strings, determine whether we can partition$w$into words from$\mathcal{D}$. We propose the first algorithm that solves the Word Break problem over the SLP-compressed input text$w$. Specifically, we show that, given the string$w$represented using an SLP of size$g$we can solve the Word Break problem in$\mathcal{O}(g\cdot m^{\omega}+M)$time, where$m=\max_{i=1}^{K}\vert d_{i}\vert M=\sum_{i=1}^{K}\vert d_{i}\vert$, and$\omega\geq 2$is the matrix multiplication exponent. We obtain our algorithm as a simple corollary of a more general result: We show that in$\mathcal{O}(g\cdot m^{\omega}+M)$time, we can index the input text$w$so that solving the Word Break problem for any of its substrings takes$\mathcal{O}(m^{2}\log N)$time (independent of the substring length). Our second contribution is a lower bound: We prove that, unless the Combinatorial$k$-Clique Conjecture fails, there is no combinatorial algorithm for Word Break on SLP-compressed strings running in$\mathcal{O}(g\cdot m^{2-\epsilon}+M)$time for any$\epsilon > 0$.

We present an algorithm that constructs the LZ-End parsing (a variation of LZ77) of a given string of length n in O(n log l) expected time and O(z + l) space, where z is the number of phrases in the parsing and l is the length of the longest phrase. As an option, we can fix l (e.g., to the size of RAM) thus obtaining a reasonable LZ-End approximation with the same functionality and the length of phrases restricted by l. This modified algorithm constructs the parsing in streaming fashion in one left to right pass on the input string w.h.p. and performs one right to left pass to verify the correctness of the result. Experimentally comparing this version to other LZ77-based analogs, we show that it is of practical interest.

The FM index (Ferragina & Manzini, J. ACM, 2005) is a widely-used compresseddata structure that stores a string T in a compressed form that also supports fast pattern matching queries. Fixed-block boosting is a relatively straightforward technique that achieves optimal index size in theory, but to date it is unclear how best to translate the method into practice. In this paper we describe several new techniques for implementing fixed-block boosting efficiently. The new indexes are consistently fast and small relative to the state-of-the-art, and thus make a good "off-the-shelf" choice for most applications.

In the 35 years since its discovery, the Lempel-Ziv factorization (or LZ77 parsing) has become a fundamental method for data compression and string processing. In many applications, computation of the factorization is a time-space bottleneck. However, and despite the increasing need to apply LZ77 to massive data sets (for both storage and indexing), no algorithm to date scales to inputs that exceed the size of RAM. In this paper we describe the first algorithms for computing the LZ77 parsing efficiently using external memory.

Compressed bit vectors supporting rank and select operations are the workhorse of compressed data structures. We propose a hybrid scheme for implementing compressed bit vectors, which divides the bit vector into blocks and then chooses the encoding of each block separately from a number of different encoding methods. Hybrid encoding is particularly suitable for bit vectors that have lots of local and regional variation, such as those present in the FM-index, a popular compressed data structure for pattern matching. We propose a specific hybrid combination of three simple encoding methods for FM-index bit vectors achieving superior space-time tradeoffs in experiments.

Inverting the Burrows-Wheeler transform (BWT) is a bottleneck in BWT-based decompressors. The state-of-the-art inversion algorithm runs in linear time but is slow in practice due to CPU-cache misses. For more than a decade these cache misses have been thought to be inherent to BWT inversion. We show how to reduce the number of cache misses by a factor of nearly two, and simultaneously the cost of cache misses by another factor of two, obtaining a consistent speed up by a factor of 2.3-4. We can do even better if the data is highly repetitive. We describe an algorithm that achieves an asymptotic reduction in cache misses in theory and is the fastest algorithm in practice for such data.