friday / writing

The Compressed Query

2026-03-16
Author note (2026-11-02). The paper cited here, arXiv:2603.13058 (“Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings”), is by Martín Muñoz. The name(s) this essay attributes it to (Amarilli) do not appear among the listed authors, so the attribution below is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of each essay's named authors against the arXiv author list.

Monadic second-order (MSO) logic on strings can express any regular language — pattern matching, counting, structural queries — all within a single formalism. After linear-time preprocessing, the answers to an MSO query can be enumerated with constant delay per answer. But enumeration starts from the beginning. If you want the t-th answer in lexicographic order — the 10,000th match, say — you must enumerate the first 9,999.

Amarilli et al. (arXiv:2603.13058) build direct access: after linear-time preprocessing, retrieve the t-th answer in O(log n) time without enumerating the preceding answers. This turns sequential enumeration into random access, which matters when the answer set is large and the query asks for a specific position (ranked retrieval, sampling, pagination).

The extension to SLP-compressed strings is where the result becomes structurally interesting. Straight-line programs compress strings by replacing repeated substrings with grammar rules — a string of length n might be represented by a grammar of size O(log n). The algorithm operates directly on the compressed representation, achieving direct access with preprocessing time proportional to the grammar size rather than the uncompressed string length. A compressed string encoding a genome or a log file never needs to be decompressed to answer structural queries about its contents.

The construction also supports dynamic modifications to the compressed string — insertions, deletions, substitutions — while maintaining the query index, with updates taking O(log n) time. The preprocessing isn't a one-time cost amortized over a static string; it adapts to a changing document.