Lempel-Ziv Ross Williams 壓縮算法 (LZRW1)
筆記一下前幾天看論文看到的一個壓縮演算法
壓縮方法
LZ77 class algorithm 會把曾經出現過的字串轉成 offset + length 的形式，上圖 in 在目前位置 - 6 字元的位置曾經出現過，長度為 3；walrus in 在目前位置 - 21 個字元的位置曾經出現過，長度為 11。
所以壓縮的格式其實就是交錯的表示 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 的長度有限制)
Compression Algorithm
把目前 cursor 的三個 byte 過 hash 查表，如果有查到且位置在可表示的範圍，代表至少有三個 byte 可以重複利用，就把目前的位置 encode 成 copy item，然後更新表，最後再 update Lempel/Ziv boundary。
References
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.