问题标签 [lempel-ziv-76]

有人可以向我解释 Lempel-Ziv 76 的复杂性吗？我的印象是您使用字典中字符串的第一个字母进行初始化，然后检查后续块是否存在于前一个子字符串中，每次找到子字符串时都会增加一个字母。如果前一个子字符串中不存在子字符串，则该子字符串称为块，下一个字母成为要搜索的下一个子字符串。

例如，

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。谢谢！

我有一个问题 - 我被介绍给 Ziv-Lempel 的一个版本，它只编码大小为 3 或更长的重复（不编码 1 或 2 个字符的重复 - 字符本身被放置到编码字符串而不是 (m ,k) 值)。有人问我是否可以提高 ziv Lempel 编码效率（就编码字符串的长度而言 - 而不是时间复杂度）。

我认为就编码字符串的长度而言 - 可能存在以下情况：不在位置 p 编码 3 长度重复，而是编码从位置 p+1 或 p+2 开始的重复可能会产生更好的结果 - 这也出现在我读到的理论中：我添加了一张相关段落的照片，仅说明了这一点（但没有给出示例）。到目前为止，我设法找到的每个示例都是编码长度为 3 的重复的代码也可以检测到的示例。

这是一段谈到存在这样一个文本的事实：

到目前为止，我们描述的压缩算法是贪婪的：任何长度为 3 或更多的重复都会立即报告并使用。有时这不是最优的：我们可以在 p 位置重复一个 [ m 1 _, k 1 _]，在p +1 或p +2位置重复一个 [ m ₂ , k ₂ ] ，其中k ₁ << k ₂。因此，非贪心算法可能会导致改进的压缩。

（原图）

在 lempel-ziv 解码方法中，我得到 indexError 这是我的代码，我知道大小将为 3，而 len(LT) 仅为 2。但我只是将伪代码转换为 python 代码。

这是错误消息：

这对谷歌来说是一个非常困难的问题。我不是在寻找 gzip 或 Zip 或放气。我想使用的算法称为“压缩”，但这并不意味着我一般都在尝试实现压缩。我正在寻找一个特定的算法。

我正在寻找compress类 Unix 系统中命令行工具使用的自适应 Lempel-Ziv 算法。我正在寻找 HTTP 说您在收到Content-Encoding: compress标头时应该使用的算法。man compress这是您在键入POSIX shell时看到的算法，在此 Wikipedia 文章中。

我了解这种压缩算法非常古老，几乎所有实际用途都已被 gzip、Zip、deflate 等取代。但是我正在用 C++ 编写一个服务器作为一个宠物项目，而 IANA 将这个 Unix“压缩”算法指定为每个服务器应该支持的编码之一。

该compress实用程序长期以来一直是 Unix shell 的一部分 - 从 POSIX 之前开始 - 我很难相信没有标准的 C 语言实现。我可以使用调用system或exec在 shell 中进行压缩（创建另一个进程……呃），但这比将算法编译到我的可执行文件中效率要低得多。

该算法是否有标准的 C 实现/库？

此函数允许估计时间序列的熵。它基于 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 中实现，我是这样做的：

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

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

LZ78 的一个快速但足够的定义来自维基百科：

每个字典条目的格式为 dictionary[...] = {index, character}，其中 index 是前一个字典条目的索引，而 character 附加到由 dictionary[index] 表示的字符串中。例如，“abc”将按如下方式存储（以相反的顺序）：dictionary[k] = {j, 'c'}, dictionary[j] = {i, 'b'}, dictionary[i] = {0 , 'a'}，其中索引 0 指定字符串的第一个字符。该算法初始化最后一个匹配索引= 0 和下一个可用索引= 1。

对于输入流的每个字符，在字典中搜索匹配项：{ last matching index , character}。

• 如果找到匹配项，则将最后一个匹配索引设置为匹配条目的索引，并且不输出任何内容。

• 如果没有找到匹配项，则创建一个新的字典条目：dictionary[ next available index ] = { last matching index , character}，算法输出最后一个匹配索引，后跟字符，然后重置最后一个匹配索引= 0 和递增下一个可用索引。一旦字典已满，就不再添加条目。

• 当到达输入流的末尾时，算法输出最后一个匹配索引。

在考虑实施时，最后一句话对我来说是一个严重的问题。好的，输出流的形式是 (index,letter)...(index,letter)(index)。

但是在一般情况下，由于任何实现都需要使用字节（或类似的，这并不重要），我们有一个填充。那么如何让解码器不被填充所迷惑呢？

我知道存在一些技巧，例如，如果我有原始字符串的总长度，那么很容易停止解码器。但是，在这种情况下，LZ78 不再是流压缩器。另一个例子是扩展字母表，使其在终端情况下具有特殊的字符，但这将至少多使用一位来进行字母编码，这对我来说是不可接受的。同样，如果字符集包含所有可能的字节，则没有问题，因为任何输出步骤都会生成至少 8 位（索引+字母），因此很容易知道我们是否在末尾。

但在 LZ78 的一般情况下，您可以使用任何字母表。例如，如果字母表只有两个元素 0 和 1，我无法理解如何不被填充所迷惑。我的意思是如何区分（索引，填充）和（索引，字母）？

如何区分00和000的编码？

• (0,0)(1)+填充（原始：001+填充）
• (0,0)(1,0)+填充（原始：0010+填充）

我错过了一个非常简单的观点吗？

请注意，即使是 Lempel & Ziv 的原始论文，也没有提及这一点。我发现和分析的所有实现都使用了我列出的技巧之一（或变体）。

C语言/压缩算法菜鸟在这里，提前道歉。

我正在研究基于 Lempel-Ziv 的 utf-16 字符串压缩算法，如此处所述http://www.unicode.org/notes/tn31/

根据实现（https://www.unicode.org/notes/tn31/#Performance），一个 1014 字节的字符串应该被压缩到大约 560（大约 60%）。

但是我下载了示例 c ( https://www.unicode.org/notes/tn31/utf16_compressor.tar.gz ) 代码并测试了压缩长度为 1290 的字符串（我添加了一个打印语句来打印输入和输出长度）但压缩后的输出长度为3018。是我遗漏了什么还是我误解了输出长度？从代码来看，压缩函数的输出缓冲区是一个无符号字符（1 字节）数组，因此意味着 3018 实际上是 3018 字节？

我需要创建一个 .Z（压缩）文件，因为接收者希望使用解压缩实用程序读取它。但我无法在我的 Linux 主机上安装压缩包。

有没有办法使用 gzip 命令获取压缩的 .Z 文件（使用自适应 Lempel-Ziv 编码）？

正在研究 lempel-ziv 减压方法，我们遇到了一些麻烦。像下面这样的文本行不会正确解压。

它变得像下面这样，把下一行弄得一团糟。

你看到代码中有任何错误吗？