Lempel-Ziv Ross Williams 壓縮算法 (LZRW1)

筆記一下前幾天看論文看到的一個壓縮演算法

壓縮方法

LZ77 class algorithm 會把曾經出現過的字串轉成 offset + length 的形式，上圖 frog in a 在目前位置 - 19 字元的位置曾經出現過，長度為 11；a 在目前位置 - 9 個字元的位置曾經出現過，長度為 3。

所以壓縮的格式其實就是交錯的表示 character (literal item) 以及 offset-length pair (copy item)。

Data Format

為了方便 Decompression 的實作，分成了 Header chunk 以及 Item chunk。

Header chunk 為了 byte alignment 把 16 個 item group 再一起 (16 bits)。

每個 bit 表示對應的 item chunk 是 literal item 還是 copy item。

Item chunk 如果是 literal item 就是 1 byte，如果是 Copy item 就是 2 byte。(Offset 及 Length 的長度有限制)

• length = b + 1 (range: [3, 16])
• offset = 256 * a + c (range: [1, 4095])

Compression Algorithm

1. 把目前 cursor 的後三個 byte 過 hash 查表，取得 pointer p，把該 hash table 的位置取代該值
2. 如果 p 指向一個可表示的範圍，並且指向的位置與當前 cursor 的 string 有 match，代表至少有三個 byte 可以重複利用，就把目前的位置 encode 成 copy item
3. 否則 encode 成 literal item
4. 更新 cursor 位置到下一個還沒編碼的位置

References

LZRW - Wikipedia

LZRW1 (ross.net)

Williams, R.N., “An Extremely Fast Ziv-Lempel Data Compression Algorithm”, Data Compression Conference 1991 (DCC'91), 8-11 April , 1991, Snowbird, Utah, pp.362-371, IEEE reference code: TH0373-1/91/0000/0362/$01.00.