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.
Data compression approach to sequence analysis / A., Puglisi; Loreto, Vittorio. - 661:(2003), pp. 184-187. (Intervento presentato al convegno 7th Granada Conference on Modeling of Complex Systems tenutosi a GRANADA, SPAIN nel SEP 02-07, 2002) [10.1063/1.1571310].
Data compression approach to sequence analysis
LORETO, Vittorio
2003
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
