有人可以向我解释 Lempel-Ziv 76 的复杂性吗？我的印象是您使用字典中字符串的第一个字母进行初始化，然后检查后续块是否存在于前一个子字符串中，每次找到子字符串时都会增加一个字母。如果前一个子字符串中不存在子字符串，则该子字符串称为块，下一个字母成为要搜索的下一个子字符串。
例如，
01011010001101110010
0|1
因为 1 不在 0 中，所以我们得到0|1|0
因为 0 在 01 中，所以我们得到0|1|01
因为 01 在 01 中，所以我们得到0|1|011|0
因为 0 在 01011 中，所以我们得到0|1|011|01
因为 01 在 01011 中，所以我们得到0|1|011|010
因为 010 在 01011 中，所以我们得到0|1|011|0100|0
依此类推，直到我们0|1|011|0100|011011|1001|0得到
如有必要，最后一个字母可以重复。
我究竟做错了什么？因为有人告诉我，对于字符串 1111111，分解为 1|111111。谢谢！
我同意你的分解：
01011010001101110010 -> 0.1.011.0100.011011.1001.0
我也相信你被告知的是正确的：
1111111 -> 1.111111
但是，您如何得出原始分解并不完全正确！因此对分解 1111111 感到困惑。我认为，根据您的推理：
1111111 -> 1.11.1111
我很确定这是不正确的。
对现有单词（块）序列的扩展并不像检查扩展之前是否显示为先前历史的子字符串那么简单。它归结为Lempel 和 Ziv 在他们的论文On the Complexity of Finite Sequences 中描述的扩展的可再现性概念（我假设这就是您正在研究的内容！）。形成一个扩展，使其成为不可复制的最短单词从以前的历史来看。他们描述的扩展的可再现性概念相当复杂，但归结为能够在以前的历史中找到一个起始位置，您可以从该起始位置顺序复制符号，到历史的结尾，形成扩展。
从您的原始序列中，假设符号的位置从 1 到 20。第一个符号本身始终是一个单词/块：
0。
下一个扩展不能从以前的历史中重现：
0. 1.
下一个扩展是：
0.1。011.
不能为 0 或 01 的原因如下： 0 可以从之前的历史中重现，通过从位置 1 复制一个符号到末尾；01 可通过将两个符号从位置 1 复制到末尾来重现；011 不可重现。
下一个扩展是：
0.1.011。0100。
0 可通过将一个符号从位置 1 复制到末尾来重现；01 可通过将两个符号从位置 1 复制到末尾来重现；010 可通过将三个符号从位置 1 复制到末尾来重现；0100 不可重现。
等等。
1111111的分解如下：第一个符号本身就是一个块：
1.
下一个扩展是：
1. 111111
1 可通过将一个符号从位置 1 复制到上一个历史记录的末尾来重现。通过将两个符号从位置 1 复制到末尾，可以重现图 11。这就是复杂的地方 - 在这种情况下，当您复制两个符号时，复制的源实际上延伸到了前一个历史记录的末尾！换句话说，您复制的第二个 1 实际上是将第一个 1 复制到 end 所产生的扩展的一部分。同样，由于这种递归复制过程，111、1111、11111、111111 都是可重现的。然而，由于我们现在已经到达原始序列的末尾，最后一个扩展被认为是 111111。
希望我的解释有点道理。
本文不同意你对算法的描述。根据论文，如果它与任何先前的分区都不匹配，则您有一个新分区。您不会像您所做的那样根据整个未分区的先前序列进行分区。因此，对于您的示例（我使用 . 而不是 | 进行分区，因为这样更易于阅读）：
01011010001101110010
分为：
0.1.01.10.100.011.0111.00.10
所以LZ76的重量是9（不是7）。
1111111
分为：
1.11.111.1
它们都提供了最终分区包含在前一个分区中的示例。因此，定义中的 < r 而不是 <= r。
我没有原始论文，所以我无法检查这篇论文是否弄错了。但是我怀疑他们错误地复制了原始论文中的定义。