Artificial sequences and complexity measures

DOI10.1088/1742-5468/2005/04/P04002zbMATH Open1456.94030arXivcond-mat/0403233OpenAlexW3099675966MaRDI QIDQ4968837FDOQ4968837

Authors: Andrea Baronchelli, Emanuele Caglioti, Vittorio Loreto 

Publication date: 9 July 2019

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Abstract: In this paper we exploit concepts of information theory to address the fundamental problem of identifying and defining the most suitable tools to extract, in a automatic and agnostic way, information from a generic string of characters. We introduce in particular 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 (e.g. texts) based on their relative information content. We also discuss in detail how specific features of data compression techniques could be used to introduce the notion of dictionary of a given sequence and of Artificial Text and we show how these new tools can be used for information extraction purposes. We point out the versatility and generality of our method that applies to any kind of corpora of character strings independently of the type of coding behind them. We consider as a case study linguistic motivated problems and we present results for automatic language recognition, authorship attribution and self consistent-classification.

Full work available at URL: https://arxiv.org/abs/cond-mat/0403233

Recommendations

• Information Capacity of Symbol Sequences
• scientific article; zbMATH DE number 6751363
• Data compression and learning in time sequences analysis
• Text and hypertext compression
• Information-theoretic method for classification of texts

zbMATH Keywords

analysis of algorithmsnew applications of statistical mechanicssource and channel coding

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Information theory (general) (94A15) Measures of information, entropy (94A17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Time-dependent statistical mechanics (dynamic and nonequilibrium) (82C99)

Cites Work

• Title not available (Why is that?)
• On Information and Sufficiency
• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ergodic theory of chaos and strange attractors
• An Introduction to Symbolic Dynamics and Coding
• A formal theory of inductive inference. Part I
• Analysis of symbolic sequences using the Jensen-Shannon divergence
• A formal theory of inductive inference. Part II
• Clustering by Compression
• The Similarity Metric
• Information distance
• A new challenge for compression algorithms: Genetic sequences
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• On the Length of Programs for Computing Finite Binary Sequences
• A measure of relative entropy between individual sequences with application to universal classification
• Fifty years of Shannon theory
• Entropy estimation of symbol sequences
• Title not available (Why is that?)
• Dynamical systems and computable information
• Predictability: a way to characterize complexity
• Using literal and grammatical statistics for authorship attribution
• Data compression and learning in time sequences analysis
• Title not available (Why is that?)
• Nonparametric entropy estimation for stationary processes and random fields, with applications to English text

Cited In (3)

• Non-sequential recursive pair substitution: some rigorous results
• Information-theoretic method for classification of texts
• Sequences With High Nonlinear Complexity

Uses Software

• PHYLIP

This page was built for publication: Artificial sequences and complexity measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968837)