Entropies defined by parsed algorithms

Loading...
Thumbnail Image
Date
2003
DOI
Open Access Location
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