Optimal Dictionary-Based Compression with Answer Set Programming: Encodings and Empirical Analysis

We develop an Answer Set Programming (ASP)-based approach for

computing the smallest bidirectional macro schemes (BMSs),

a fundamental NP-hard optimization problem in dictionary-based compression.

Our approach relies on high-level ASP encodings and delegates both the

grounding and solving tasks to an off-the-shelf ASP solver.

The proposed encoding is compact and extensible, and

leverages advanced ASP techniques to improve scalability,

including ASP modulo acyclicity and refined declarative encodings of acyclicity constraints.

We further show that our ASP encoding can be naturally extended to compute

the smallest straight-line programs (SLPs),

another important NP-hard measure of repetitiveness.

Furthermore, we establish the competitiveness of our approach by

empirically contrasting it with a more dedicated MaxSAT-based approach.