c++ - 在具有后缀树的 LZ77/LZSS 上匹配重叠前瞻

Question

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

然而，在我的实现中，有些文件需要很长时间才能压缩，大约几分钟。原因有两个:朴素的匹配算法占用了大部分时间，但这种情况的发生特别是因为我从文件构建了一个压缩图以实现最佳压缩。查看分析器，大部分时间都花在寻找匹配项上，甚至使结果图的二次大小相形见绌。

一段时间以来，我一直在研究几种可能的替代品；引起我注意的一个是dictionary-symbolwise flexible parsing using multilayer suffix trees .多层部分很重要，因为我感兴趣的 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 的实现或讨论，其中后缀树提到匹配与超前缓冲区重叠？

Answer 1

据我了解，给定一个后缀树，我们有兴趣(粗略地)计算每个后缀 S，哪个较长的后缀与 S 具有最长的公共(public)前缀。

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

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

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