作者：
发布于 2013 年 2 月 23 日 (最后更新：2013 年 3 月 18 日)

LZW 文件压缩器

评分：4.2/5 (112 票)
*****

LZ 系列算法

Abraham Lempel 和 Jacob Ziv 在 1977 年和 1978 年分别发表了两种压缩算法：LZ77 和 LZ78。

Terry Welch 在 1984 年发表了 LZW 算法，作为对 LZ78 的改进。

LZW 只是原始 LZ 算法的众多衍生算法之一，其中更著名的是 LZSS (用于 RAR)、LZMA (用于 7z) 和 Deflate (用于 ZIP)。

本文介绍 LZW 是因为
  • 它易于理解和编写，并且
  • 它提供了不错的压缩率和速度，而且
  • 其专利已过期

目标

目标是实现一个 LZW 文件压缩器，并逐步改进它。

Alpha 版本
  • 版本 1 [ 跳转 ] [ 下载 ]
    直接但速度慢的实现。编码器使用普通映射。解码器使用字符串向量。

  • 版本 2 [ 跳转 ] [ 下载 ]
    更快的压缩。编码器使用哈希映射。解码器沿用版本 1。

  • 版本 3 [ 跳转 ] [ 下载 ]
    更快的压缩和解压缩。编码器和解码器都进行对映射，而不是字符串映射。

  • 版本 4 [ 跳转 ] [ 下载 ]
    更快的压缩和极快的解压缩。编码器使用自定义内存分配器。解码器经过优化。

  • 版本 5 [ 跳转 ] [ 下载 ]
    极快的压缩和解压缩。编码器使用基于向量的二叉搜索树。解码器沿用版本 4。

Beta 版本
  • 版本 6 [ 跳转 ] [ 下载 ]
    使用可变宽度编码。与版本 5 相比，它速度明显变慢，但压缩效果更好。

以上程序是命令行工具。它们的源代码作为 ZIP 存档附在本文章中。

备注
  • 编译时启用优化可以提高程序的性能。

  • 我目前使用 MinGW (GCC 4.7.2) 并通过运行以下命令进行编译：
    g++ -Wall -Wextra -pedantic -std=c++11 -O3 lzw_vX.cpp -o lzw_vX.exe

语言

源代码是用 C++11 编写的，即 C++ 语言标准的 2011 版。

为了成功编译本文章中的源代码片段以及附带的完整程序，您的 C++ 编译器必须支持 lambda 函数、基于范围的 for() 循环和初始化列表。

无损压缩与扩展

给定大小为 SD 的数据 D，目的是将其编码为大小为 SE 的数据 E，使得
  • SE < SD
  • E 可以解码为 D

如果 SE 小于 SD，则实现了压缩。
如果此外，原始数据 D 可以从 E 重构，则压缩是无损的。

备注
  • 压缩率计算公式为 SE / SD。

扩展是压缩的相反，其中 SE > SD。

之所以会发生扩展，是因为无损压缩算法在数学上不可能压缩所有文件。这可以通过计数论证来证明，您可以通过查看本文底部的链接了解更多信息。

一个简化的、粗略的例子 
Suppose we have a lossless compression algorithm LCA that can compress all files.
For simplicity, let's consider that the files to be compressed are made of bits.
A bit can only hold either 1 or 0.

Let's take all files consisting of at most two bits:

""    (empty file)
"00"
"01"
"10"
"11"
"0"
"1"

Now let's compress them:

LCA("")   = ""    // the empty file naturally compresses to itself
LCA("00") = "0"   // successfully compressed!
LCA("01") = "1"   // successfully compressed!
LCA("10") =       // uh-oh
LCA("11") =       // uh-oh
LCA("0")  =       // major uh-oh
LCA("1")  =       // major uh-oh

上面的例子表明，因为无损压缩算法需要为每个数据文件生成一个唯一的编码文件，所以并非所有数据文件都能被压缩——事实上，其中一些文件会被扩展。

例如，“0”可以压缩成什么？我们不能重用对 ""、“00” 或 “01” 的输出，因为那样解码器如何知道要解码哪个文件？

这是计数论证的关键：如果所有文件都可以被压缩，那么唯一的压缩文件总数将少于未压缩文件的数量，这意味着它们之间不存在一一对应的关系，这意味着压缩算法不是无损的。

熵与字典编码器

就我们而言，熵是数据不可预测性的度量。低熵数据倾向于具有重复序列。高熵数据倾向于随机。

字典编码器是一种利用低熵的无损压缩算法。它将数据序列与“字典”中的代码（占用空间更少）相关联。通过用相应的代码替换重复序列来实现压缩。替换的序列越长，其频率越高，压缩效果越好。

备注
  • 文本文件倾向于具有低熵。
  • 多媒体数据文件和存档倾向于具有高熵。

LZW 算法

LZW 是一种字典编码器。它从包含所有单字节序列的字典开始，将它们与代码相关联。在读取数据文件 DF 时，字典会使用多字节序列进行更新。编码文件 EF 将完全由代码组成。

为简单起见，字节序列将被称为“字符串”。

用于存储代码的类型将是 CodeType。

备注
  • 在 C++ 语言中，char 被定义为字节。

  • 在大多数计算机上，字节的宽度为八位。

  • 位可以保持 1 或 0 的值。

  • CodeType 可以是任何比字节更宽的类型。

  • 映射是一种数据结构，它将一个值“键”与另一个值“元素”相关联。

  • 数组是映射的一种特殊情况，其中数字代码（索引）与元素相关联，例如
    dictionary[14] == "cat"

  • 编码器的字典是一个将字符串与数字代码关联的映射，例如
    dictionary["cat"] == 14

编码器伪代码 
dictionary  : map of string to CodeType
S           : empty string
c           : byte
DF          : the data file
EF          : the encoded file

dictionary = entries for all strings consisting of a single, unique byte

while ( could read a new byte from DF into c )
{
    S = S + c       // append c to S

    if ( dictionary doesn't contain S )
    {
        dictionary[S] = next unused code
        // if the dictionary had entries for codes 0 to 17,
        // this would add an entry for code 18, with the key S

        S = S - $   // remove last byte from S
        write dictionary[S] to EF
        S = c       // S now contains only c
    }
}

if ( S isn't empty )
    write dictionary[S] to EF

编码器简化运行 
dictionary["a"] = 0
dictionary["b"] = 1

DF: "abababab"

while() begins
read 'a', S = "a", -
read 'b', S = "ab", dictionary["ab"] = 2, S = "a", EF: {0}, S = "b"
read 'a', S = "ba", dictionary["ba"] = 3, S = "b", EF: {0 1}, S = "a"
read 'b', S = "ab", -
read 'a', S = "aba", dictionary["aba"] = 4, S = "ab", EF: {0 1 2}, S = "a"
read 'b', S = "ab", -
read 'a', S = "aba", -
read 'b', S = "abab", dictionary["abab"] = 5, S = "aba", EF: {0 1 2 4}, S = "b"
while() ends

EF: {0 1 2 4 1}

dictionary["a"] = 0
dictionary["b"] = 1
dictionary["ab"] = 2
dictionary["ba"] = 3
dictionary["aba"] = 4
dictionary["abab"] = 5

可以想见，解码器必须使用与编码器相同的字典，否则 DF 无法从 EF 恢复。为了解决这个问题，DF 是增量编码的，编码器因此确保解码器有足够的信息来重建字典。

解码器伪代码 
dictionary  : array of string (equivalent to: map of CodeType to string)
S           : empty string
k           : CodeType
DF          : the data file
EF          : the encoded file

dictionary = entries for all strings consisting of a single byte

while ( could read a new CodeType from EF into k )
{
    if ( k > dictionary size )
        cannot decode!
    else
    if ( k == dictionary size ) // special case
        dictionary[next unused code] = S + S[0]
    else
    if ( S isn't empty )
        dictionary[next unused code] = S + dictionary[k][0]

    write dictionary[k] to DF
    S = dictionary[k]
}

解码器简化运行 
dictionary[0] = "a"
dictionary[1] = "b"

EF: {0 1 2 4 1}

while() begins
read 0, -, -, -, DF = "a", S = "a"
read 1, -, -, dictionary[2] = "ab", DF = "ab", S = "b"
read 2, -, -, dictionary[3] = "ba", DF = "abab", S = "ab"
read 4, -, dictionary[4] = "aba", DF = "abababa", S = "aba"     // special case
read 1, -, -, dictionary[5] = "abab", DF = "abababab", S = "b"
while() ends

DF: "abababab"

dictionary[0] = "a"
dictionary[1] = "b"
dictionary[2] = "ab"
dictionary[3] = "ba"
dictionary[4] = "aba"
dictionary[5] = "abab"

解码器首先必须处理错误输入。因为 DF 是增量编码的，所以有效代码永远不能超过字典的当前大小。因此，如果读取了这样的代码，解码器必须放弃。

然后解码器必须处理特殊情况，即接收到它应该添加到字典中的字符串的代码。

这种情况仅发生在编码器处理模式 cScSc 时，其中 c 是一个字节，S 是一个字符串，并且编码器已经将 cS 放入了字典。cS 的代码将被写入 EF，而 cSc 将被添加到字典中，并在下一次迭代中，cSc 的代码将被写入 EF。解码器按照伪代码处理这种情况：为 cS + c 添加一个条目，其中 cS 是先前解码的字符串，c 是它的第一个字节。

版本 1

上面的伪代码为直接实现铺平了道路。但是，仍然缺少一个细节：CodeType 应该是什么类型？到目前为止唯一的说明是它必须比字节更宽。原因是字典仍然需要能够增长，在它被填充了所有单字节字符串的代码（256 个条目）之后。如果 CodeType 是字节，字典最多可以容纳 256 个条目，所有这些条目都将在开始时被填充，然后字典就无法增长了。

一个合适的类型是宽度为 16 位的类型，例如 unsigned short int，或者为了清晰起见使用 uint16_t。现在字典可以容纳总共 65,536 个条目，其中 65,536 - 256 = 65,280 个是新条目。

有人可能会倾向于使用 32 位（或 64 位）类型，如 uint32_t（uint64_t），这允许字典存储大量的条目。实际上，这会降低压缩效果，因为写入 EF 的每个代码都需要 32 位（或 64 位）来存储，而且其中许多位都不会被使用。此外，字典会不断增长，直到耗尽计算机的所有内存。

说到字典增长，16 位字典最终会填满。这可以通过将其重置为其包含前 256 个条目的初始状态来处理。编码器和解码器只需在开头添加一个检查即可。

if ( dictionary is full )
    reset dictionary

在 C++ 源代码中，重置是通过一个命名的 lambda 函数（它们通常是匿名的）来完成的。将 lambda 函数嵌入到编码器中的原因在于，字典重置函数必须为字典定制，并且永远不会在编码器之外使用。

[ 下载版本 1 ]

版本 2

第一个版本存在性能问题：压缩和解压缩大文件需要太长时间。

我们假设导致速度减慢的原因是输入和输出，即文件读取和写入。C++ 文件流本身已进行了内部缓冲，因此我们假设缓冲区不够大。由于流允许使用自定义缓冲区，因此我们继续使用两个 1 MB 的缓冲区，一个用于输入文件，另一个用于输出文件。

示例代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <cstddef>
#include <fstream>
#include <ios>
#include <memory>

// ...

const std::size_t one_mb {1024 * 1024}; // one megabyte (or "mebibyte", more accurately)
const std::unique_ptr<char[]> custom_buffer(new char[one_mb]);
std::fstream f; // must set the custom buffer before opening the file

f.rdbuf()->pubsetbuf(custom_buffer.get(), one_mb);
f.open("file.txt", std::ios_base::in | std::ios_base::binary);


这确实有效地以 1 MB 的块进行文件读写，大大减少了读写次数。然而，程序仍然很慢。看来最初的假设是错误的，I/O 并不是瓶颈。

由于程序的简单性，可以推断出减速发生在编码器和解码器中。
编码器和解码器都大量使用字符串。将字节附加到字符串可能会触发内存重新分配以及随后将数据复制到新位置。

通过使用 std::map 以外的东西可以改进编码器。C++11 标准添加了 std::unordered_map，它的行为类似于 std::map，除了它对键进行哈希（这就是它被称为“哈希表”的原因）。哈希可以概括如下：将某物（在我们的例子中是字符串）转换为其唯一的哈希码（一个数字）。

当哈希函数为两个不同的输入获得相同的哈希码时，这称为哈希冲突。好的哈希函数冲突少，坏的哈希函数冲突多，完美的哈希函数没有冲突。后者是我们够不到的，因为遇到的每个可能的字符串都必须变成它自己唯一的哈希码，而我们不能使用足够宽的哈希码类型来容纳它。

上一段的目的是作为引入，说明此版本的程序理论上可能损坏数据。尽管 16 位字典的 65,536 个条目限制应该使冲突非常不可能，但它们仍然是可能的。我们为此获得的回报是更快的代码检索，这意味着更快的压缩。

在使用 std::unordered_map 之前，必须编写一个哈希函子来处理 std::vector<char>。

幸运的是，已经存在一个 std::hash 函子来处理 std::basic_string<char>（更常称为 std::string），可以重用它。其余代码保持不变。

示例代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <cstddef>
#include <functional>
#include <string>
#include <vector>

struct HashCharVector {
    std::size_t operator () (const std::vector<char> &vc) const
    {
        return std::hash<std::string>()(std::string(vc.cbegin(), vc.cend()));
    }
};

// ...

#include <unordered_map>

std::unordered_map<std::vector<char>, CodeType, HashCharVector> dictionary;


[ 下载版本 2 ]

版本 3

到目前为止，对编码器所做的改动不大，对解码器则完全没有改动。显然，是时候做出改变了；如果算法和相关数据结构导致程序缓慢，那么尝试优化程序有什么意义？

让我们回顾一下我们到目前为止学到的知识
  • 编码器不需要在字典中存储实际的字符串。
  • LZW 编码器伪代码显示，任何新添加的字符串都是通过将一个字节附加到已存在的字符串而产生的。

通俗英文翻译：告别字符串！

计划如下：编码器的字典将不再将字符串映射到 CodeType。它将把一个对（CodeType，字节）映射到一个 CodeType。

初始的单字节字符串将表示为“无效”CodeType 与给定字节的对。这个“无效”代码必须是一个永远不会出现在 EF 中的值。一个不错的选择是字典大小限制，在源代码中是 globals::dms。因为当字典达到该大小时会重置，所以永远不会生成映射到该代码的条目。

编码器伪代码 
dictionary  : map of pair (CodeType, byte) to CodeType
c           : byte
i           : CodeType
DF          : the data file
EF          : the encoded file

i = invalid_code

reset_dictionary : lambda function {
    dictionary = entries for all pairs consisting of the invalid_code and a unique byte
}

while ( could read a new byte from DF into c )
{
    if ( dictionary is full )
        reset_dictionary()

    if ( dictionary doesn't contain pair (i, c) )
    {
        dictionary[pair (i, c)] = next unused code
        write i to EF
        i = dictionary[pair (invalid_code, c)]
    }
    else
        i = dictionary[pair (i, c)]
}

if ( i != invalid_code )
    write i to EF

在大多数计算机上，这种基于对的算法将比以前的基于字符串的算法运行得更快。

现在我们对于解码器有两个选择。
  1. 保持原样
  2. 尝试从中也移除字符串

第一种选择是可能的，因为到目前为止的所有三个程序都会为相同的 DF 生成相同的 EF（反之亦然）。所以解码器可以保持原样，程序仍然可以正确地解压缩文件。然而，更快解压缩速度的承诺是诱人的。

我们从一个由所有 invalid_code 和一个唯一字节组成的数组开始，这将是字典。当读取 EF 时，将添加新条目，由一个有效代码和一个字节组成，该代码表示现有字符串，并将新字节附加到该字符串。

此时应该很明显，要重构字符串，我们将使用代码信息将附加的字节链接在一起。这是通过一个名为 rebuild_string() 的新 lambda 函数完成的。

简化的字典机制 
// `i_c' is an alias for `invalid_code'

                  0           1          2         3         4         5         6         7
dictionary = {(i_c, 'b'), (i_c, 'c'), (0, 'l'), (1, 'o'), (3, 'w'), (2, 'u'), (5, 'e'), (4, 's')}

rebuild_string(6) == "blue"
rebuild_string(7) == "cows"

请注意，重构的字符串将是反向的。

解码器伪代码 
dictionary  : array of pair (CodeType, byte)
i           : CodeType
k           : CodeType
DF          : the data file
EF          : the encoded file

i = invalid_code

reset_dictionary : lambda function {
    dictionary = entries for all pairs consisting of the invalid_code and a unique byte
}

rebuild_string(CodeType k) : lambda function {
    build the string S by chaining all bytes starting at k and ending at invalid_code
}

while ( could read a new CodeType from EF into k )
{
    if ( dictionary is full )
        reset_dictionary()

    if ( k > dictionary size )
        cannot decode!
    else
    if ( k == dictionary size )
        dictionary[next unused code] = pair (i, rebuild_string(i)[0])
    else
    if ( i != invalid_code )
        dictionary[next unused code] = pair (i, rebuild_string(k)[0])

    write rebuild_string(k) to DF
    i = k
}

上述解码器的源代码在实际程序中的结构不同，因为引入了一个字符串变量，以确保 k 字符串只被“重构”一次。

[ 下载版本 3 ]

版本 4

解码器仍然很慢，因为 rebuild_string() lambda 函数生成的字符串是通过值传递的。这意味着需要为 s 变量分配空间，因为它会复制 lambda 函数返回的任何字符串的内容。

解码器的优化变得清晰：s 成为一个字符串指针，而 rebuild_string() 返回其内部生成的、现在是 static 的字符串的内存地址。唯一复制的是字符串的内存地址（基本上是一个数字），这是一个非常廉价的操作。

由于这个更改，解码器变得非常快，我个人觉得它终于达到了最优。

然而，编码器仍然有很长的路要走。在其当前形式下，所能做的最好的就是尝试减少 std::map 重复的内部内存分配。这是通过使用自定义内存池分配器来实现的。

分配器是管理内存的类。像 std::map 这样的容器通常使用默认的内置分配器，但可以提供一个自定义分配器来代替。

目标是尽可能少地分配内存。具有此目标的分配器将获取一大块内存（池），然后当容器请求内存时，从预先分配的内存中提供更小的块，而不是实际获取新内存。

编写我们自己的分配器并非易事，很快我们就会陷入困境，需要优化它。

所以我们只需要使用现成的分配器。Juha Nieminen 的FSBAllocator 是一个很好的选择（有关更多信息，请参阅链接）。版本 4 捆绑了这个库，因此不需要单独下载。

[ 下载版本 4 ]

版本 5

在版本 4 中，自定义分配器减轻了内存分配引起的性能损失。因此，如果程序仍然很慢，那只能是 std::map 仍然很慢。

标准库的 std::map 很好地服务了我们，但如果编码速度要达到最优，则必须编写自定义字典数据结构，为 LZW 算法设计。

编码器算法本身没有任何问题。我们要做的是编写一个 EncoderDictionary 类，其功能比当前的 std::map<std::pair<CodeType, char>, CodeType> 更快。

可以通过向 EncoderDictionary 类添加额外功能来简化编码器。两个明显的改进是
  1. 使字典自动重置。
  2. 在一次传递中搜索并插入一个新元素。

因此，编码器伪代码大大简化了。

ed    : EncoderDictionary // custom dictionary type
i     : CodeType
temp  : CodeType          // will be used to temporarily save i
c     : byte
DF    : the data file
EF    : the encoded file

i = invalid_code

while ( could read a new byte from DF into c )
{
    temp = i
    i = ed.search_and_insert(c, i)

    if ( i == invalid_code )
    {
        write temp to EF
        i = ed.search(c, invalid_value)
    }
    //
    // else
    //     i = ed.search(c, i)
    //
}

if ( i != invalid_code )
    write i to EF

上面的算法应该看起来很熟悉，因为它基于版本 4 的对编码器。

注释掉的 else 分支不是必需的，因为 ed.search_and_insert() 已经将 i 更新为 (c, i) 的索引（如果找到了该对），否则将 i 设置为 invalid_code。

新字典还会自行初始化并在填满时重置，因此 reset_dictionary() lambda 函数也不再需要了。

至此，我们可以专注于实现 EncoderDictionary。

每个人似乎都在使用二叉搜索树来提高 LZW 编码器的性能。我尝试了一种基于索引的解决方案（无需搜索，但内存消耗更大），但对性能感到失望，尽管它仍然比版本 4 快。

最后，我决定将 EncoderDictionary 实现为一个基于向量的不平衡二叉搜索树，并从 Juha Nieminen 的文章中获得了很大启发。

二叉搜索树 (BST) 是一种由链接节点组成的数据结构。任何节点都有一个父节点，最多有两个子节点。（根节点是例外，因为它没有父节点。）

节点包含数据，在我们的例子中是字节。左子节点将包含比父节点值小的字节。右子节点将包含比父节点值大的字节。

如果树的分支深度相差超过一个级别，则该树被视为不平衡。这会降低大树的搜索性能，因此通常会付出额外的努力来平衡树。在我们的例子中，树会太小，以至于性能不会显着下降。

最后，基于向量意味着节点存储在 std::vector 中，该向量预先分配了所需的内存，而不是节点通过动态内存分配来生成其子节点。其效果与在 std::map 中使用FSBAllocator 相当。

不平衡 BST 的示意图

请注意，节点的所有左侧后代（左子树）包含小于其祖先节点的值，而右侧后代（右子树）包含大于其祖先节点的值。

让我们在树中搜索值 65。

start at root, 65 > 32, go right
65 > 35, go right
65 < 70, go left
65 > 60, go right
65 == 65, found it!

在包含 10 个节点的树中找到一个值需要 5 次比较。在如此小的规模下很难看到搜索速度的提高，但当我们使用该程序处理多兆字节文件时，它会变得非常明显。

平衡 BST 的示意图

如果树是平衡的，不平衡树可能看起来像这样。注意分支的深度（级别）。

重申一下，平衡树在我们的情况下是一项额外的努力，它并非真正有必要，因此不会被追求。

回到 EncoderDictionary，很明显成员函数 search_and_insert() 非常重要。它有三个任务：
  1. 如果节点向量已满，则重置它。
  2. 如果找到了对 (c, i)，则返回其索引。
  3. 如果未找到对 (c, i)，则将其添加到节点向量并返回invalid_code。

节点向量是 std::vector<Node>，其中 Node 是在 EncoderDictionary 内部定义的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
struct Node {

    ///
    /// @brief Default constructor.
    /// @param c    byte that the Node will contain
    ///
    explicit Node(char c): first(globals::dms), c(c), left(globals::dms), right(globals::dms)
    {
    }

    CodeType    first;  ///< Code of first child string.
    char        c;      ///< Byte.
    CodeType    left;   ///< Code of child node with byte < `c`.
    CodeType    right;  ///< Code of child node with byte > `c`.
};


对 first 的注释可能具有误导性，因为它不指子节点，而是指第一个使用当前节点数据作为前缀字符串的节点的索引。

还记得在版本 4 中，我们将对（CodeType，字节）映射到 CodeType 吗？这里也是如此，只不过代码通过节点相互链接，这增加了搜索速度。

EncoderDictionary::search_and_insert() 代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
CodeType search_and_insert(CodeType i, char c)
{
    // dictionary's maximum size was reached
    if (vn.size() == globals::dms)
        reset();

    if (i == globals::dms)
        return search_initials(c);

    const CodeType vn_size = vn.size();
    CodeType ci {vn[i].first}; // Current Index

    if (ci != globals::dms)
    {
        while (true)
            if (c < vn[ci].c)
            {
                if (vn[ci].left == globals::dms)
                {
                    vn[ci].left = vn_size;
                    break;
                }
                else
                    ci = vn[ci].left;
            }
            else
            if (c > vn[ci].c)
            {
                if (vn[ci].right == globals::dms)
                {
                    vn[ci].right = vn_size;
                    break;
                }
                else
                    ci = vn[ci].right;
            }
            else // c == vn[ci].c
                return ci;
    }
    else
        vn[i].first = vn_size;

    vn.push_back(Node(c));
    return globals::dms;
}


reset() 的作用应该很明显。

search_initials(c) 基本上是可能的 search(c, globals::dms) 函数的优化等效项，它返回初始单字节字符串的索引。

[ 下载版本 5 ]

版本 6

在版本 5 中实现了不错的压缩率（速度）。现在重点将转移到提高压缩率上。

理论上，如果我们允许字典保存超过 64 KiB 的条目，我们将获得更好的压缩效果。但是，为了访问这些条目，CodeType 需要从 16 位扩展。

让我们回顾一下为什么在之前的五个版本（之后将称为“alpha 版本”）中我们选择了 16 位代码类型。原因是写入 EF 的代码会浪费更多空间而不是节省空间，从而降低压缩效果。之所以浪费空间，是因为代码的宽度比必需的宽，留下了未使用的位。

为了说明这一点，请考虑编码 CodeType 值 375
375 in base 10 == 101110111 in base 2

CodeType =  8 bits: not enough bits
CodeType = 16 bits: 00000001 01110111
CodeType = 32 bits: 00000000 00000000 00000001 01110111

技术准确性免责声明
  • 字节序不是本文的主题。

请注意，虽然 8 位无法存储 375 的值，但 16 位 CodeType 会浪费 7 位，而 32 位 CodeType 会浪费 23 位。存储 375 的值的理想宽度显然是 9 位。

计划如下：使用 32 位 CodeType，以及最多包含 16 Mi（16 * 1024 * 1024）个条目的字典，同时只读取和写入编码所需的位数。

备注
  • 包含 16 Mi 个条目的字典将使用超过 16 MiB。
  • 之所以如此，是因为一个条目包含的不仅仅是一个字节。
  • 如果 sizeof (Node) == 16 字节，编码器将使用大约 256 MiB。
  • 如果 sizeof (std::pair<CodeType, char>) == 8 字节，解码器将使用大约 128 MiB。

这种使用可变宽度编码的方法是可行的，因为我们可以始终验证编码字典中最大代码所需的位数，并相应地调整代码的输入/输出宽度。

棘手的部分将是实现自定义 I/O 系统，因为它建立在旧系统之上，而旧系统只理解字节以及通过组合字节获得的东西。

目标是编写自定义的 CodeWriter 和 CodeReader 组件，编码器和解码器将适应使用它们，而不是裸露的 std::ostream 和 std::istream。

几天过去了，我在与自定义 I/O 系统搏斗，它也在与我搏斗。

读取和写入可变宽度代码是一项相当大的工作，它涉及移位和掩码位，并保存当前不完整的字节，直到读取/写入足够的位数。

我不得不在两种代码拆分布局之间做出选择：LSB-First（最低有效位优先）和 MSB-First（最高有效位优先）。有关打包顺序的更多信息，请参阅 LZW 的维基百科文章。

备注
  • MSB-First 更容易可视化，也更直观。
  • LSB-First 不那么直观，但我发现它的运行速度比 MSB-First 快，而且似乎更容易实现。

这里没有理由列出 CodeWriter 和 CodeReader 的源代码。这些类又丑又晦涩，而且仅仅是勉强可用。由于需要额外的代码来同步位宽度，它们还使 compress() 和 decompress() 函数变得臃肿。

CodeWriter 和 CodeReader 的本质是它们可以以可变的二进制宽度（从最小 9 位到理论最大 32 位，但由于字典限制永远不会达到）来写入和读取代码。

涉及巨大字典的计划已更改。没有人阻止您将 globals::dms 改回 16 Mi，但如果您要听我的建议，16 Mi 太多了。

大字典可能会降低压缩率，这似乎不合逻辑，但如果代码宽度增长过大，以至于使用较小字典的较短代码更划算，则这是可以预期的。

使用大字典将为高熵文件提供更好的结果，但在这种使用场景下，给定文件很可能会被扩展。

我已决定，一个合理的字典条目限制是 512 Ki（512 * 1024）。程序仍然运行得相当快，尽管明显比版本 5 慢，同时几乎总是提供更好的压缩率。至少此版本终于可以压缩 license.txt，以防您还没有注意到 alpha 版本无法做到。

欢迎您尝试不同的限制。显然，像 64 KiB 这样的低限制将创建一个消耗大约是版本 5 两倍内存但速度相当快的程序。恢复到 16 位 CodeType 并使用低于 64 KiB 的限制将进一步提高速度，但会降低压缩效果。

在我的测试中，使用 32 KiB 字典限制和 16 位 CodeType 的版本 6 在压缩速度和压缩率方面都优于版本 5。

较高的字典限制会减慢程序速度，但这并不意味着总是能实现更好的压缩，尽管通常是这样。这完全取决于要压缩文件的性质。

备注
  • 如果您尝试不同的字典大小，请记住，对于编码文件 EF，您应该使用与压缩它相同的程序来解压缩它。

  • 否则，解压缩可能会失败。

[ 下载版本 6 ]

结束语

我为文章的结尾变得冗长表示歉意。我打算继续更新它，并添加新版本，同时压缩文本。

请记住，这些程序仅仅是玩具，对于高熵数据（如压缩存档、MP3、AVI 以及其他媒体）会表现不佳。实际上，在这种使用场景下，生成的存档应该比原始文件大得多。对于文本文件，通常能达到最佳压缩率。

这些程序可以使用 nuwen 的 MinGW 发行版 9.5 (GCC 4.7.2) 进行编译，有关下载，请参阅下面的链接。

附带的 ZIP 存档打包了程序的源代码及其 Doxygen 文档。

如果您发现错误、指出错误或对改进本文及附件程序有任何建议，请通过 PM 告知我。谢谢。


LZW 和压缩概述
计数论证
C++11
软件
杂项

致谢

附件：[lzw_v1.zip] [lzw_v2.zip] [lzw_v3.zip] [lzw_v4.zip] [lzw_v5.zip] [lzw_v6.zip]