计算二进制字符串的 Lempel-Ziv (LZ) 复杂度（也称为序列复杂度）

Question

我需要计算二进制字符串的 LZ 复杂度。 LZ 复杂度是从开始到结束查看流时遇到的差异子串的数量。例如：

s = 1001111011000010

在不同子串中标记序列复杂度 c(s) = 6： s = 1 / 0 / 01 / 1110 / 1100 / 0010 /

有人可以指导我找到一个简单的解决方案吗？我确信对于这个众所周知的问题应该有一些非常直接的实现，但我很难找到它们。可以简单地通过构建后缀树或类似的东西来完成吗？如果是，具体如何？我该怎么办？

有人知道任何 c/c++ 源代码来完成这项任务吗？

提前致谢。

澄清答案中建议的树的构造。这棵树看起来像这样吗？

         o
       /   \
      o     o
     / \   / \
    o   o o   o
       /     /
      o     o

Answer 1

@Arash 和 @Sanchit Gupta：您可能对 LZ76 复杂性和 LZ78 复杂性感到困惑。 Arash 指的是 LZ76 复杂度，另一种是 LZ78 复杂度。您可以参考论文“Estimating the Entropy Rate of Spike Trains via Lempel-Ziv Complexity”的第3节。

Answer 2

下面是如何使用树计算 LZ 复杂度的快速示例。为了方便起见 - 我的；不是你的 - 这段代码实现了一个固定大小的预分配树，并且是为什么 void* 指针难以使用且难以维护的一个主要示例。按原样交出这段代码，你的讲师可能会朝你的脸开枪:)

#include <stdlib.h>
#include <stdio.h>

int LZComplexity(char *p_binarySequence, int p_maxTreeNodes)
{
 void **patternTree;
 void **currentNode;
 void **nextFreeNode;
 int nodeCount;
 int sequenceIndex;
 int currentDigit;

 nodeCount = 0;
 patternTree = malloc(sizeof(void*) * (p_maxTreeNodes << 1));
 currentNode = patternTree;
 nextFreeNode = patternTree + (sizeof(void*) << 1);
 currentNode[0] = NULL;
 currentNode[1] = NULL;
 sequenceIndex = 0;

 while (p_binarySequence[sequenceIndex])
 {
  currentDigit = p_binarySequence[sequenceIndex] - 48;
  if (NULL == currentNode[currentDigit])
  {
   currentNode[currentDigit] = nextFreeNode;
   nextFreeNode[0] = NULL;
   nextFreeNode[1] = NULL;
   nextFreeNode += (sizeof(void*) << 1);
   currentNode = patternTree;
   nodeCount++;
  }
  else
  {
   currentNode = currentNode[currentDigit];
  }
  sequenceIndex++;
 }

 free(patternTree);
 return nodeCount;
}


int main(int argc, char *argv[])
{
 printf("%u\n", LZComplexity("10100101001011101011", 1000));
 return 0;
}

Answer 3

1 0 01 11 10 110 00 010
序列的复杂度为 8，因为分区是 8 而不是 6 - 1/0/01/11/10/110/00/010

Answer 4

Guillermo Valle 有一个实现，可以生成正确的答案（与当前的维基百科代码不同）。

例如，

0001 的复杂度为 2：0 001

010 的复杂度为 3：0 1 0

Answer 5

创建一棵二叉树，其中左为 0，右为 1。对于每一位，尝试查找树中的序列。如果存在，连接下一点，冲洗，重复。如果不存在，请将其添加到树中并继续。 LZ 复杂度是树中路径的总数（不仅仅是叶节点数）。

顺便问一下，这是作业吗？

Answer 6

这可能与您相关。是并行实现
计算 LZ 复杂度的 LZMP 算法
在 CUDA 中并在 nVidia GPU 上运行。

http://www.ariel.ac.il/sites/ratsaby/代码/LZMP.zip

Answer 7

这在 Python 中应该可以解决问题（来自：Kaspar、F. Schuster、H.时空模式复杂性的轻松计算测量。物理评论 A，第 36 卷，第 2 期，第 842 页。）

#!/usr/bin/python


def lz_complexity(s):
    i, k, l = 0, 1, 1
    k_max = 1
    n = len(s) - 1
    c = 1
    while True:
        if s[i + k - 1] == s[l + k - 1]:
            k = k + 1
            if l + k >= n - 1:
                c = c + 1
                break
        else:
            if k > k_max:
               k_max = k
            i = i + 1
            if i == l:
                c = c + 1
                l = l + k_max
                if l + 1 > n:
                    break
                else:
                    i = 0
                    k = 1
                    k_max = 1
            else:
                k = 1
    return c


def main():
    lz = lz_complexity('1001111011000010')
    assert lz == 6 
    print lz


if __name__ == '__main__':

    main()