💻 computer science

Ranked MSO-enumeration over compressed words

This paper presents the first algorithm for ranked MSO-query enumeration on grammar-compressed strings, achieving linear preprocessing and constant delay by adapting factorization trees to the compressed setting, which subsequently enables efficient enumeration of polyregular functions on compressed inputs.

Original authors: Markus Lohrey

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Markus Lohrey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library of books, but instead of storing every single page, you only keep a tiny instruction manual (a "recipe") that tells you how to reconstruct the entire book. This is what grammar compression does for data: it stores a huge string of text in a very small, compressed format called a Straight-Line Program (SLP). Think of the SLP as a set of nested instructions like "Take the word 'Hello', repeat it 100 times, then add 'World'."

The problem this paper tackles is: How do you find specific answers inside this compressed book without first unpacking the whole thing?

Usually, if you want to find every sentence that matches a complex rule (like "Find all names that appear after a date but before a location"), you have to read the whole book. If the book is compressed, you might think you have to uncompress it first, which defeats the purpose of saving space.

The Main Achievement: The "Magic Index"

The authors, Markus Lohrey, have created a new method to search these compressed books. Here is the breakdown of their breakthrough:

The Setup: You have a compressed string (the recipe) and a specific question (a query) written in a powerful logic language called MSO (Monadic Second-Order logic). This language is like a very precise search engine query that can say things like "Find the 3rd letter that is different from the 5th letter."
The Goal: You want to list all the answers (the "tuples" or positions) one by one.
The "Ranked" Twist: In the past, computers would spit out answers in a random, chaotic order. This paper introduces "Ranked Enumeration." This means the computer lists the answers in a specific, predictable order (like alphabetical order or numerical order) that you define in advance.
The Result: The authors show that you can prepare the compressed recipe in linear time (very fast, proportional to the size of the recipe, not the huge book it represents). Once prepared, the computer can spit out the answers one by one with constant delay.
- Analogy: Imagine a librarian who spends 5 minutes organizing a tiny index card (the preprocessing). After that, they can hand you the next correct book page instantly, no matter how long the book is. There is no waiting time between handing you page 1 and page 2.

How They Did It: The "Factorization Tree"

To achieve this magic, the authors used a clever tool called a Factorization Tree.

The Metaphor: Imagine you have a long string of letters. A factorization tree is like a family tree for that string. It breaks the string down into smaller chunks.
The Rule: If a chunk is made of many smaller chunks that are all "repeating" the same pattern (mathematically, they are "idempotent"), the tree treats them as a special group.
The Innovation: The authors figured out how to build this family tree directly from the compressed recipe (the SLP) without ever writing out the full string. They call this a "Simon SLP."
The Traversal: They also developed a way to "walk" through this compressed tree instantly. Imagine walking through a maze where the walls are instructions. Usually, you have to read every instruction to know where to turn. Their method allows you to jump from one instruction to the next instantly, knowing exactly where you are in the final, huge string.

Why This Matters (According to the Paper)

Polyregular Functions: The paper mentions a specific type of data transformation called a "polyregular function" (like a complex text editor macro). Previously, if you had a compressed text and wanted to apply this macro, you couldn't easily list the results in order. Now, you can.
First Time for Compressed Data: This is the first time anyone has achieved this "constant delay" speed for ranked (ordered) queries on compressed data. Before this, you either had to wait longer between answers or deal with answers coming out in a random order.

What They Didn't Do (The Limits)

The paper is very specific about what it covers:

No Set Variables: The queries they handle only look for specific positions (like "the 5th letter"). They do not yet handle queries that ask about "sets of letters" (like "find all groups of letters that form a palindrome"). If you ask about sets, the answers get too big to print instantly, and this method doesn't apply yet.
Strings Only: This works for text (strings). They mention that doing this for trees (like XML files) is a future goal, but they haven't solved that yet.
No "Weight" Sorting: Other researchers have sorted answers by "weight" (like importance scores). This paper sorts by a strict logical order (like dictionary order). They note that combining these two ideas is still an open question.

Summary

In short, this paper gives us a new, super-fast way to search through compressed text. It's like having a magic map that lets you find specific spots in a giant city by looking at a tiny blueprint, and then walking to those spots one by one without ever getting stuck or waiting. The answers come out in a neat, organized line, ready for you to use immediately.

Technical Summary: Ranked MSO-enumeration over Compressed Words

Problem Statement
The paper addresses the problem of enumerating the answers to a fixed Monadic Second-Order (MSO) query over a string that is provided in a compressed format. Specifically, the input string $w$ is given by a Straight-Line Program (SLP), which is a context-free grammar generating exactly one string. The goal is to compute all tuples $(a_1, \dots, a_k)$ of positions in $w$ satisfying a fixed MSO formula $\Phi(x_1, \dots, x_k)$ .

A critical constraint of this work is ranked enumeration. Unlike standard enumeration algorithms where output order is opaque, ranked enumeration requires the output tuples to be printed in a specific, user-defined order that is itself MSO-definable (e.g., lexicographic order on position tuples). The efficiency metric for such algorithms is linear preprocessing time (linear in the size of the SLP, $|G|$ ) followed by constant delay (a constant bound on the time between outputting consecutive tuples).

Prior to this work, ranked enumeration for MSO queries was known for uncompressed strings and trees, but no results existed for compressed data. Furthermore, existing enumeration results for compressed strings (e.g., [29]) achieved only output-linear delay and did not support ranked enumeration.

Methodology
The solution combines three primary technical components:

Factorization Trees and Simon SLPs:
The core structural tool is the factorization tree, a parse tree for a word with respect to a morphism into a finite monoid, where nodes with $\ge 3$ children evaluate to the same idempotent element. Simon's theorem guarantees such trees have height bounded by a constant depending on the monoid size.
The paper introduces the concept of a Simon SLP (SSLP): an SLP that is structurally compatible with a factorization tree of the generated word. The authors prove (Theorem 3.1) that any given SLP can be transformed into an equivalent SSLP in linear time. This transformation involves constructing a nondeterministic transducer that generates factorization trees and then restructuring the grammar to reflect the tree's hierarchy, ensuring the "idempotent-contracted depth" of the SLP is bounded by a constant ( $3|M|$ ).
Constant-Time Traversal in Compressed Strings:
To navigate the compressed string efficiently, the paper utilizes and extends techniques from [26] for two-way constant-time traversal. The authors define compressed paths (sequences of triples representing left/right moves in the SLP's DAG) and maintain a dynamic data structure (a binary tree $B$ ) that stores a constant number of "active" paths.
Crucially, they define procedures right and left that, given a path in the compressed representation, compute its lexicographic successor or predecessor in constant time. This involves splitting edges in the traversal tree and managing "idempotent-contracted" subpaths within specific parts of the SLP (the $e$ -parts).
MSO Interpretation and Successor Computation:
The enumeration algorithm is framed as computing the image of a polyregular function (or more generally, an MSO-string-to-string interpretation). The algorithm iteratively computes the "successor" of a current tuple of positions according to the MSO-definable linear order.
The proof involves transforming the MSO formulas into Non-deterministic Finite Automata (NFAs) and deriving a finite monoid $M$ . By precomputing monoid elements for nodes in the factorization tree (or the equivalent SSLP), the algorithm can determine the next position in the enumeration sequence in constant time. It handles the transition between positions by analyzing the monoid elements of the segments between current positions and using the structure of the factorization tree to navigate to the next valid position without decompressing the string.

Key Contributions and Results

Main Theorem (Theorem 5.1): For a fixed MSO formula with $k$ free first-order variables and an MSO-definable linear order on $k$ -tuples, the set of query answers on an SLP-compressed string can be enumerated with linear preprocessing time ( $O(|G|)$ ) and constant delay. This is the first result of its kind for ranked enumeration on compressed data.
Corollary for Polyregular Functions (Corollary 5.3): The result generalizes to polyregular string-to-string functions. For a fixed polyregular function $f$ and an SLP $G$ producing $w$ , the symbols of $f(w)$ can be enumerated from left to right with linear preprocessing and constant delay. This extends a previous result by Bojanczyk [8] (which assumed uncompressed input) to the compressed setting, despite the fact that polyregular functions do not generally preserve compression size.
Corollary for Successor-MSO (Corollary 5.5): The result holds for the broader class of successor-MSO string-to-string interpretations, which are strictly larger than polyregular functions.
Technical Contribution (Simon SLPs): The paper establishes that every SLP can be converted to a Simon SLP in linear time. This makes factorization trees accessible to the grammar-compressed setting, a contribution noted as being of independent interest.

Significance and Claims
The paper claims to make the "first step" in the direction of ranked enumeration on compressed data. It addresses a specific gap where previous compressed enumeration algorithms (e.g., [29]) could not control the output order, and previous ranked enumeration algorithms (e.g., [2, 12, 19]) could not handle compressed inputs.

The authors emphasize that their approach relies on the specific structure of factorization trees and the ability to perform constant-time navigation on SLPs. They explicitly note limitations:

The current results apply only to queries with free first-order variables; handling free set variables (which would require output-linear delay rather than constant delay) is an open problem, as the factorization tree approach does not currently extend to set variables.
The work is currently restricted to strings; extending the results to forests (using forest straight-line programs) is identified as future work, pending the combination of forest factorization theorems with forest SLP traversal techniques.
The ranking is restricted to MSO-definable linear orders; the relationship between this model and weight-based ranking (using cost transducers) remains unclear.

In summary, the paper provides a theoretical foundation for efficient, ordered query processing on highly compressed data, demonstrating that the "gold standard" of linear preprocessing and constant delay is achievable for MSO queries on SLPs, provided the output order is MSO-definable.