  Locally decodable channel codes form a special class of error-correcting
codes with the property that the decoder is able to reconstruct any bit of the
input message from querying only a few bits of a noisy codeword. It is well
known that such codes require significantly more redundancy (in particular have
vanishing rate) compared to their non-local counterparts. In this paper, we
define a dual problem, i.e. locally decodable source codes (LDSC). We consider
both almost lossless (block error) and lossy (bit error) cases. In almost
lossless case, we show that optimal compression (to entropy) is possible with
O(log n) queries to compressed string by the decompressor. We also show the
following converse bounds: 1) linear LDSC cannot achieve any rate below one,
with a bounded number of queries, 2) rate of any source coding with linear
decoder (not necessarily local) in one, 3) for 2 queries, any code construction
cannot have a rate below one. In lossy case, we show that any rate above rate
distortion is achievable with a bounded number of queries. We also show that,
rate distortion is achievable with any scaling number of queries. We provide an
achievability bound in the finite block-length regime and compare it with the
existing bounds in succinct data structures literature.
