LZ77 via Prefix-Free Parsing
Aaron P. Hong, Massimiliano Rossi, Christina Boucher · Society for Industrial and Applied Mathematics eBooks · 2023
In this paper, we present an algorithm for constructing the Lempel-Ziv 77 (LZ77) factorization using prefix-free parsing, an algorithm that was first developed as preprocessing algorithm for constructing the Burrows-Wheeler transform and the suffix array for input text. It was then demonstrated that the output of prefix-free parsing can be an effective data structure that emulates a compressed suffix tree (CST). PFP-LZ77 marries this data structure with the algorithm proposed by Karkkäinen et al. [CPM 2013]. In particular, we implemented a modification of the primitives used to support CST operations to enable previous smaller value and next smaller value queries on the suffix array of the text. This allow PFP-LZ77 to exploit the repetitiveness of the text, while building the LZ77 parse. We show that PFP-LZ77, SE-KKP, and ReLZ were the only methods capable of scaling to large datasets (e.g., 1024 copies of chromosome 19). And although SE-KKP and ReLZ performed well, SE-KKP was between 2.5 and 5 times slower, and used between 3 and 11 times more memory than PFP-LZ77 for reasonably large datasets (i.e., more than 16 copies of chromosome 19), and ReLZ only generates an LZ77 approximation. Our implementation is available at https://github.com/AaronHong1024/PFP_LZ77.