  The ability to find short representations, i.e. to compress data, is crucial
for many intelligent systems. We present a theory of incremental compression
showing that arbitrary data strings, that can be described by a set of
features, can be compressed by searching for those features incrementally,
which results in a partition of the information content of the string into a
complete set of pairwise independent pieces. The description length of this
partition turns out to be close to optimal in terms of the Kolmogorov
complexity of the string. Exploiting this decomposition, we introduce ALICE - a
computable ALgorithm for Incremental ComprEssion - and derive an expression for
its time complexity. Finally, we show that our concept of a feature is closely
related to Martin-L\"of randomness tests, thereby formalizing the meaning of
"property" for computable objects.
