背景:我在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的实现或讨论,后缀树提到匹配重叠前瞻缓冲区？
LZSS有人可以解释一下和算法之间的区别吗LZ77？我在网上查了几个小时，但找不到区别。我找到了LZ77算法并且了解了它的实现。
但是，与 有何LZSS不同LZ77？假设我们有一个字符串，"abracadabra"如何以LZSS不同的方式压缩它LZ77？有我可以遵循的 C 伪代码吗？
感谢您的时间！
我试图找到 LZ77 的正确实现，LZ77是 1977 年论文中的原始著名算法。我发现有许多不同的实现会产生不同的输出，但仍标记为 LZ77。例如，有些使用哈希表，在更“官方”的算法（如 LZRW 或 LZJB）中使用的东西。所以我很困惑。
我测试过的一些实现：
据我所知，没有人使用任何后处理编码，例如霍夫曼等。
我用来压缩的文本：
Oho! Oho! Rise up, O Teti!
Take your head, collect your bones,
Gather your limbs, shake the earth from your flesh!
Take your bread that rots not, your beer that sours not,
Stand at …我想压缩.txt包含yyyy-mm-dd hh:mm:ss格式日期和有时在不同行中重复的英语单词的文件。
我阅读了一些有关压缩算法的文章，发现在我的例子中基于字典的编码比基于熵的编码更好。因为我想自己实现算法，所以我需要一些不太复杂的东西。所以我关注了LZW和LZ77，但不能在它们之间做出选择，因为我发现的文章结论是矛盾的。根据一些文章，LZW 具有更好的压缩比，而根据其他文章，领先者是 LZ77。所以问题是，对于我的情况，哪一个最有可能更好？是否有更易于实现的算法可以满足我的目的？