2026-08-17T17:40:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23252 2025-10-27T10:36:16Z ddc:004 open_access

Efficient Terabyte-Scale Text Compression via Stable Local Consistency and Parallel Grammar Processing Díaz-Domínguez, Diego Grammar compression locally consistent parsing hashing We present compression algorithms designed to process terabyte-sized datasets in parallel. Our approach builds on locally consistent grammars, a lightweight form of compression, combined with simple post-processing techniques to achieve further space reductions. Locally consistent grammar algorithms are suitable for scaling as they need minimal satellite information to compact the text, but they are not inherently parallel. To enable parallelisation, we introduce a novel concept that we call stable local consistency. A grammar algorithm ALG is stable if for any pattern P occurring in a collection 𝒯 = {T_1, T_2, …, T_k}, instances ALG(T_1), ALG(T_2), …, 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 the parse tree of 𝒯 that remains the same in all the occurrences of P. This feature enables compression, but it only holds if ALG defines a common set of nonterminal symbols for the strings. Stability removes this restriction, allowing us to run ALG(T_1), ALG(T_2), …, ALG(T_k) in parallel and subsequently merge their grammars into a single output equivalent to that of ALG(𝒯). We implemented our ideas and tested them on massive datasets. Our experiments showed that our method could process 7.9 TB of bacterial genomes in around nine hours, using 16 threads and 0.43 bits/symbol of working memory, achieving a compression ratio of 85x. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Díaz-Domínguez 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.14 urn:nbn:de:0030-drops-232525 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode