8

背景：我在 C++ 上实现了一个通用 LZSS 后端（可在此处获得。我在这个版本中使用的匹配算法非常简单，因为它最初是为了压缩相对较小的文件（最多 64kB），用于相对古老的硬件（特别是，Mega Drive/Sega Genesis，其中 64kB 是整个主 RAM）。

然而，在我的实现中，一些文件的压缩时间太长了，大约几分钟。原因有两个：天真的匹配算法花费了大部分时间，但这特别是因为我从文件中构造了一个压缩图以实现最佳压缩。查看分析器，大部分时间都花在寻找匹配上，甚至使结果图的二次大小相形见绌。

一段时间以来，我一直在研究几种可能的替代品；引起我注意的是使用多层后缀树的字典符号灵活解析。多层部分很重要，因为我感兴趣的 LZSS 变体之一对（位置、长度）使用可变大小的编码。

我当前的实现允许滑动窗口中的匹配项与前瞻缓冲区重叠，因此该输入：

aaaaaaaaaaaaaaaa

可以直接编码为

(0,'a')(1,0,15)

代替

(0,'a')(1,0,1)(1,0,2)(1,0,4)(1,0,8)

这里，(0,'a') 表示将字符“a”编码为文字，而 (1,n,m) 表示“从位置 n 复制 m 个字符”。

问题：说了这么多，这是我的问题：我在后缀树上找到的每个资源似乎都暗示它们无法处理重叠的情况，而只允许您找到不重叠的匹配项。当涉及到后缀树时，研究论文、书籍甚至一些实现都给出了没有重叠的压缩示例，就好像它们是完美的压缩一样（我会链接到其中的一些，但我的声誉不允许这样做）。他们中的一些人甚至提到在描述基本压缩方案时重叠可能很有用，但在讨论后缀树时却奇怪地沉默了。

由于无论如何都需要扩充后缀树以存储偏移信息，因此这似乎是一个可以在查找匹配项时检查的属性——您将过滤掉从前瞻缓冲区开始的任何匹配项。并且树的构造/更新方式意味着，如果一条边将您带到与从前瞻开始的匹配对应的节点，则您将返回前一个节点，因为任何进一步的后代也将在前瞻中缓冲。

我的方法是错误的还是不正确的？是否有 LZ77/LZSS 的实现或讨论，其后缀树提到匹配与前瞻缓冲区重叠？

4

1 回答 1

3

据我了解，给定一个后缀树，我们（大致）对计算每个后缀 S 感兴趣，较长的后缀与 S 具有最长的公共前缀。

将每个树节点的引用添加到具有最长后缀的后代叶子（使用 DFS 的线性时间）。从每片叶子开始，向根部走，检查新的引用，如果找到更长的后缀就停下来。后一步的运行时间是线性的，因为每个树边都被检查一次。

不幸的是，有界窗口的生活更加困难。我们不是传播一个引用，而是传播几个。为了计算从节点引用的后缀集，我们按长度排序将它们合并。然后，只要我们有长度为 x > y > z 的后缀，如果 x - z < 8192（例如），那么我们可以删除 y，因为所有三个对于当前节点是最叶共同祖先的所有后缀都同样适用，并且如果 y 在窗口中，则 x 或 z 是。由于窗口占整个文件的很大一部分，因此每个节点最多会有几个引用。

如果您想回顾尽可能短的距离，那么有一个 O(n log^2 n) 时间算法（可能通过各种难以实现的魔法改进为 O(n log n)）。在算法过程中，我们为每个节点构造一个按长度计算后代后缀的二叉搜索树，然后进行次长查找。要从其子节点构建节点的树，请从最大的子树开始并插入其他节点的元素。通过重路径参数，每个长度都被插入 O(log n) 次。

于 2015-07-10T22:41:46.713 回答