Lempel-Ziv Complexity

Problem

Estimate Lempel-Ziv complexity. Binarize the series with 1 when x is above the mean and 0 otherwise, parse the string into distinct phrases, and return the phrase count times log2(n) divided by n.

Return 0.0 for fewer than two points.

Hint

Regular repeating patterns are compressible, so complexity is low.

Test cases

case 1

in: [[1,2,1,2,1,2]]

expected: 1.292481250360578

case 2

in: [[1,1,1,1]]

expected: 1

case 3

in: [[1,2,3,4,5,6,7,8]]

expected: 1.125

case 4

in: [[0,1,0,1,0,1,0,1]]

expected: 1.125

Starter codePython

import math
def lempel_ziv_complexity(series):
    # Your code here
    pass

4 test cases · run your code against them in the editor