背景:我有一个通用LZSS后端的C++实现(可在此处找到)。我在此版本中使用的匹配算法非常简单,因为它最初是为了压缩相对较小的文件(最多64kB)而设计的,用于相对古老的硬件(特别是Mega Drive/Sega Genesis,在其中64kB是主RAM的全部内容)。
然而,我的实现有些文件需要花费太长时间进行压缩,大约几分钟。原因是双重的:朴素的匹配算法占用了大部分时间,但这是因为我构建了一个压缩图来实现最佳压缩。查看分析器,大部分时间都花在寻找匹配上,甚至超过了结果图形的平方大小。
我已经研究了几个潜在的替代品一段时间了;其中一个引起了我的注意:使用多层后缀树的字典符号灵活解析。多层部分很重要,因为我感兴趣的LZSS变体之一使用可变长度编码来表示(位置,长度)。
我的当前实现允许滑动窗口中的匹配与前瞻缓冲区重叠,因此,这个输入:
可以直接编码为
然而,我的实现有些文件需要花费太长时间进行压缩,大约几分钟。原因是双重的:朴素的匹配算法占用了大部分时间,但这是因为我构建了一个压缩图来实现最佳压缩。查看分析器,大部分时间都花在寻找匹配上,甚至超过了结果图形的平方大小。
我已经研究了几个潜在的替代品一段时间了;其中一个引起了我的注意:使用多层后缀树的字典符号灵活解析。多层部分很重要,因为我感兴趣的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与后缀树的方法,提到了匹配重叠前视缓冲区?