基于使用Python的Lempel-Ziv算法的熵估计器

Question

该函数允许估计时间序列的熵。它基于Lempel-Ziv压缩算法。对于长度为n的时间序列，熵估计为：

E =（1 / n SUM_i L_i）^ - 1 ln（n）

其中L_i是从位置i开始的最短子串的长度，其先前不从位置1到i-1出现。当n接近无穷大时，估计的熵收敛于时间序列的实熵。

MATLAB函数中已经有了一个实现：https://cn.mathworks.com/matlabcentral/fileexchange/51042-entropy-estimator-based-on-the-lempel-ziv-algorithm?s_tid=prof_contriblnk

我想在Python中实现，我这样做：

def contains(small, big):
    for i in range(len(big)-len(small)+1):
        if big[i:i+len(small)] == small:
            return True
    return False

def actual_entropy(l):
    n = len(l)
    sequence = [l[0]]
    sum_gamma = 0

    for i in range(1, n):
        for j in range(i+1, n+1):
            s = l[i:j]
            if contains(s, sequence) != True:
                sum_gamma += len(s)
                sequence.append(l[i])
                break

    ae = 1 / (sum_gamma / n ) * math.log(n)            
    return ae

但是，当数据量越来越大时，我发现计算速度太慢。例如，我使用23832个元素的列表作为输入，消耗的时间是这样的:(数据可以找到here）

0-1000: 1.7068431377410889 s
1000-2000: 18.561192989349365 s
2000-3000: 84.82257103919983 s
3000-4000: 243.5819959640503 s
...

我有数千个这样的列表要计算，这么长时间是难以忍受的。我应该如何优化此功能并使其更快地工作？

Answer 1

我玩了一下，尝试了另一种来自StackOverflow上的thread的不同方法。这是我提出的代码：

def contains(small, big):
    try:
        big.tostring().index(small.tostring())//big.itemsize
        return True
    except ValueError:
        return False

def actual_entropy(l):
    n = len(l)
    sum_gamma = 0

    for i in range(1, n):
        sequence = l[:i]

        for j in range(i+1, n+1):
            s = l[i:j]
            if contains(s, sequence) != True:
                sum_gamma += len(s)
                break

    ae = 1 / (sum_gamma / n) * math.log(n)
    return ae

有趣的是，将numpy数组转换为字符串比直接使用字符串更快。我的机器上的代码与您提供的数据的非常粗略的基准是：

   N:  my code - your code
1000:   0.039s -    1.039s
2000:   0.266s -   18.490s
3000:   0.979s -   74.761s
4000:   2.891s -  285.488s

如果并行化外部循环，您可以更快地实现这一点。