Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing

Diego Diaz-Dominguez

REVIEW 3 major objections 6 minor 1 cited by

Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Stable local consistency makes grammar compression parallel and scalable to terabytes.

desk verdict A real terabyte-scale grammar compressor with an under-proved but likely correct theory; the merge invariant holds by induction, stability needs a written proof. read the letter →

arxiv 2411.12439 v2 pith:AW33AWGV submitted 2024-11-19 cs.DS

Diego Diaz-Dominguez This is my paper · ORCID

classification cs.DS MSC 68P3068W10

keywords grammarcompressionlocallyconsistentparsingstablelocalconsistencyparallelhashfingerprintsLMSmergingterabyte-scaledata

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 claims that grammar compression can be made parallel by a property it calls stable local consistency: if each independent chunk is parsed with the same set of hash functions, repeated substrings acquire cores with identical tree topology even though nonterminal names differ. It then shows a merge operation that matches rules by right-hand-side strings, producing a single grammar equivalent to one built over the whole collection. If these claims hold, the result is a grammar compressor that runs in linear expected time, uses working memory proportional to grammar size, and processed 7.9 TB of bacterial genomes in about nine hours on 16 threads, at 0.43 bits per symbol, with an 85x compression ratio. The paper positions this as making terabyte-scale grammar-based compression and downstream grammar-based string processing practical.

What carries the argument

The load-bearing mechanism is stable local consistency, defined via the recursive polynomial fingerprints of Equation 2: each nontterminal's fingerprint is computed from the fingerprints of the symbols on its right-hand side, so two equal expansions get equal fingerprints regardless of the grammar in which they appear. BuildGram uses these fingerprints to classify positions as L/S/LMS types and induce breaks, generalising the suffix-sorting parsing of Nong et al. MergeGrams then matches rules level by level using the fingerprint-derived comparability of right-hand sides, discarding rules from one grammar whose expansion already occurs in the other.

What would settle it

Take two strings that share a long pattern P but differ in flanks chosen to shift the LMS-type classification inside P; run BuildGram on each with the same H, then run MergeGrams. If the merged grammar is not equivalent to BuildGram over the concatenated collection — for instance if some rule expansion in the merged grammar is not a string of the collection — the stability property fails.

Watch

Extended reading notes

Core claim

The central claim is that the stable property of BuildGram — that independent executions on different collections, given the same hash set H, produce cores with the same topology for every pattern — allows MergeGrams to combine grammars by matching right-hand sides rather than by synchronising nonterminal labels. The paper proves that MergeGrams(Ga,Gb) returns a locally consistent grammar for the union collection that is equivalent to BuildGram(Tab,H), runs in O(Ga+Gb) time with high probability, and uses O(Ga log ga + Gb log gb) bits of space. It also proves BuildGram runs in O(n) time with high probability and O(G log w) bits of working space. The experiments support the practical consequence: the implementation LCG compresses terabyte-scale collections with a speed between 232 and 506 MB/s, using 0.29–2.05 bits per symbol of memory, roughly an order of magnitude less memory than existing grammar compressors.

Load-bearing premise

The whole parallel merge depends on the claim that two independent runs of the parser on different collections, using the same hash functions, will always give the same repeated substring the same internal phrase boundaries (the same core topology), no matter what surrounds it.

Editorial extensions

If this is right

Grammar-based compression can be parallelised without loss: merging chunk grammars yields exactly the grammar the whole collection would have produced, so compression ratio does not degrade when many threads are used.
BuildGram's O(n) expected time and O(G log w) working space make it feasible to compress tens of terabytes on a single machine with modest memory.
The stability concept is not tied to the specific parsing: any locally consistent grammar that uses hashing to break text can be made stable in the same way.
Post-processing (run-length encoding of equal-symbol runs and removal of unique nonterminals) further shrinks the grammar, with Simp deleting more than 80% of nonterminals in the experiments.
The resulting grammar can be used as input to grammar-based string algorithms, potentially scaling MEM computation, BWT construction, and pattern matching to larger collections.

Reading between the lines

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

If stability holds without a common nonterminal label set, a collection could be parsed by different machines with different hash seeds and still be merged by comparing right-hand sides, as long as the seeds are shared; the paper only requires the same H, so this is an untested extension.
The merge cost is linear in grammar size rather than text size, which suggests that repeated merging (as in a streaming or distributed setting) adds only a small overhead; the paper's PBuildGram already does tree-shaped merges, so a more general distributed merge tree is a natural next step.
The empirical memory collapse from VByte keys suggests most of the reported working memory is phrase storage, not grammar structure; an inference is that an on-disk or more compact phrase store could bring working memory close to zstd levels while keeping grammar-based compression.
A testable consequence: if stability fails on low-entropy or highly repetitive boundaries (e.g., long runs of the same symbol where breaks are suppressed), the compression ratio would drop or the merged grammar would generate spurious strings; the paper avoids runs in the parsing, so the boundary handling is the spot to probe.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

LCG is the real deal on the practical side — genuinely the first grammar compressor demonstrated at terabyte scale — and the theory is under-proved but, as far as I can tell, correct.

The experiments carry the paper: 7.9 TB of bacterial genomes compressed in about nine hours with 16 threads and 0.43 bps of working memory, and it is the only grammar-based tool in the comparison that handled ATB and HUM at all. Table 2 and Figure 4 give a credible resource breakdown, and the paper is honest about losing on ratio to RePair and on memory to zstd. The genuinely new pieces are the stable-local-consistency framing and the merge-by-RHS algorithm; the code is public on GitHub. The enabling trick is real: fingerprinting full expansions means two independent runs agree on phrase boundaries without sharing nonterminal identifiers, which is what lets you merge grammars by matching right-hand sides.

The soft spots are where the reader puts them, with one correction. The stress test's failure scenario — equal RHS strings with unequal expansions, generating strings outside Tab — does not survive contact with the algorithm. The Section 3.6 invariant is bookkeeping: at level 1 the RHSs are terminals, so equal RHS means equal expansion, and the induction steps through the M remapping, which is defined by RHS matches. If a common expansion is parsed at different boundaries in Ta and Tb, the level-1 rules simply differ; higher levels then fail to match, and you get a larger grammar, not a wrong one. The paper omits the inductive step, which is annoying, but it is a page of work.

The genuine gap is stability itself. Definition 1 promises identical core topology for any pattern; the informal argument in Section 3.3.1 leans on 'identical context,' which is weaker than the definition. I believe the full claim is true w.h.p., because the fingerprint order is a total order on symbols that depends only on expansions, so the standard LMS local-consistency argument applies. But the paper never proves it, and the equivalence claim Gab = BuildGram(Tab,H) is asserted rather than demonstrated; Theorem 3's proof covers time and space only. Minor: Theorem 2 states O(G log w) for space, but the introduction says O(G log G) and the proof's own expansion is O(G log G) + g log w + |H|w. Also, all numbers are single runs, no error bars.

Who this is for: the grammar-compression and string-algorithms community, and anyone compressing genome collections. It deserves a serious referee. Send it, and ask the author to write out the stability and merge-correctness proofs before acceptance.

Referee Report

3 major / 6 minor

Summary. The paper proposes stable local consistency as a property of grammar-compression algorithms and uses it to design a parallel compressor, LCG. The main theoretical objects are BuildGram(T,H), which builds a locally consistent grammar in O(n) time w.h.p. using a shared set of hash functions, and MergeGrams(Ga,Gb), which merges two independently built grammars in O(Ga+Gb) time and O(Ga log ga + Gb log gb) space. The paper claims that the merged grammar is equivalent to the grammar BuildGram would produce on the union of the inputs. The experimental section reports that LCG compresses 7.9 TB of bacterial genomes in about nine hours with 16 threads and 0.43 bits/symbol of working memory, with compression ratios of 85x on ATB and up to 328x on COVID, and includes detailed comparisons with zstd, agc, RePair, and BigRePair.

Significance. If the equivalence theorem were established, this would be a significant contribution: it would provide the first grammar-compression method that scales to terabyte-sized collections with near-linear time and modest memory, and the stability concept would be of independent interest for parallel string processing. The experimental evidence is strong and transparent: Table 1 shows speed/memory/ratio for four competitors, Table 2 reports grammar-size statistics, Figure 4 gives time and memory breakdowns, and the implementation is released. The compression ratios are competitive, and the memory footprint is two to three orders of magnitude below that of RePair and BigRePair on the tested inputs. The main weakness is that the central theoretical equivalence is not proved; the current paper is therefore best read as a well-executed empirical demonstration plus an unproven theoretical framework.

major comments (3)

[Section 3.6, Theorem 3] The central claim that MergeGrams(Ga,Gb) is equivalent to BuildGram(Tab,H) is not proved. The proof of Theorem 3 only bounds the time and space of the merge operations; it never shows that the rule set of Gab coincides with, or is equivalent to, the rule set produced by BuildGram on the union, nor that the merged rules have the same expansions as the sequential ones. The 'comparable right-hand sides' invariant is stated in the first paragraph of Section 3.6 and is asserted to hold for i+1 after a merge round, but no inductive argument is given. In particular, the step from level i to i+1 requires showing that if a level-i RHS of Gb equals a level-i RHS of Ga after renumbering, then the corresponding nonterminals have identical terminal expansions; this is exactly the property that must be established, and the stability discussion in Section 3.3.1 only gives the weaker statement for occurrences 'surrounded by an identical context.' Without this proof, the merge could fail to identify rules that BuildGram(Tab,H) would identify, producing a larger grammar, or could merge rules with equal integer RHS but different expansions, producing a grammar that generates strings outside Tab. The proof must be supplied or the claim must be weakened.
[Section 3.3.1, Definition 1] Definition 1 promises that, for any pattern P appearing in two distinct texts, the independent executions ALG(Ta) and ALG(Tb) produce cores with identical topology. The only supporting argument is the sentence stating that if exp(T_i[ell]) appears in another collection T' different from T 'surrounded by an identical context,' then the breaks and core topology are identical. This condition is strictly weaker than the definition; it does not cover occurrences with different flanking contexts, which are exactly the cases that can arise in the merge scenario. Since the merge equivalence in Theorem 3 relies on this stability property, the paper needs either a rigorous proof that the hash-based LMS parsing is stable in the sense of Definition 1, or a formal statement of the weaker property that actually holds together with a proof that this weaker property suffices for the merge to be equivalent to BuildGram(Tab,H). As written, the property is asserted informally and is load-bearing for the paper's main theoretical claim.
[Sections A.2-A.3, PBuildGram] The experiments do not directly test the pair BuildGram/MergeGrams of Sections 3.3-3.6; they test PBuildGram, which uses a different variant of BuildGram with a read-only sink grammar and a merge tree (Section A.3). The correctness and equivalence of this parallel pipeline to BuildGram(Tab,H) is never stated as a theorem or proved. In particular, the modified BuildGram in Section A.2 assigns new metasymbols using s_a+s_b+1 and relies on the sink grammar's hash tables being read-only; the interaction between this variant and the MergeGrams equivalence is not analyzed. Since the experimental results are the paper's main evidence, the relationship between PBuildGram and the theoretical claims should be formalized.

minor comments (6)

[Section 3.5] In the overview of MergeGrams, 'MergeGrams(Ga,Ga)' should read 'MergeGrams(Ga,Gb)'.
[Section 2.3 and Definition 1] Section 2.3 says the core of P has identical topology and labels, while Definition 1 says cores have identical topology and different nonterminal labels; please clarify whether the definition of core includes labels or only topology.
[Section 3.3, Theorem 2] Theorem 2 states O(G log w) bits of working space, but the proof's last sentence claims O(G logG)+g logw+|H|w = O(G logw), which is not correct since O(G logG) dominates O(G logw) whenever logG is not O(log log n). The introduction and the proof both suggest the intended bound is O(G logG) bits; please correct the theorem statement and the algebra.
[Section 3.3, Theorem 2 proof] The proof of the O(n) time bound should make explicit that the sum of log|T_j| over the input strings is at most (n/nmax) log nmax, which is at most n for nmax at least 2; the current text jumps from a sum involving 2k log nmax to the conclusion O(n) without this inequality.
[References] Several citations to Nong et al. are inconsistent: Section 2.3 cites Nong et al. [29], Section 3.3 cites Nong et al. [22], and Section 3.3.1 cites Nong et al. [27]; references [22] and [29] do not correspond to the intended works by Nong, Zhang, and Chan. Please fix the citation numbers.
[Section 4] The experimental section does not report the threshold t or the fingerprint widths m_i used in the runs; please provide these parameters for reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central merge equivalence is asserted with an informal proof gap, but no claim reduces by construction to its own inputs or to a load-bearing self-citation.

full rationale

The claimed derivation chain is not circular. BuildGram's construction and MergeGrams' equivalence rest on the newly defined stable local consistency property (Definition 1), which is asserted for the hash-based parsing rather than derived from a fitted parameter or from a self-citation. The hash fingerprints h_i are computed from expansions via Equation 2/4, so equal expansions receive equal fingerprints by design; this is an input assumption with collision probability, not an output later presented as a prediction. The merge invariant in Section 3.6 (Q_a = Q_b implies exp(X_a) = exp(X_b)) is argued inductively from a terminal base case and from renumbering Gb symbols into Ga's alphabet; although the proof is informal and Theorem 3 proves time and space bounds but not the stated equivalence to BuildGram(Tab,H), that is an unproven correctness gap, not a circular reduction. Compression ratios are direct measurements, and the tunable parameters mentioned (fingerprint width, buffer threshold) affect speed and memory rather than forcing the claimed equivalence. The paper's self-citations [7,8,9] support applications of locally consistent grammars and are either accompanied by external support or are not load-bearing for the merge equivalence claim. No fitted input is renamed as a prediction, and no uniqueness theorem from the authors is invoked to force a choice. Accordingly, no circular step can be exhibited, and the paper is self-contained against external benchmarks.

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

The central theoretical claims rest on unproved stability and merge equivalence, which are listed as ad hoc assumptions; the only numeric freedom is the fingerprint range and buffer threshold, both tuned for memory rather than fitted to a target compression ratio. No new physical or mathematical entities are postulated.

free parameters (2)

fingerprint range m_i (bit width) = 32-bit fingerprints in experiments (m_i < 2^32)
Chosen to balance collisions against working memory; Section 4.1.2 says 32-bit fingerprints are likely enough for repetitive collections of tens of TB. Not fitted to a target compression ratio.
buffer memory threshold t in PBuildGram = not reported
User-set threshold in Section A.3 that triggers merging of buffer grammars; it trades memory against merge frequency but does not affect the final grammar content.

assumptions (5)

domain assumption Nong et al. LMS parsing is locally consistent.
BuildGram uses this parsing (Section 3.3.1); the paper cites [8,5] for the local-consistency property but does not prove it. If false, cores and stability collapse.
domain assumption Every pattern P in a locally consistent grammar has a core with identical topology across occurrences.
Section 2.3 states this as the defining property of locally consistent grammars, citing Sahinalp-Vishkin [32]. It is the basis for the compression and for stability.
ad hoc to paper BuildGram with shared hash set H is stable: independent executions produce cores with the same topology.
Definition 1 in Section 3.3.1 is new and is argued informally, not proved. MergeGrams relies on it to match rules across grammars.
ad hoc to paper If two right-hand sides are equal after renumbering, their terminal expansions are equal, and merging by exact string matching preserves equivalence to BuildGram(Tab,H).
Section 3.6 asserts the invariant and equivalence; Theorem 3 does not prove correctness, only time and space.
standard math Fingerprint collisions are rare enough for correctness with high probability.
The universal/polynomial hash construction (Section 2.4, [10]) gives collision probability 1/m; the paper's w.h.p. bounds depend on this.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing." pith.science (2026). https://pith.science/paper/AW33AWGV

@misc{pith2026241112439,
  author       = {Pith},
  title        = {Pith review of: Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AW33AWGV}},
  note         = {Machine review of arXiv:2411.12439}
}

abstract

We present a highly parallelizable text compression algorithm that scales efficiently to terabyte-sized datasets. Our method builds on locally consistent grammars, a lightweight form of compression, combined with simple recompression techniques to achieve further space reductions. Locally consistent grammar algorithms are particularly suitable for scaling, as they need minimal satellite information to compact the text. We introduce a novel concept to enable parallelisation, stable local consistency. A grammar algorithm ALG is stable, if for any pattern $P$ occurring in a collection $\mathcal{T}=\{T_1, T_2, \ldots, T_k\}$, the instances $ALG(T_1), ALG(T_2), \ldots, ALG(T_k)$ independently produce cores for $P$ with the same topology. In a locally consistent grammar, the core of $P$ is a subset of nodes and edges in $\mathcal{T}$'s parse tree that remains the same in all the occurrences of $P$. This feature is important to achieve compression, but it only holds if ALG synchronises the parsing of the strings, for instance, by defining a common set of nonterminal symbols for them. Stability removes the need for synchronisation during the parsing phase. Consequently, we can run $ALG(T_1), ALG(T_2), \ldots, ALG(T_k)$ fully in parallel and then merge the resulting grammars into a single compressed output equivalent to $ALG(\mathcal{T})$. We implemented our ideas and tested them on massive datasets. Our results showed that our method could process a diverse collection of bacterial genomes (7.9 TB) in around nine hours, requiring 16 threads and 0.43 bits/symbol of working memory, producing a compressed representation 85 times smaller than the original input.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

LCPan: efficient variation graph construction using Locally Consistent Parsing
q-bio.GN 2025-11 conditional novelty 6.0 of 10

An iterative LCP implementation enables a variation graph constructor that is >10x faster and >13x more memory-efficient than vg on human pangenome data.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages · cited by 1 Pith paper

[1]

Prefix-free parsing for building big BWT s

Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big BWT s. Algorithms for Molecular Biology , 14:1--15, 2019

work page 2019
[2]

The smallest grammar problem

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Transactions on Information Theory , 51(7):2554--2576, 2005

work page 2005
[3]

Optimal-time dictionary-compressed indexes

Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. Optimal-time dictionary-compressed indexes. ACM Transactions on Algorithms (TALG) , 17(1):1--39, 2020

work page 2020
[4]

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

Richard Cole and Uzi Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proc. 18th Annual ACM Symposium on Theory of Computing (STOC) , pages 206--219, 1986

work page 1986
[5]

FM -indexing grammars induced by suffix sorting for long patterns

Jin-Jie Deng, Wing-Kai Hon, Dominik K \"o ppl, and Kunihiko Sadakane. FM -indexing grammars induced by suffix sorting for long patterns. In Proc. 22nd Data Compression Conference (DCC) , pages 63--72. IEEE, 2022

work page 2022
[6]

AGC : compact representation of assembled genomes with fast queries and updates

Sebastian Deorowicz, Agnieszka Danek, and Heng Li. AGC : compact representation of assembled genomes with fast queries and updates. Bioinformatics , 39(3):btad097, 2023

work page 2023
[7]

Efficient construction of the BWT for repetitive text using string compression

Diego D \' az-Dom \' nguez and Gonzalo Navarro. Efficient construction of the BWT for repetitive text using string compression. Information and Computation , 294:105088, 2023

work page 2023
[8]

An LMS -based grammar self-index with local consistency properties

Diego D \' az-Dom \' nguez, Gonzalo Navarro, and Alejandro Pacheco. An LMS -based grammar self-index with local consistency properties. In Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 100--113, 2021

work page 2021

Show all 33 references

[9]

Computing all-vs-all MEM s in grammar-compressed text

Diego D \' az-Dom \' nguez and Leena Salmela. Computing all-vs-all MEM s in grammar-compressed text. In Proc. 30th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 157--170. Springer, 2023

2023
[10]

Polynomial hash functions are reliable

Martin Dietzfelbinger, Joseph Gil, Yossi Matias, and Nicholas Pippenger. Polynomial hash functions are reliable. In Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP) , pages 235--246, 1992

1992
[11]

Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding

Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540 , 2013

2013 arXiv
[12]

Rpair: Rescaling R e P air with rsync

Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, and Yoshimasa Takabatake. Rpair: Rescaling R e P air with rsync. In Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 35--44, 2019

2019
[13]

Optimal dynamic strings

Pawe Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub a cki, and Piotr Sankowski. Optimal dynamic strings. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1509--1528, 2018

2018
[14]

David A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE , 40(9):1098--1101, 1952

1952
[15]

AllTheBacteria -all bacterial genomes assembled, available and searchable, 2024

Martin Hunt, Leandro Lima, Wei Shen, John Lees, and Zamin Iqbal. AllTheBacteria -all bacterial genomes assembled, available and searchable, 2024. bioRxiv preprint. https://doi.org/10.1101/2024.03.08.584059 doi:10.1101/2024.03.08.584059

2024 doi
[16]

A really simple approximation of smallest grammar

Artur Je \.z . A really simple approximation of smallest grammar. Theoretical Computer Science , 616:141--150, 2016

2016
[17]

Kieffer and En Hui Yang

John C. Kieffer and En Hui Yang. Grammar--based codes: a new class of universal lossless source codes . IEEE Transactions on Information Theory , 46(3):737--754, 2000

2000
[18]

Near-optimal search time in -optimal space, and vice versa

Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares. Near-optimal search time in -optimal space, and vice versa. Algorithmica , 86(4):1031--1056, 2024

2024
[19]

Toward a definitive compressibility measure for repetitive sequences

Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. Toward a definitive compressibility measure for repetitive sequences. IEEE Transactions on Information Theory , 69(4):2074--2092, 2022

2022
[20]

Jesper Larsson and Alistair Moffat

N. Jesper Larsson and Alistair Moffat. Off-line dictionary-based compression. Proceedings of the IEEE , 88(11):1722--1732, 2000

2000
[21]

On the complexity of finite sequences

Abraham Lempel and Jacob Ziv. On the complexity of finite sequences . IEEE Transactions on Information Theory , 22(1):75--81, 1976

1976
[22]

Fast and accurate long-read alignment with B urrows- W heeler T ransform

Heng Li and Richard Durbin. Fast and accurate long-read alignment with B urrows- W heeler T ransform. Bioinformatics , 26(5):589--595, 2010

2010
[23]

Maintaining dynamic sequences under equality tests in polylogarithmic time

Kurt Mehlhorn, Rajamani Sundar, and Christian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica , 17:183--198, 1997

1997
[24]

Muthukrishnan and S \"u leyman Cenk Sahinalp

S. Muthukrishnan and S \"u leyman Cenk Sahinalp. Approximate nearest neighbors and sequence comparison with block operations. In Proc of 32nd Annual ACM Symposium on Theory of Computing (STOC) , pages 416--424, 2000

2000
[25]

Computing MEM s and relatives on repetitive text collections

Gonzalo Navarro. Computing MEM s and relatives on repetitive text collections. ACM Transactions on Algorithms , 21(1):1--33, 2024

2024
[26]

Nevill-Manning and Ian H

Craig G. Nevill-Manning and Ian H. Witten. Compression and explanation using hierarchical grammars. The Computer Journal , 40(2\_and\_3):103--116, 1997

1997
[27]

Practical linear-time O(1) -workspace suffix sorting for constant alphabets

Ge Nong. Practical linear-time O(1) -workspace suffix sorting for constant alphabets. ACM Transactions on Information Systems , 31(3):1--15, 2013

2013
[28]

Linear suffix array construction by almost pure induced-sorting

Ge Nong, Sen Zhang, and Wai Hong Chan. Linear suffix array construction by almost pure induced-sorting. In Proc. 19th Data Compression Conference (DCC) , pages 193--202, 2009

2009
[29]

Louza, Simon Gog, Mauricio Ayala-Rinc \' o n, and Gonzalo Navarro

Daniel Saad Nogueira Nunes, Felipe A. Louza, Simon Gog, Mauricio Ayala-Rinc \' o n, and Gonzalo Navarro. A grammar compression algorithm based on induced suffix sorting . In Proc. 28th Data Compression Conference (DCC) , pages 42--51, 2018

2018
[30]

RePair and all irreducible grammars are upper bounded by high-order empirical entropy

Carlos Ochoa and Gonzalo Navarro. RePair and all irreducible grammars are upper bounded by high-order empirical entropy. IEEE Transactions on Information Theory , 65(5):3160--3164, 2018

2018
[31]

Sublinear algorithms for approximating string compressibility

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, and Adam Smith. Sublinear algorithms for approximating string compressibility. Algorithmica , 65:685--709, 2013

2013
[32]

Symmetry breaking for suffix tree construction

S \"u hleyman Cenk Sahinalp and Uzi Vishkin. Symmetry breaking for suffix tree construction. In Proc. 26th Annual ACM Symposium on Theory of Computing (STOC) , pages 300--309, 1994

1994
[33]

A universal algorithm for sequential data compression

Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression . IEEE Transactions on Information Theory , 23(3):337--343, 1977

1977

Pith tools

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

[1] [1]

Prefix-free parsing for building big BWT s

Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big BWT s. Algorithms for Molecular Biology , 14:1--15, 2019

work page 2019

[2] [2]

The smallest grammar problem

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Transactions on Information Theory , 51(7):2554--2576, 2005

work page 2005

[3] [3]

Optimal-time dictionary-compressed indexes

Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. Optimal-time dictionary-compressed indexes. ACM Transactions on Algorithms (TALG) , 17(1):1--39, 2020

work page 2020

[4] [4]

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

Richard Cole and Uzi Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proc. 18th Annual ACM Symposium on Theory of Computing (STOC) , pages 206--219, 1986

work page 1986

[5] [5]

FM -indexing grammars induced by suffix sorting for long patterns

Jin-Jie Deng, Wing-Kai Hon, Dominik K \"o ppl, and Kunihiko Sadakane. FM -indexing grammars induced by suffix sorting for long patterns. In Proc. 22nd Data Compression Conference (DCC) , pages 63--72. IEEE, 2022

work page 2022

[6] [6]

AGC : compact representation of assembled genomes with fast queries and updates

Sebastian Deorowicz, Agnieszka Danek, and Heng Li. AGC : compact representation of assembled genomes with fast queries and updates. Bioinformatics , 39(3):btad097, 2023

work page 2023

[7] [7]

Efficient construction of the BWT for repetitive text using string compression

Diego D \' az-Dom \' nguez and Gonzalo Navarro. Efficient construction of the BWT for repetitive text using string compression. Information and Computation , 294:105088, 2023

work page 2023

[8] [8]

An LMS -based grammar self-index with local consistency properties

Diego D \' az-Dom \' nguez, Gonzalo Navarro, and Alejandro Pacheco. An LMS -based grammar self-index with local consistency properties. In Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 100--113, 2021

work page 2021