在字典编码中，最常用的恐怕要算LZ77编码了。LZ77的思想很简单，就是用一个<offset, length>元组来表示当前位置的字节串在前offset个字节中出现过。正是由于这个简单的思想，所有基于LZ77实现的实用算法都有着不错的解压速度。经典的使用LZ77编码的压缩算法有zip/gz的deflate算法，7z的lzma算法等。
在对LZ77算法研究中，我们也发现算法中的一些不足之处，LZ77最明显的不足是offset值的过度零散导致对<offset, length>元组的后续处理效果不好。例如处理一个16MB的数据块，一个<offset, length>中offset的取值就有16777216种之多，虽然可以对offset进行分段处理，但还是或多或少会影响到压缩率的提升。
于是我们有了ROLZ算法，ROLZ全称是Reduced Offset Lempel Ziv，即减少了offset的LZ编码。在ROLZ中，重复串出现的位置不再是用相对当前的偏移量offset，而是用一个表项编号index来表示。
在详细介绍ROLZ算法之前，我们先介绍一个压缩算法中常用的概念——上下文（context），上下文就是当前编码位置之前的内容，在实际应用中，我们只取当前编码位置前k个字符做为上下文，称为k阶上下文。上下文是提高压缩率的一个重要工具，例如字符串"queen"，如果用一般的统计模型来处理，由于英语中字母"u"出现频率不高，我们可能会给"u"分配一个长的前缀编码。但考虑一阶上下文"q"，在英语中"q"后面出现"u"的概率非常高，我们就会给"u"分配相对较短的前缀编码，从而利用上下文提高了编码效率。
在编码中，我们总会保存每个上下文的一些信息，但是当上下文阶数k >= 3时，上下文的个数会急剧升高，当k=4时就已经有256^4 = 4GB的上下文各数。所以对于较长的上下文，我们往往取一个对前k个字符的一个Hash值作为上下文，这样的结果是可能几个完全不同的上下文会占用相同的存储空间，导致上下文的预测准确率有所降低，但这种做法满足了程序对内存的要求，实际中也被广泛使用。
现在进入正题，在ROLZ算法中，我们会建立一张二维表rolz_table[context][index]，在处理完每个位置后，我们将这个位置存入对应上下文的桶中，以下就字符串"construct- destruct"举个例子（考虑一阶上下文，假设当前编码到位置12）：
0 1 2 3 4 5 6 7 8 9 10 11 $ 13 14 15 16 17c o n s t r u c t - d e s t r u c ttable["c"] = { 8, 1}table["o"] = { 2}table["n"] = { 3}table["s"] = { 4}table["t"] = { 9, 5}table["r"] = { 6}table["u"] = { 7}table["-"] = { 10}table["d"] = { 11} 如果是传统的LZ77算法，这时候我们应该输出一个匹配对<offset=9, length=6>表示重复串"struct"。但在ROLZ算法中，我们只在对应上下文的桶中寻找匹配，在当前上下文"e"的桶中找不到匹配（因为是一个空的桶），只好将"s"原样输出，然后将当前位置加入上下文"e"的桶中：
0 1 2 3 4 5 6 7 8 9 10 11 12 $ 14 15 16 17c o n s t r u c t - d e s t r u c ttable["c"] = { 8, 1}table["o"] = { 2}table["n"] = { 3}table["s"] = { 4}table["t"] = { 9, 5}table["r"] = { 6}table["u"] = { 7}table["-"] = { 10}table["d"] = { 11}table["e"] = { 12} 现在编码位置13的"t"，我们在上下文"s"的桶中寻找匹配，发现table["s"][0]就是我们要找的匹配，于是匹配成功，输出一个ROLZ匹配项<index=0, length=5>表示当前位置的重复串"truct"。
所以，对字符串"construct-destruct"，LZ77和ROLZ的编码结果分别如下：
LZ77: construct-de<9,6>ROLZ: construct-des<0,5>
可以看到ROLZ的输出多了一个字符"s"，但是offset变成了更容易处理的index，实践表明对大量输入的时候ROLZ通常能得到更好的压缩率。
ROLZ的编码实现比LZ77要简单得多，因为rolz_table本身就是一张很好的散列表，我们不需要像LZ77那样另外创建一个查找结构。而解压相对LZ77要复杂一些，我们必须和压缩过程一样构建起整个rolz_table，然后通过查表将index转换为重复串的位置，所以ROLZ解压相对LZ77要慢一些。
我个人有一个ROLZ+算术编码的完整实现，目前压缩率已经和7z相当。下面也附上一个简单的ROLZ+Polar编码实现（压缩率略高于gz），使用3阶Hash上下文，每个上下文有15个桶项：
1 /******************************************************************************* 2 * RichSelian's nooblike compressor: ROLZ + Polar coding 3 ******************************************************************************/ 4 #include5 #include 6 7 /******************************************************************************* 8 * POLAR Coder 9 ******************************************************************************/ 10 #define POLAR_SYMBOLS 512 /* should be even */ 11 #define POLAR_MAXLEN 15 /* should be less than 16, so we can pack two length values into a byte */ 12 13 #define M_round_down(x) while((x)&(-(x)^(x))) { (x) &= (-(x)^(x)); } 14 #define M_round_up(x) while((x)&(-(x)^(x))) { (x) &= (-(x)^(x)); } (x) <<= 1; 15 #define M_int_swap(x, y) {int (_)=(x); (x)=(y); (y)=(_);} 16 17 int polar_make_leng_table(const int* freq_table, int* leng_table) { 18 int symbols[POLAR_SYMBOLS]; 19 int i; 20 int s; 21 int total; 22 int shift = 0; 23 24 memcpy(leng_table, freq_table, POLAR_SYMBOLS * sizeof(int)); 25 26 MakeTablePass: 27 /* sort symbols */ 28 for(i = 0; i < POLAR_SYMBOLS; i++) { 29 symbols[i] = i; 30 } 31 for(i = 0; i < POLAR_SYMBOLS; i++) { 32 if(i > 0 && leng_table[symbols[i - 1]] < leng_table[symbols[i]]) { 33 M_int_swap(symbols[i - 1], symbols[i]); 34 i -= 2; 35 } 36 } 37 38 /* calculate total frequency */ 39 total = 0; 40 for(i = 0; i < POLAR_SYMBOLS; i++) { 41 total += leng_table[i]; 42 } 43 44 /* run */ 45 M_round_up(total); 46 s = 0; 47 for(i = 0; i < POLAR_SYMBOLS; i++) { 48 M_round_down(leng_table[i]); 49 s += leng_table[i]; 50 } 51 while(s < total) { 52 for(i = 0; i < POLAR_SYMBOLS; i++) { 53 if(s + leng_table[symbols[i]] <= total) { 54 s += leng_table[symbols[i]]; 55 leng_table[symbols[i]] *= 2; 56 } 57 } 58 } 59 60 /* get code length */ 61 for(i = 0; i < POLAR_SYMBOLS; i++) { 62 s = 2; 63 if(leng_table[i] > 0) { 64 while((total / leng_table[i]) >> s != 0) { 65 s += 1; 66 } 67 leng_table[i] = s - 1; 68 } else { 69 leng_table[i] = 0; 70 } 71 72 /* code length too long -- scale and rebuild table */ 73 if(leng_table[i] > POLAR_MAXLEN) { 74 shift += 1; 75 for(i = 0; i < POLAR_SYMBOLS; i++) { 76 if((leng_table[i] = freq_table[i] >> shift) == 0 && freq_table[i] > 0) { 77 leng_table[i] = 1; 78 } 79 } 80 goto MakeTablePass; 81 } 82 } 83 return 0; 84 } 85 86 int polar_make_code_table(const int* leng_table, int* code_table) { 87 int i; 88 int s; 89 int t1; 90 int t2; 91 int code = 0; 92 93 memset(code_table, 0, POLAR_SYMBOLS * sizeof(int)); 94 95 /* make code for each symbol */ 96 for(s = 1; s <= POLAR_MAXLEN; s++) { 97 for(i = 0; i < POLAR_SYMBOLS; i++) { 98 if(leng_table[i] == s) { 99 code_table[i] = code;100 code += 1;101 }102 }103 code *= 2;104 }105 106 /* reverse each code */107 for(i = 0; i < POLAR_SYMBOLS; i++) {108 t1 = 0;109 t2 = leng_table[i] - 1;110 while(t1 < t2) {111 code_table[i] ^= (1 & (code_table[i] >> t1)) << t2;112 code_table[i] ^= (1 & (code_table[i] >> t2)) << t1;113 code_table[i] ^= (1 & (code_table[i] >> t1)) << t2;114 t1++;115 t2--;116 }117 }118 return 0;119 }120 121 int polar_make_decode_table(const int* leng_table, const int* code_table, int* decode_table) {122 int i;123 int c;124 125 for(c = 0; c < POLAR_SYMBOLS; c++) {126 if(leng_table[c] > 0) {127 for(i = 0; i + code_table[c] < 65536; i += (1 << leng_table[c])) {128 decode_table[i + code_table[c]] = c;129 }130 }131 }132 return 0;133 }134 135 /*******************************************************************************136 * ROLZ137 ******************************************************************************/138 #define ROLZ_BUCKET_SIZE 65536139 #define MATCH_IDX_SIZE 15 /* make element of rolz_table[] 64 Bytes */140 #define MATCH_LEN_MIN 2141 #define MATCH_LEN_MAX 17 /* MATCH_LEN_MAX < MATCH_LEN_MIN + (POLAR_SYMBOLS-256) / MATCH_IDX_SIZE */142 143 static int ch1 = 0;144 static int ch2 = 0;145 static int ch3 = 0;146 147 #define M_rolz_item(x, n) (rolz_table[(x)].m_item[(rolz_table[(x)].m_head + MATCH_IDX_SIZE - (n)) % MATCH_IDX_SIZE])148 149 static struct {150 unsigned int m_item[MATCH_IDX_SIZE];151 unsigned char m_head;152 } rolz_table[ROLZ_BUCKET_SIZE];153 154 static inline unsigned int rolz_context() {155 return (unsigned)(ch1 * 131313131 + ch2 * 131313 + ch3 * 131) % ROLZ_BUCKET_SIZE;156 }157 158 static inline void rolz_update_context(unsigned char* buf, int pos, int cache) {159 rolz_table[rolz_context()].m_head = (rolz_table[rolz_context()].m_head + 1) % MATCH_IDX_SIZE;160 if(cache) {161 M_rolz_item(rolz_context(), 0) = pos | (buf[pos] << 24);162 } else {163 M_rolz_item(rolz_context(), 0) = pos;164 }165 ch3 = ch2;166 ch2 = ch1;167 ch1 = buf[pos];168 return;169 }170 171 int rolz_encode(unsigned char* ibuf, unsigned short* obuf, int ilen) {172 int olen = 0;173 int pos = 0;174 int i;175 int j;176 int match_idx;177 int match_len;178 179 memset(rolz_table, 0, sizeof(rolz_table));180 ch3 = 0;181 ch2 = 0;182 ch1 = 0;183 while(pos < ilen) {184 match_len = MATCH_LEN_MIN - 1;185 match_idx = -1;186 if(pos + MATCH_LEN_MAX < ilen) { /* find match */187 for(i = 0; i < MATCH_IDX_SIZE; i++) {188 if(M_rolz_item(rolz_context(), i) == 0 || M_rolz_item(rolz_context(), i) >> 24 != ibuf[pos]) {189 continue;190 }191 192 j = 1;193 while(j < MATCH_LEN_MAX && ibuf[pos + j] == ibuf[(M_rolz_item(rolz_context(), i) & 0x00ffffff) + j]) {194 j++;195 }196 if(j > match_len) {197 match_len = j;198 match_idx = i;199 }200 }201 }202 if(match_len < MATCH_LEN_MIN) {203 match_len = 1;204 match_idx = -1;205 }206 207 if(match_idx == -1) { /* encode */208 obuf[olen++] = ibuf[pos];209 } else {210 obuf[olen++] = 256 + (match_len - MATCH_LEN_MIN) * MATCH_IDX_SIZE + match_idx;211 }212 213 for(i = 0; i < match_len; i++) { /* update context */214 rolz_update_context(ibuf, pos, 1);215 pos += 1;216 }217 }218 return olen;219 }220 221 int rolz_decode(unsigned short* ibuf, unsigned char* obuf, int ilen) {222 int olen = 0;223 int pos = 0;224 int i;225 int match_pos;226 int match_idx;227 int match_len;228 229 ch3 = 0;230 ch2 = 0;231 ch1 = 0;232 for(pos = 0; pos < ilen; pos++) {233 if(ibuf[pos] < 256) { /* decode */234 match_idx = -1;235 match_len = 1;236 obuf[olen++] = ibuf[pos];237 } else {238 match_idx = (ibuf[pos] - 256) % MATCH_IDX_SIZE;239 match_len = (ibuf[pos] - 256) / MATCH_IDX_SIZE + MATCH_LEN_MIN;240 }241 242 if(match_idx != -1) { /* expand match */243 match_pos = M_rolz_item(rolz_context(), match_idx);244 for(i =-0; i < match_len; i++) {245 obuf[olen++] = obuf[match_pos + i];246 }247 }248 for(i = 0; i < match_len; i++) { /* update context */249 rolz_update_context(obuf, olen - match_len + i, 0);250 }251 }252 return olen;253 }254 255 /*******************************************************************************256 * MAIN257 ******************************************************************************/258 int main(int argc, char** argv) {259 static unsigned char ibuf[10000000]; /* blocksize = 10MB */260 static unsigned short rbuf[10000000];261 static unsigned char obuf[12000000];262 int ilen;263 int rlen;264 int olen;265 int rpos;266 int opos;267 int i;268 int freq_table[POLAR_SYMBOLS];269 int leng_table[POLAR_SYMBOLS];270 int code_table[POLAR_SYMBOLS];271 int decode_table[1 << (POLAR_MAXLEN + 1)];272 int code_buf;273 int code_len;274 275 if(argc == 2 && strcmp(argv[1], "e") == 0) {276 while((ilen = fread(ibuf, 1, sizeof(ibuf), stdin)) > 0) {277 rlen = rolz_encode(ibuf, rbuf, ilen);278 olen = 0;279 280 memset(freq_table, 0, sizeof(freq_table));281 code_buf = 0;282 code_len = 0;283 284 for(i = 0; i < rlen; i++) {285 freq_table[rbuf[i]] += 1;286 }287 polar_make_leng_table(freq_table, leng_table);288 polar_make_code_table(leng_table, code_table);289 290 /* write length table */291 for(i = 0; i < POLAR_SYMBOLS; i += 2) {292 obuf[olen++] = leng_table[i] * 16 + leng_table[i + 1];293 }294 295 /* encode */296 for(i = 0; i < rlen; i++) {297 code_buf += code_table[rbuf[i]] << code_len;298 code_len += leng_table[rbuf[i]];299 while(code_len > 8) {300 obuf[olen++] = code_buf % 256;301 code_buf /= 256;302 code_len -= 8;303 }304 }305 if(code_len > 0) {306 obuf[olen++] = code_buf;307 code_buf = 0;308 code_len = 0;309 }310 fwrite(&rlen, sizeof(rlen), 1, stdout);311 fwrite(&olen, sizeof(olen), 1, stdout);312 fwrite(obuf, 1, olen, stdout);313 }314 return 0;315 }316 if(argc == 2 && strcmp(argv[1], "d") == 0) {317 while(fread(&rlen, sizeof(rlen), 1, stdin) == 1 && fread(&olen, sizeof(olen), 1, stdin) == 1) {318 olen = fread(obuf, 1, olen, stdin);319 rpos = 0;320 opos = 0;321 code_buf = 0;322 code_len = 0;323 324 /* read length table */325 for(i = 0; i < POLAR_SYMBOLS; i += 2) {326 leng_table[i] = obuf[opos] / 16;327 leng_table[i + 1] = obuf[opos] % 16;328 opos++;329 }330 331 /* decode */332 polar_make_code_table(leng_table, code_table);333 polar_make_decode_table(leng_table, code_table, decode_table);334 335 while(rpos < rlen) {336 while(opos < olen && code_len < POLAR_MAXLEN) {337 code_buf += obuf[opos++] << code_len;338 code_len += 8;339 }340 i = decode_table[code_buf % 65536];341 342 rbuf[rpos++] = i;343 code_buf >>= leng_table[i];344 code_len -= leng_table[i];345 }346 347 ilen = rolz_decode(rbuf, ibuf, rlen);348 fwrite(ibuf, 1, ilen, stdout);349 }350 }351 return -1;352 }