Entropies defined by parsed algorithms
Loading...
Date
2003
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
Abstract
Common deterministic measures of the information content of symbolic strings revolve
around the resources used in describing or parsing the string. The well known and successful
Lempel-Ziv parsing process is described briefly, and compared to the lessor known Titchener
parsing process that might have certain theoretical advantages in the study of the nature of
deterministic information in strings. Common to the two methods we find that the maximal
complexity is asymptotic to hn/ log n, where h is a probabilistic entropy and n is the length
of the string. By considering a generic parsing process that can be used to define string
complexity, it is shown that this complexity bound appears as a consequence of the counting
of unique words, rather than being a result specific to any particular parsing process.
Description
Keywords
Parsing process
Citation
Mills, B.I. (2003), Entropies defined by parsed algorithms, Research Letters in the Information and Mathematical Sciences, 5, 17-22