PFP Compressed Suffix Trees

Abstract

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string $S$, it produces a dictionary $D$ and a parse $P$ of overlapping phrases such that $\text{BWT}(S)$ can be computed from $D$ and $P$ in time and workspace bounded in terms of their combined size $|\text{PFP}(S)|$. In practice $D$ and $P$ are significantly smaller than $S$ and computing $\text{BWT}(S)$ from them is more efficient than computing it from $S$ directly, at least when $S$ is the concatenation of many genomes. In this paper, we consider $\text{PFP}(S)$ as a data structure and show how it can be augmented to support full suffix tree functionality, still built and fitting within $O(|\text{PFP}(S)|)$ space. This entails the efficient computation of various primitives to simulate the suffix tree: computing a longest common extension (LCE) of two positions in $S$; reading any cell of its suffix array (SA), of its inverse (ISA), of its BWT, and of its longest common prefix array (LCP); and computing minima over ranges and next/previous smaller value queries over the LCP. Our experimental results show that the PFP suffix tree can be efficiently constructed for very large repetitive datasets and that its operations perform competitively with other compressed suffix trees that can only handle much smaller datasets.