Adaptive Learning of Compressible Strings

Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $σn/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $σ$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(σ-1)n+O(σ\sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to $τ$ bits, performs $q=O(τ)$ substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length $n$ over an integer alphabet of size $σ$ with $rle$ runs can be reconstructed with $q=O(rle (σ+ \log \frac{n}{rle}))$ substring queries in linear time and space. We then present an algorithm that spends $q \in O(σg\log n)$ substring queries and runs in $O(n(\log n + \log σ)+ q)$ time using linear space, where $g$ is the size of a smallest straight-line program generating the string.