作者：
釋出於 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]