prefix-free-parsing · research · also PFP

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

related
Prefix-free code, Burrows-Wheeler transform, r-index

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

  1. Boucher et al.: Prefix-free parsing for building big BWTs, Algorithms for Molecular Biology 14:13 (2019), theory and indexing sections (accessed 2026-11-17)
  2. Diaz-Dominguez et al.: Prefix-free parsing for merging big BWTs, arXiv:2506.03294v1 (2025), sections 2-4 (accessed 2026-11-17)
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.

JSON: /data/terms/prefix-free-parsing.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Prefix-free parsing. Hesela. 2026-11-17. https://hesela.dev/terms/prefix-free-parsing/