INFORMATICA - COMPRESSIONE DI KOLMOGOROV

Considerando una sequenza numerica binaria finita:
S = 011011011111001101010101111001101011...011
poniamo che M sia un compressore di S, ossia un algoritmo che in un numero finito di passi genera S e la cui dimensione in bit LENGTH(M) sia inferiore alla lunghezza di S, LENGTH(S) (a tutti gli effetti M potrebbe sostituire S dato che la rigenera a perdita nulla).

Se si considera la complessità di Kolmogorov K(M) del compressore M si può sicuramente dire che la stringa binaria S può essere compressa con M fino alla dimensione minima K(M).

La complessità di Kolmogorov K(S) della stringa S è la complessità di Kolmogorov K(M') dove M' è il compressore minimo di S (ossia per qualsiasi compressore M: K(M)>K(M')). Si tratta quindi della dimensione in bit dell'algoritmo minimo che genera S.

Si noti che esiste almeno una M (l'algoritmo Ms che riproduce pedissequamente la sequenza stessa S) quindi K(Ms) = LENGTH(S)+h (h costante) è finita per definizione da cui il limite superiore di K(S) è K(Ms).

K(S) non può essere nullo ma sempre maggiore o uguale ad 1.

K(S) è la "reale" quantità di informazione contenuta in S e quindi S non potrà mai essere ridotta per compressione (senza perdita) ad un numero di bit inferiore a K(S).

marcomattiucci.it

Informatica:

Sistemi complessi: