这两种算法都是LZSS的有效实现吗?

Question

我从事逆向工程，经常碰到各种各样的解压缩算法。大多数时候，它是LZSS，就像维基百科描述的那样:

1. 初始化大小为2^n的字典
2. 当输出小于已知输出大小时:
   读
   1. 标记
   2. 如果设置了标志，则输出字面值字节(并将其附加在字典的末尾)
   3. 如果标志未设置:
      1. 读取长度和查看位置
      2. 将长度字节从字典位置后面的转录到输出和字典末尾。

问题是实现遵循了如何编码标志的两种学派。第一个将输入视为位序列:

(…)

1. 读取标志为1位
2. 如果设置了，读取字面值字节为8个未对齐的位
3. 如果没有设置，读取长度和位置为n和m未对齐的位

这涉及到大量的位移位操作。

另一个通过仅对标志存储使用位操作节省了一点CPU时间，而字面值字节，长度和位置是从对齐的输入字节派生的。为了实现这一点，它通过提前获取几个标志来打破线性。所以算法是这样修改的:

(…)

1. 通过读取一个字节一次读取8个标志。对于这8个标志中的每一个:
   1. 如果设置了，读取作为对齐字节的字面值
   2. 如果没有设置，读取长度和位置作为对齐的字节(从获取的字节中获得特定的值涉及一些位操作，但它没有第一个版本那么昂贵)。

我的问题是:这些都是有效的LZSS实现，还是我识别这些算法错误?他们有已知的名字吗?

Answer 1

它们实际上是LZSS的变体，因为它们都使用一位来决定是literal还是match。更一般地说，它们是LZ77的变体。

Deflate也是LZ77的一个变体，它不使用整位来表示literal和match。相反，deflate对于文字和长度的组合只有一个代码，因此该代码隐式地确定下一个内容是文字还是匹配。长度码后跟一个单独的距离码。

lz4(一个特定的算法，而不是一个族)以不同的方式处理字节对齐，对字面值的数字进行编码，后面必须有一个匹配。具有字面值数目的第一个字节也具有部分距离。字面值是按字节对齐的，就像字面值后面的偏移量和其余的距离一样。