Pair Encoding: Approximation and the Cost of a Strict Budget

How well can pair encoding compress a string with a limited number of merge rules? We characterize legal partial executions as reachable creation-ordered binary forests and establish a separation between strict and relaxed budgets. For every string, we construct one binary hierarchy whose prunings approximate both the rule count and final length of every comparison forest within $O({\log }^{2}n)$. This yields a uniform weighted approximation and an unconditional budget/length bicriteria algorithm. Conversely, unless $\mathrm{P}=\mathrm{NP}$, no deterministic polynomial-time algorithm achieves a sublinear length factor under a strict budget on growing-alphabet inputs, even with sufficiently small fixed budget inflation and complete freedom to redesign the dictionary. The hardness is witnessed by an NP-hard gap between one final token and linearly many tokens; extracting a vertex cover from any output forest makes the conclusion independent of dictionary design. The rule-free $n$-approximation has the optimal worst-case asymptotic order at strict budget. We also derive computable length certificates and sharp utility-loss identities across snapshot, final-state, and temporal resolutions. Reproducible experiments retain all $9,473$ exact records and $288$ full-window runs, measuring certificate strength, policy sensitivity, and the structural identities on finite inputs.