Papers for

software developers in text processing

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Algorithms for finding smallest substring compression schemes efficiently

Exact and Approximation Algorithms for Computing Smallest SESs and BMSs

Abstract: Compression schemes represent repetitive strings compactly by using repeated substrings. Computing the minimum size of a representation of a given input string is important for compression and for understanding relationships between compression schemes, although this task is NP-hard for several schemes. In this paper, we introduce exact and approximation algorithms for finding smallest substring equation systems (SESs) and bidirectional macro schemes (BMSs). Specifically, for an input string of length $n$, we give deterministic and randomized algorithms for computing a smallest SES using $O^*(4^n)$ and $O^*(2^n)$ time and space, respectively. We also give a deterministic algorithm for computing a smallest BMS using $O^*(2^n)$ time and space. We further give deterministic and randomized $(1+α)$-approximation algorithms for smallest SESs using $O^*(4^{e^{-α}n})$ and $O^*(2^{e^{-α}n})$ time and space, respectively, for every $α\ge 0$. A conversion from SESs to BMSs gives $4(1+α)$-approximation algorithms for smallest BMSs with the same time and space bounds. All time bounds hold in the worst case, and the randomized algorithms return correct answers with high probability. Our algorithms adapt several approaches to exact and approximation algorithms for combinatorial problems, such as dynamic programming over determinant expansions and a greedy algorithm for monotone submodular functions.

Thu 12 NovData Structures and Algorithms
The gist
Compressing repetitive strings relies on representing repeated parts concisely. The authors focus on two specific types of such representations called smallest substring equation systems (SESs) and bidirectional macro schemes (BMSs). They offer new exact algorithms that can find these smallest representations and also faster approximate algorithms that get close to the smallest size. These algorithms use clever methods like dynamic programming and greedy approaches to solve a problem that’s usually very hard to do exactly.
Open → 2611.16164v1