Compression of Data Streams Down to Their Information Content

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Source coding (94A29)

Abstract: According to Kolmogorov complexity, every finite binary string is compressible to a shortest code -- its information content -- from which it is effectively recoverable. We investigate the extent to which this holds for infinite binary sequences (streams). We devise a new coding method which uniformly codes every stream

X

into an algorithmically random stream

Y

, in such a way that the first

n

bits of

X

are recoverable from the first

I (X u p h a r p o o n r i g h t_{n})

bits of

Y

, where

I

is any partial computable information content measure which is defined on all prefixes of

X

, and where

X u p h a r p o o n r i g h t_{n}

is the initial segment of

X

of length

n

. As a consequence, if

g

is any computable upper bound on the initial segment prefix-free complexity of

X

, then

X

is computable from an algorithmically random

Y

with oracle-use at most

g

. Alternatively (making no use of such a computable bound

g

) one can achieve an oracle-use bounded above by

K (X u p h a r p o o n r i g h t_{n}) + l o g n

. This provides a strong analogue of Shannon's source coding theorem for algorithmic information theory.

Cited in

(5)

This page was built for publication: Compression of Data Streams Down to Their Information Content

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224086)