algorithm - 计算二进制字符串的 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

下面是一个快速示例，说明如何使用树计算 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;
}