Measuring complexity with zippers
Published 1 January 2006
Baronchelli, A, Caglioti, E, Loreto, V
Citations17
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Physics concepts have often been borrowed and independently developed by other fields of science. In this perspective a significant example is that of entropy in Information Theory. The aim of this paper is to provide a short and pedagogical introduction to the use of data compression techniques for the estimate of entropy and other relevant quantities in Information Theory and Algorithmic Information Theory. We consider in particular the LZ77 algorithm as case study and discuss how a zipper can be used for information extraction.
Keywords
Computer Science
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
IEEE Transactions on Information TheoryA universal algorithm for sequential data compression
5,467 Citations1977J. Ziv, A. Lempel
The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable- to-block codes designed to match a completely specified source.
Information and ControlA formal theory of inductive inference. Part II
1,786 Citations1964Ray J. Solomonoff
Four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction.
Information and ControlA formal theory of inductive inference. Part I
1,149 Citations1964Ray J. Solomonoff
IEEE Transactions on Information TheoryThe Similarity Metric
1,059 Citations2004Ming Li, Daniel Chen +3 more
A new "normalized information distance" is proposed, based on the noncomputable notion of Kolmogorov complexity, and it is demonstrated that it is a metric and called the similarity metric.
Journal of the ACMOn the Length of Programs for Computing Finite Binary Sequences
912 Citations1966Gregory J. Chaitin
An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed to study the use of Turing machines for calculating finite binary sequences.
Cambridge University Press eBooksStatistical Field Theory
891 Citations1989C. Itzykson, Jean-Michel Drouffe
Physical Review LettersLanguage Trees and Zipping
370 Citations2002Dario Benedetto, Emanuele Caglioti +1 more
BioinformaticsA new sequence distance measure for phylogenetic tree construction
351 Citations2003Hasan H. Otu, Khalid Sayood
A new sequence distance measure based on the relative information between the sequences using Lempel-Ziv complexity is proposed, which can be used to construct phylogenetic trees.
Chaos An Interdisciplinary Journal of Nonlinear ScienceEntropy estimation of symbol sequences
330 Citations1996Thomas Schürmann, Peter Grassberger
Algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations are considered, and a scaling law is proposed for extrapolation from finite sample lengths.
Springer series in solid-state sciencesProducts of Random Matrices
290 Citations1993A. Crisanti, Giovanni Paladin +1 more
IEEE Transactions on Information TheoryA measure of relative entropy between individual sequences with application to universal classification
152 Citations1993J. Ziv, Neri Merhav
Proceedings of the IEEEThe sliding-window Lempel-Ziv algorithm is asymptotically optimal
95 Citations1994A.D. Wyner, J. Ziv
Physica D Nonlinear PhenomenaData compression and learning in time sequences analysis
43 Citations2003Andrea Puglisi, Dario Benedetto +3 more
The existence of a scaling function (the “learning function”) is shown which rules the way in which the compression algorithm learns a sequence B after having compressed a sequence A and it turns out that there exists a cross-over length for the sequence B.
Journal of Statistical Mechanics Theory and ExperimentArtificial sequences and complexity measures
7 Citations2005Andrea Baronchelli, Emanuele Caglioti +1 more
A class of methods which use in a crucial way data compression techniques in order to define a measure of remoteness and distance between pairs of sequences of characters based on their relative information content are introduced.