Prefix-free parsing
Prefix-free parsing splits a text into overlapping phrases whose dictionary and parse support construction of its Burrows-Wheeler transform.
Parsing: A rolling-hash trigger ends one phrase and starts the next with a shared window of w symbols. The dictionary stores distinct phrases; the parse records their lexicographic identifiers. In the 2019 formulation, phrase suffixes longer than w form a prefix-free set. This is not Huffman prefix coding. [1]
Construction: BWT workspace is bounded by the combined dictionary and parse sizes, not automatically by the final run count r. Window and trigger parameters affect both structures. The 2019 chromosome-19 experiment's 131 MB index supports counting only; a later sampling stage can dominate peak memory when locate support is added. [1]
Scaling: The 2025 PFP-merge preprint constructs subgroup BWTs and merges them. It targets groups with strong internal repetition but weaker similarity between groups. Its experiment trades lower peak memory for longer wall-clock time; the paper's filtered inputs and BWT/eBWT conventions matter when comparing tools. [2]
Use: Budget construction separately from the deployed index and specify count, locate and extraction requirements before comparing sizes. A small final index is not evidence that its builder fits the same memory budget. [1] [2]
Relations
Limitations
- Compression and construction costs depend on the input and parameters; the cited experiments are not a general memory guarantee for arbitrary collections. [1, 2]
Citations
- Boucher et al.: Prefix-free parsing for building big BWTs, Algorithms for Molecular Biology 14:13 (2019), theory and indexing sections
- Diaz-Dominguez et al.: Prefix-free parsing for merging big BWTs, arXiv:2506.03294v1 (2025), sections 2-4
Sources & caveats
- The 2019 journal article and explicitly versioned 2025 preprint are synthesized separately; no PFP benchmark was rerun by Hesela.
- No third-party paper text, figures, genomic data or implementation is redistributed.