Count the distinct phrases a sequence needs to build itself

An algorithmic rather than statistical notion of randomness: a sequence is complex when it cannot be assembled cheaply from its own past. A periodic signal parses into a handful of phrases however long it runs; noise needs a new phrase almost every step. No distribution and no stationarity required.

Usage

Lzcomp(y)

Arguments

y

Sequence; values compared for equality.

Value

List with estimate, normalized, alphabet, n.

Details

Formula: C(s) is the number of phrases in the LZ76 exhaustive parse; normalised, C(s) log_a(n) / n.

References

Lempel, A. & Ziv, J. (1976). IEEE Trans Inform Theory 22:75-81.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Lzcomp(V)
#> $estimate
#> [1] 8
#> 
#> $normalized
#> [1] 1
#> 
#> $alphabet
#> [1] 8
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Lempel-Ziv complexity, LZ76 parse"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"