Adaptive learning of compressible strings

Gabriele Fici, Rossano Venturini, Nicola Prezza

Risultato della ricerca: Articlepeer review


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(σ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 [Formula presented]> substring queries in linear time and space. We then present an algorithm that spends q∈O(σglogn) substring queries and runs in O(n(logn+logσ)+q) time using linear space, where g is the size of a smallest straight-line program generating the string.
Lingua originaleEnglish
pagine (da-a)46-52
Numero di pagine7
RivistaTheoretical Computer Science
Stato di pubblicazionePublished - 2021

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???


Entra nei temi di ricerca di 'Adaptive learning of compressible strings'. Insieme formano una fingerprint unica.

Cita questo