algorithm - 这两种算法都是 LZSS 的有效实现吗？

Question

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

1. Initialize dictionary of size 2^n
2. While output is less than known output size:
   1. Read flag
   2. If the flag is set, output literal byte (and append it at the end of dictionary)
   3. If the flag is not set:
      1. Read length and look behind position
      2. Transcribe length bytes from the dictionary at look behind position to the output and at the end of dictionary.

问题在于，实现遵循两种如何对标志 进行编码的流派。第一个将输入视为位序列:

2. (...)
   1. Read flag as one bit
   2. If it's set, read literal byte as 8 unaligned bits
   3. If it's not set, read length and position as n and m unaligned bits

这涉及大量的位移操作。

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

2. (...)
   1. Read 8 flags at once by reading one byte. For each of these 8 flags:
      1. If it's set, read literal as aligned byte
      2. If it's not set, read length and position as aligned bytes (deriving the specific values from the fetched bytes involves some bit operations, but it's nowhere as expensive as the first version.)

我的问题是:这些都是有效的 LZSS 实现，还是我认为这些算法有误？它们有什么已知的名字吗？

Answer 1

它们实际上是 LZSS 的变体，因为它们都使用一位来决定文字与匹配。更一般地说，它们是 LZ77 上的变体。

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

lz4 (一个特定的算法，而不是一个系列)以不同的方式处理字节对齐，对 number 的文字进行编码，它后面必须跟一个匹配项。带有文字数量的第一个字节也有部分距离。文字是字节对齐的，文字后面的偏移量和其余距离也是如此。