Prefix-free parsing for merging big BWTs

Ben Langmead; Diego Diaz-Dominguez; Francesco Masillo; Giovanni Manzini; Travis Gagie; Veronica Guerrini; Vikram Shivakumar; Zsuzsanna Liptak

REVIEW 3 major objections 4 minor 26 references

Prefix-free parsing for merging big BWTs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that building and merging BWTs of small, mutually dissimilar subdatasets lets prefix-free parsing index huge collections in a fraction of the memory, with a 9.39 GB bacterial collection handled in under a gigabyte.

desk verdict The merge algorithm in §3 is incorrect as written: the BWT interleaves characters from different phrases that share a suffix, so per-phrase block copies don't produce the right order. read the letter →

arxiv 2506.03294 v2 pith:WLQWGTK6 submitted 2025-06-03 cs.DS

Diego Diaz-Dominguez , Travis Gagie , Veronica Guerrini , Ben Langmead , Zsuzsanna Liptak , Giovanni Manzini , Francesco Masillo , Vikram Shivakumar This is my paper

classification cs.DS

keywords Burrows-WheelerTransformprefix-freeparsingBWTmerginglow-memoryalgorithmspangenomicsrepetitivetextindexingextended

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a memory-saving way to build the Burrows-Wheeler Transform (BWT) of a very large dataset that can be split into small, mutually dissimilar pieces, such as genomes grouped by species or by chromosome. Instead of parsing the entire dataset at once, the method builds the BWT of each small piece and then merges those BWTs into the BWT of the whole dataset. This avoids storing a single huge parse and dictionary, which is what makes plain PFP memory-hungry on terabyte-scale pangenomes. The authors demonstrate the approach on 9.39 GB of bacterial genomes, where their tool peaked at 0.91 GB, compared with 13.84 GB for standard PFP and 1.71 GB for the next-best tested tool.

What carries the argument

The load-bearing object is the valid phrase suffix: in a prefix-free parse, phrases start and end with trigger strings of length w, and any proper phrase suffix of length at least w is valid. PFP's correctness rests on the fact that no valid phrase suffix is a proper prefix of another, so the lexicographic order of valid phrase suffixes determines the BWT order of the characters that precede them. The merging algorithm scans these suffixes, looks up the phrase ending at each suffix, its total occurrence count, and the small dataset that owns it, then copies that many characters from the corresponding small BWT into the output. Supporting tables and streaming of the small dictionaries' suffix arrays keep the memory footprint down.

What would settle it

Run pfp-merge on a dataset whose pieces share many w-length substrings, such as genomes of the same species split across pieces: if a substantial fraction of valid phrase suffixes appear in more than one small dictionary, the output BWT will be wrong or peak memory will approach plain PFP. A direct check is to count, for a proposed split with w=20, how many valid phrase suffixes occur in more than one small dataset; if that count is not near zero, the central claim fails for that split.

Watch

Extended reading notes

Core claim

The central discovery is that the piecewise BWTs can be merged by scanning valid phrase suffixes in lexicographic order, rather than by aligning the pieces. After removing trigger strings that appear in more than one small dataset, every valid phrase suffix appears in exactly one small dataset, so the characters preceding that suffix in the whole BWT are all in one small BWT and keep their relative order. A single pass over the suffix array of the concatenated dictionaries, copying blocks of characters equal to each phrase's occurrence count from the appropriate small BWT, therefore produces the BWT of the whole dataset. This bypasses the large parse and dictionary that plain PFP would need for the entire collection.

Load-bearing premise

The dataset can be split into small pieces that are almost mutually dissimilar, so that nearly every w-length substring occurs in only one piece; otherwise the merge cannot assign each valid phrase suffix to exactly one small BWT and the memory benefit collapses.

Editorial extensions

If this is right

Collections of genomes grouped by species or chromosome can be indexed with PFP in memory close to the size of one group's dictionary rather than the whole collection's parse.
The memory during the final merge is dominated by the suffix array of the concatenated dictionaries, which can be streamed from disk, so datasets beyond the reach of plain PFP become tractable.
The algorithm can be parallelized by starting each small suffix array at an interior position, sharing the static dictionaries and tables across threads without proportionally increasing memory.
When queries only involve {A,C,G,T}, storing dictionaries in 3 bits per character keeps phrase-suffix comparisons fast, making the approach practical at scale.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The reported 0.77 GB used by the merging phase itself suggests the memory advantage will grow with the number of groups: adding pieces adds tables, not another full-size parse.
The merge could be combined with other BWT construction algorithms for the small pieces, potentially inheriting their speed while keeping the lower memory of this approach.
The same unique-phrase-suffix idea could extend to other parse-based indexes, such as r-index-style structures or Wheeler graphs, making piecewise construction a general pattern for repetitive pangenomes.
A practical deployment would need an automatic way to find a valid decomposition and to verify that w=20 is sufficient; without that, the approach remains heuristic.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear Colleague,

You should know that the merge algorithm in §3, Figure 2, is not correct as written. The proof assumes that for a phrase β ending with a valid phrase suffix α, the occ(β) characters preceding α in the small dataset's BWT form a contiguous block. They don't. The BWT orders all characters preceding α by the suffix that follows α—which is the suffix starting after the phrase—and occurrences of β are interleaved with those of other phrases that also end with α. The counterexample in the stress-test note is sound: with text CACBCAC, w=1, trigger C, the code fragment produces a 6-character string instead of the true 8-character BWT. So the central claim—that you can merge small BWTs by copying per-phrase blocks—is not established.

That's a shame because the paper starts from a real pain point: PFP's memory blows up on AllTheBacteria and the 231-genome HPRC. The idea of decomposing the dataset into pieces that share few w-mers, building their BWTs, and merging them is natural and potentially useful. The engineering details are nice too: the 3-bit dictionary encoding, the streaming suffix-array merge, the min-heap note. The paper is clearly written, and the code is public.

But the flaws are load-bearing. The per-phrase block copy is wrong. The similarity condition is heuristic—'most w-mers appear in only one small dataset'—and w=20 is asserted without support. There is one experiment, no repeated runs, and no output validation; the reported memory numbers are interesting but not meaningful evidence for an algorithm that is described incorrectly. The method is also slower than grlBWT and bigbwt, so the only selling point is the low memory peak.

What might work: if the merge step copies whole α-blocks from the appropriate small BWT (since each α appears in only one small dataset), then the order within the block is already correct. That would require a different code fragment and a different proof. The authors may have done something like that in the implementation; the paper should say.

My take: the idea is worth pursuing, but this version isn't ready. The authors need to fix the correctness argument (or the algorithm), add a real validation of the output, and specify what the similarity condition requires. I'd send it to review, because a serious referee could push them in the right direction, but I wouldn't accept it as is.

Best regards.

Referee Report

3 major / 4 minor

Summary. The paper proposes a memory-reduction strategy for building the BWT of very large repetitive datasets with prefix-free parsing (PFP). The idea is to split the dataset into smaller, mutually dissimilar datasets, build a BWT for each small dataset with PFP, and then merge these BWTs into the BWT of the whole dataset. The merge is described in Section 3 through a code fragment (Figure 2) that copies, for each valid phrase suffix, a block of characters from the appropriate small dataset's BWT. The paper reports a single experiment on 9.39 GB of bacterial pangenomes, where pfp-merge peaks at 0.91 GB, far below plain PFP (bigbwt, 13.84 GB) and competitive with grlBWT (1.71 GB). The central correctness claim is that, under a heuristic condition that most w-mers appear in only one small dataset, each valid phrase suffix appears in exactly one small dataset, so copying the corresponding BWT characters yields the whole BWT.

Significance. If the merge procedure were correct, the paper would describe a practically attractive way to extend PFP's low-memory construction to datasets that are not repetitive enough for recursive PFP. The experimental result is striking: a 15x reduction in peak memory compared with plain PFP on a real 9.39 GB collection. The paper is also clearly written and makes its code and data available. These strengths are real, and the proposed direction of building small BWTs and merging them is worth pursuing. However, the correctness of the central algorithm is not established, and there is a concrete failure mode even under the paper's own 'not very similar' assumption. Because the contribution is the merge algorithm itself, this flaw is load-bearing.

major comments (3)

[§3, Figure 2] The proof of correctness for the merge loop counts characters but never proves that the occ(SAD[i]) characters belonging to a given phrase are contiguous in oldBWT[DS(SAD[i])]. In a BWT/eBWT, the characters preceding the same valid phrase suffix α are ordered by the suffix following α; for occurrences at the end of a phrase, that suffix includes the following phrase, not the phrase identity. Two phrases ending with the same α can therefore interleave their occurrences in oldBWT, and the fread of occ(SAD[i]) characters copies the wrong context. A concrete failure occurs on text CACBCAC with w=1 and trigger string C: the phrases CAC and CBC share the valid suffix C, yet Figure 2, applied to the BWT of that single dataset, produces a string of length 6 instead of the true BWT of length 8. Thus the central claim of Section 3 is not established even under the ideal assumption that every valid phrase suffix appears in exactly one small dataset.
[§3, 'not very similar' condition] The decomposition condition is informal: no algorithm or validation test is given for checking that most w-mers appear in only one small dataset, and the statement that w=20 is 'usually enough' is anecdotal. More importantly, the condition as stated is insufficient: the counterexample above satisfies the condition (the only valid suffix C appears in exactly one small dataset), yet the merge loop is still incorrect. A revised paper would need to either prove a formal condition under which the per-phrase blocks in oldBWT are contiguous, or replace the extraction step with a correct procedure that uses, for example, suffix-array intervals and rank/select operations.
[§4, Table 1] The experimental section reports peak memory and time on a single 9.39 GB collection, but does not report any verification that the BWT produced by pfp-merge is identical to the BWT of the whole dataset. Given the flaw in Figure 2, the experiment cannot currently be interpreted as evidence for correctness of the merging procedure. At minimum, the paper would need a differential test against bigbwt on the same input, and ideally on multiple datasets with varying degrees of similarity, together with a precise description of what the implementation actually does if it differs from Figure 2.

minor comments (4)

[§4] The text refers to 'Masillo's CMT-BWT' in the experiments, while Section 1 calls it 'CMS-BWT'; the tool name should be reconciled.
[Table 1] The table uses 'glrbwt' while the text and repository name use 'grlbwt' (or 'grlBWT'); the spelling should be unified.
[Abstract] The abstract has formatting issues in the PDF text, including missing spaces such as 'Whenbuilding'; this should be corrected in the camera-ready version.
[§3, streaming SAD] The claim that storing dictionaries instead of SAD reduces space 'by about 4 or 8' depends on the suffix-array entry size and the dictionary encoding; the statement should be qualified more precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: pfp-merge builds on prior PFP machinery and is evaluated against external tools, with no fitted quantity relabeled as a prediction.

full rationale

The claimed contribution is a construction: if a dataset splits into small datasets whose w-mers are mostly disjoint, the paper builds each small dataset's BWT independently and merges them using the dictionary suffix array (Section 3, Fig. 2). The target whole-dataset BWT is never an input to the construction; the merge reads only the small datasets' BWTs, phrase occurrence counts, and dictionary order. Correctness is argued from PFP invariants about valid phrase suffixes being prefix-free and confined to one small dataset, not by assuming the output. No parameter is fitted to the target BWT and then reported as a prediction: Table 1 compares measured peak memory against external implementations bigbwt, grlBWT, ropebwt3 and lg. The citations to Boucher et al. [5,6] and the 2018 arXiv note [11] are ordinary references to the prior PFP method the paper extends, not a self-citation chain that forces the conclusion; the merge step is a new combination of known pieces. The \u201cw=20 is usually enough\u201d heuristic and the \u201cnot very similar\u201d assumption are unvalidated modeling assumptions, hence correctness risks, not circularity. The derivation chain is self-contained modulo the cited PFP foundation, so no circular step is present.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No invented entities. The free parameters are PFP's own tuning knobs. The axioms are PFP theory plus the paper's similarity-condition assumption, and the latter is the least validated input.

free parameters (2)

PFP window length w = 20 in experiments
Chosen by hand as 'usually enough' in Section 3; it determines which w-mers are shared across small datasets and whether valid phrase suffixes are unique to one small dataset.
PFP modulus p = default program setting, not stated
Controls trigger density and dictionary size; default parameter settings were used in all experiments, with no sensitivity analysis reported.

assumptions (4)

standard math PFP phrase properties: every phrase starts and ends with a trigger string, and every valid phrase suffix begins with the phrase-ending trigger.
Section 2 restates these as established PFP facts; the merge proof depends on them.
domain assumption The dataset can be partitioned into small datasets that are not very similar, i.e., most w-mers appear in only one small dataset.
Section 3 asserts this condition; without it, removing shared triggers may leave no usable phrase suffixes and the merge cannot be done efficiently or correctly.
domain assumption For a fixed valid phrase suffix, the order of preceding characters in the whole eBWT is the same as in the containing small dataset's eBWT.
Used in Section 3 to justify copying blocks from oldBWT[DS(SAD[i])] in Figure 2.
standard math Replacing non-ACGT characters by X preserves the multiset of ACGT substrings.
Section 3 uses this for 3-bit dictionary encoding in the experiments.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Prefix-free parsing for merging big BWTs." pith.science (2026). https://pith.science/paper/WLQWGTK6

@misc{pith2026250603294,
  author       = {Pith},
  title        = {Pith review of: Prefix-free parsing for merging big BWTs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WLQWGTK6}},
  note         = {Machine review of arXiv:2506.03294}
}

read the original abstract

When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset can be broken down into small datasets that are not very similar to each other -- such as collections of many copies of genomes of each of several species, or collections of many copies of each of the human chromosomes -- then we can drastically reduce PFP's memory footprint by building the BWTs of the small datasets and then merging them into the BWT of the whole dataset.

Figures

Figures reproduced from arXiv: 2506.03294 by the authors.

**Figure 1.** A code fragment for filling in the characters in the BWT that precede in the dataset valid phrase suffixes always preceded by the same distinct character. By itself, this usually fills in most of the BWT. To compare valid phrase suffixes quickly, we can build the suffix array SAD of the concatenation dict of the phrases in the dictionary. In fact, if – dSize is the number of characters in dict, – valid(SAD[i]) indic… view at source ↗

**Figure 2.** A code fragment that merges the BWTs of the small datasets into the BWT of the whole dataset. 3 Merging Suppose we have a dataset that can be broken down into small datasets that are not very similar to each other, in the sense that most w-mers that appear in the whole dataset appear in only one of the small datasets. (In our experiments, we found setting w = 20 is usually enough.) We find the set of trigger strings… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

iScience 24(6) (2021)

Ahmed,O.,Rossi,M.,Kovaka,S.,Schatz,M.C.,Gagie,T.,Boucher,C.,Langmead, B.: Pan-genomic matching statistics for targeted nanopore sequencing. iScience 24(6) (2021)

work page 2021
[2]

Genome Biology24(1), 122 (2023)

Ahmed, O.Y., Rossi, M., Gagie, T., Boucher, C., Langmead, B.: SPUMONI 2: improved classification using a pangenome index of minimizer digests. Genome Biology24(1), 122 (2023)

work page 2023
[3]

In: Proc

Boucher, C., Cenzato, D., Lipták, Z., Rossi, M., Sciortino, M.: Computing the original eBWT faster, simpler, and with less memory. In: Proc. 28th Symposium on String Processing and Information Retrieval (SPIRE). pp. 129–142 (2021)

work page 2021
[4]

In: Proc

Boucher, C., Cvacho, O., Gagie, T., Holub, J., Manzini, G., Navarro, G., Rossi, M.: PFP compressed suffix trees. In: Proc. 23rd Workshop on Algorithm Engineering and Experiments (ALENEX). pp. 60–72 (2021)

work page 2021
[5]

Algorithms for Molecular Biology14, 1–15 (2019)

Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix- free parsing for building big BWTs. Algorithms for Molecular Biology14, 1–15 (2019)

work page 2019
[6]

In: Proc

Boucher, C., Gagie, T., Kuhnle, A., Manzini, G.: Prefix-free parsing for building big BWTs. In: Proc. 18th Workshop on Algorithms in Bioinformatics (WABI). pp. 2:1–2:16 (2018)

work page 2018
[7]

Information and Computation294, 105088 (2023)

Díaz-Domínguez, D., Navarro, G.: Efficient construction of the BWT for repetitive text using string compression. Information and Computation294, 105088 (2023)

work page 2023
[8]

Algorithmica63(3), 707–730 (2012)

Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica63(3), 707–730 (2012)

work page 2012

Show all 26 references

[9]

iScience27(10) (2024)

Ferro, E., Oliva, M., Gagie, T., Boucher, C.: Building a pangenome alignment index via recursive prefix-free parsing. iScience27(10) (2024)

2024
[10]

In: Proc

Gagie, T., I, T., Manzini, G., Navarro, G., Sakamoto, H., Takabatake, Y.: Rpair: rescaling RePair with rsync. In: Proc. 26th Symposium on String Processing and Information Retrieval (SPIRE). pp. 35–44. Springer (2019)

2019
[11]

arxiv (2018)

Gagie, T., Manzini, G.: Prefix-free parsing for building big BWTs. arxiv (2018)

2018
[12]

In: Proc

Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. In: Proc. 29th Symposium on Discrete Algorithms (SODA). pp. 1459–1477 (2018)

2018
[13]

Journal of the ACM67(1), 1–54 (2020)

Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Journal of the ACM67(1), 1–54 (2020)

2020
[14]

In: Proc

Goga,A.,Baláž,A.:Prefix-freeparsingforbuildinglargetunnelledWheelergraphs. In: Proc. 22nd Workshop on Algorithms in Bioinformatics (WABI 2022). pp. 18–1 (2022)

2022
[15]

In: Proc

Hong, A., Rossi, M., Boucher, C.: LZ77 via prefix-free parsing. In: Proc. 25th Symposium on Algorithm Engineering and Experiments (ALENEX). pp. 123–134 (2023) 8 D. Díaz-Domínguez et al

2023
[16]

Hunt, M., Lima, L., Anderson, D., Hawkey, J., Shen, W., Lees, J., Iqbal, Z.: AllThe- Bacteria-allbacterialgenomesassembled,availableandsearchable.bioRxiv(2024)

2024
[17]

In: Proc

Kim, J., Varki, R., Oliva, M., Boucher, C.: Re2pair: Increasing the scalability of RePair by decreasing memory usage. In: Proc. 32nd European Symposium on Algorithms (ESA). pp. 78–1 (2024)

2024
[18]

Bioinformatics40(12), btae717 (2024)

Li, H.: BWT construction and search at the terabase scale. Bioinformatics40(12), btae717 (2024)

2024
[19]

Lipták,Z.,Lucà,S.,Masillo,F.:MeasuringgenomicdatawithPFP.bioRxiv(2025)

2025
[20]

Cambridge Uni- versity Press, 2nd edn

Mäkinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-scale algorithm design: bioinformatics in the era of high-throughput sequencing. Cambridge Uni- versity Press, 2nd edn. (2023)

2023
[21]

Theoretical Computer Science387(3), 298–312 (2007)

Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows– Wheeler transform. Theoretical Computer Science387(3), 298–312 (2007)

2007
[22]

In: Proc

Masillo, F.: Matching statistics speed up BWT construction. In: Proc. 31st Euro- pean Symposium on Algorithms (ESA). pp. 83–1 (2023)

2023
[23]

arXiv (2025)

Olbrich, J.: Fast and memory-efficient BWT construction of repetitive texts using lyndon grammars. arXiv (2025)

2025
[24]

Bioinformatics41(3), btaf104 (2025)

Olbrich,J.,Büchler,T.,Ohlebusch,E.:Generatingmultiplealignmentsonapange- nomic scale. Bioinformatics41(3), btaf104 (2025)

2025
[25]

Journal of Computational Biology29(2), 169–187 (2022)

Rossi, M., Oliva, M., Langmead, B., Gagie, T., Boucher, C.: MONI: a pangenomic index for finding maximal exact matches. Journal of Computational Biology29(2), 169–187 (2022)

2022
[26]

Tridgell, A., Mackerras, P.: The rsync algorithm. Tech. Rep. TR-CS-96-05, The Australian National University (1996)

1996

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

iScience 24(6) (2021)

Ahmed,O.,Rossi,M.,Kovaka,S.,Schatz,M.C.,Gagie,T.,Boucher,C.,Langmead, B.: Pan-genomic matching statistics for targeted nanopore sequencing. iScience 24(6) (2021)

work page 2021

[2] [2]

Genome Biology24(1), 122 (2023)

Ahmed, O.Y., Rossi, M., Gagie, T., Boucher, C., Langmead, B.: SPUMONI 2: improved classification using a pangenome index of minimizer digests. Genome Biology24(1), 122 (2023)

work page 2023

[3] [3]

In: Proc

Boucher, C., Cenzato, D., Lipták, Z., Rossi, M., Sciortino, M.: Computing the original eBWT faster, simpler, and with less memory. In: Proc. 28th Symposium on String Processing and Information Retrieval (SPIRE). pp. 129–142 (2021)

work page 2021

[4] [4]

In: Proc

Boucher, C., Cvacho, O., Gagie, T., Holub, J., Manzini, G., Navarro, G., Rossi, M.: PFP compressed suffix trees. In: Proc. 23rd Workshop on Algorithm Engineering and Experiments (ALENEX). pp. 60–72 (2021)

work page 2021

[5] [5]

Algorithms for Molecular Biology14, 1–15 (2019)

Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix- free parsing for building big BWTs. Algorithms for Molecular Biology14, 1–15 (2019)

work page 2019

[6] [6]

In: Proc

Boucher, C., Gagie, T., Kuhnle, A., Manzini, G.: Prefix-free parsing for building big BWTs. In: Proc. 18th Workshop on Algorithms in Bioinformatics (WABI). pp. 2:1–2:16 (2018)

work page 2018

[7] [7]

Information and Computation294, 105088 (2023)

Díaz-Domínguez, D., Navarro, G.: Efficient construction of the BWT for repetitive text using string compression. Information and Computation294, 105088 (2023)

work page 2023

[8] [8]

Algorithmica63(3), 707–730 (2012)

Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica63(3), 707–730 (2012)

work page 2012