一句话：提出在 SLP 压缩文档上对 annotated automata 查询进行结果枚举的算法，实现 output-linear/常数延迟并改进已有对数延迟。
论文研究压缩文档上的查询结果枚举问题。压缩模型采用 straight-line program（SLP），查询模型为 Annotated Automata，它是带字母标注的正则自动机扩展，可产出任意长结果并推广 regular spanners。作者设计持久化数据结构 Enumerable Compact Sets with Shifts，在预处理后以 output-linear delay 枚举所有结果。预处理时间线性于 SLP 大小、三次于自动机大小；该延迟优于 Schmid 与 Schweikardt 在相同预处理时间下关于未压缩文档大小的对数延迟。该结果给出 regular spanners 的常数延迟枚举算法；通过 succinctly encoded annotations 的扩展，相较 vset automata 的已有结果节省指数因子；并沿用 Schmid 与 Schweikardt 的方式支持复杂文档编辑且保持常数延迟。
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a context-free grammar that produces a single string. For our queries, we use a model called Annotated Automata, an extension of regular automata that allows annotations on letters. This model extends the notion of Regular Spanners as it allows arbitrarily long outputs. Our main result is an algorithm that evaluates such a query by enumerating all results with output-linear delay after a preprocessing phase which takes linear time on the size of the SLP, and cubic time over the size of the automaton. This is an improvement over Schmid and Schweikardt's result, which, with the same preprocessing time, enumerates with a delay that is logarithmic on the size of the uncompressed document. We achieve this through a persistent data structure named Enumerable Compact Sets with Shifts which guarantees output-linear delay under certain restrictions. These results imply constant-delay enumeration algorithms in the context of regular spanners. Further, we use an extension of annotated automata which utilizes succinctly encoded annotations to save an exponential factor from previous results that dealt with constant-delay enumeration over vset automata. Lastly, we extend our results in the same fashion Schmid and Schweikardt did to allow complex document editing while maintaining the constant delay guarantee.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2209-12301,
title = {Constant-delay enumeration for SLP-compressed documents},
author = {Martín Muñoz and Cristian Riveros},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:17)2025}
}