Data Compression Approach to Sequence Analysis
Vittorio Loreto · AIP conference proceedings · 2003
In this short note we review the concept of complexity in the context of Information Theory (Shannon Entropy) and Algorithmic Complexity Theory (Chaitin‐Kolmogorov Complexity), remarking its relation with data compression analysis. We recall in particular that compression schemes (or “zippers”) allow for an approximate measuring of the complexity of a sequence of symbols. Moreover it has recently been shown that zippers allow for a definition of remoteness, in terms of complexity, between two strings of characters. We discuss how these ideas can be used for the implementation of suitable data‐compression oriented algorithms for information extraction and we give two specific examples.