データ圧縮のROLZ辞書符号化
58707 ワード
辞書符号化では、最もよく使われるのはおそらくLZ 77符号化である.LZ 77の考え方は簡単で、現在の位置を表すバイト列が前offsetバイトに現れたことをメタグループで表す.この単純な考え方のため、LZ 77に基づいて実現されたすべての実用的なアルゴリズムは良い解凍速度を持っている.古典的なLZ 77符号化を用いた圧縮アルゴリズムにはzip/gzのdeflateアルゴリズム,7 zのlzmaアルゴリズムなどがある.
LZ 77アルゴリズムの研究では、アルゴリズムのいくつかの不足点も発見され、LZ 77の最も明らかな不足はoffset値の過度な分散がメタグループに対する後続の処理効果を悪化させることである.例えば、16 MBのデータブロックを処理すると、1つのにおけるoffsetの値は167777216種類以上あり、offsetをセグメント化することができるが、圧縮率の向上に多かれ少なかれ影響する.
そこで我々はROLZアルゴリズムを持ち,ROLZは全称Reduced Offset Lempel Ziv,すなわちoffsetのLZ符号化を低減した.ROLZでは、繰り返し列が現れる位置は、現在のオフセット量offsetではなく、テーブル項目番号indexで表されます.
ROLZアルゴリズムを詳しく紹介する前に、圧縮アルゴリズムでよく使われる概念であるコンテキスト(context)を紹介します.コンテキストは現在の符号化位置の前の内容で、実際の応用では、現在の符号化位置の前のk文字だけをコンテキストとして、k次コンテキストと呼ばれています.コンテキストは圧縮率を向上させる重要なツールであり、例えば文字列「queen」であり、一般的な統計モデルで処理すると、英語ではアルファベット「u」の出現頻度が高くないため、「u」に長い接頭辞符号化を割り当てる可能性がある.しかし、1次コンテキスト「q」を考慮すると、英語では「q」の後ろに「u」が現れる確率が非常に高く、「u」に比較的短い接頭辞符号化を割り当て、コンテキストを利用して符号化効率を向上させることができる.
符号化では,各コンテキストのいくつかの情報を常に保存するが,コンテキスト次数k>=3ではコンテキストの個数が急激に上昇し,k=4では256^4=4 GBのコンテキストの各数が既に存在する.したがって、長いコンテキストでは、前のk文字に対するHash値をコンテキストとしてとることが多い.この結果、いくつかの全く異なるコンテキストが同じ記憶領域を占有する可能性があり、コンテキストの予測精度が低下するが、この方法はプログラムのメモリに対する要求を満たし、実際には広く使用されている.
ここで本題に入ります.ROLZアルゴリズムでは、2 Dテーブルrolz_を作成します.table[context][index]では、各位置を処理した後、この位置を対応するコンテキストのバケツに格納し、以下に文字列「construct-destruct」の例を挙げる(1次コンテキストを考慮して、現在位置12に符号化されていると仮定する):
従来のLZ 77アルゴリズムの場合、一致ペアは繰り返し列「struct」を表す.しかし、ROLZアルゴリズムでは、対応するコンテキストのバケツでのみ一致を探し、現在のコンテキスト「e」のバケツでは一致が見つからない(空のバケツであるため)、「s」をそのまま出力し、現在の位置をコンテキスト「e」のバケツに追加するしかありません.
現在、符号化位置13の「t」は、コンテキスト「s」のバケツの中でマッチングを探しているが、table[「s」][0]が私たちが探しているマッチングであることを発見し、マッチングに成功し、ROLZマッチング項目が現在の位置を表す重複列「truct」を出力する.
したがって、文字列「construct-destruct」、LZ 77およびROLZの符号化結果は、それぞれ以下のようになる.
ROLZの出力には1文字「s」が多くなっていることがわかりますが、offsetはより扱いやすいindexになり、実際には大量の入力に対してROLZは通常より良い圧縮率を得ることができることを示しています.
ROLZの符号化実装はLZ 77よりもずっと簡単である.rolz_table自体は良いハッシュリストであり、LZ 77のように検索構造を別途作成する必要はありません.解凍はLZ 77に比べて複雑であり、圧縮プロセスと同様にrolz_全体を構築しなければならない.tableは、その後、テーブルを調べてindexを繰り返し列の位置に変換するので、ROLZ解凍はLZ 77に対して少し遅い.
個人的にはROLZ+算術符号化の完全な実装comprolzがあり、現在圧縮率は7 zに相当している.以下にも簡単なROLZ+Polar符号化実装(圧縮率はgzよりやや高い)を添付し、3次Hashコンテキストを使用して、各コンテキストに15個のバケツエントリがある.
LZ 77アルゴリズムの研究では、アルゴリズムのいくつかの不足点も発見され、LZ 77の最も明らかな不足はoffset値の過度な分散が
そこで我々はROLZアルゴリズムを持ち,ROLZは全称Reduced Offset Lempel Ziv,すなわちoffsetのLZ符号化を低減した.ROLZでは、繰り返し列が現れる位置は、現在のオフセット量offsetではなく、テーブル項目番号indexで表されます.
ROLZアルゴリズムを詳しく紹介する前に、圧縮アルゴリズムでよく使われる概念であるコンテキスト(context)を紹介します.コンテキストは現在の符号化位置の前の内容で、実際の応用では、現在の符号化位置の前のk文字だけをコンテキストとして、k次コンテキストと呼ばれています.コンテキストは圧縮率を向上させる重要なツールであり、例えば文字列「queen」であり、一般的な統計モデルで処理すると、英語ではアルファベット「u」の出現頻度が高くないため、「u」に長い接頭辞符号化を割り当てる可能性がある.しかし、1次コンテキスト「q」を考慮すると、英語では「q」の後ろに「u」が現れる確率が非常に高く、「u」に比較的短い接頭辞符号化を割り当て、コンテキストを利用して符号化効率を向上させることができる.
符号化では,各コンテキストのいくつかの情報を常に保存するが,コンテキスト次数k>=3ではコンテキストの個数が急激に上昇し,k=4では256^4=4 GBのコンテキストの各数が既に存在する.したがって、長いコンテキストでは、前のk文字に対するHash値をコンテキストとしてとることが多い.この結果、いくつかの全く異なるコンテキストが同じ記憶領域を占有する可能性があり、コンテキストの予測精度が低下するが、この方法はプログラムのメモリに対する要求を満たし、実際には広く使用されている.
ここで本題に入ります.ROLZアルゴリズムでは、2 Dテーブルrolz_を作成します.table[context][index]では、各位置を処理した後、この位置を対応するコンテキストのバケツに格納し、以下に文字列「construct-destruct」の例を挙げる(1次コンテキストを考慮して、現在位置12に符号化されていると仮定する):
0 1 2 3 4 5 6 7 8 9 10 11 $ 13 14 15 16 17
c o n s t r u c t - d e s t r u c t
table["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}従来のLZ 77アルゴリズムの場合、一致ペア
0 1 2 3 4 5 6 7 8 9 10 11 12 $ 14 15 16 17
c o n s t r u c t - d e s t r u c t
table["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マッチング項目
したがって、文字列「construct-destruct」、LZ 77およびROLZの符号化結果は、それぞれ以下のようになる.
LZ77: construct-de<9,6>
ROLZ: construct-des<0,5>ROLZの出力には1文字「s」が多くなっていることがわかりますが、offsetはより扱いやすいindexになり、実際には大量の入力に対してROLZは通常より良い圧縮率を得ることができることを示しています.
ROLZの符号化実装はLZ 77よりもずっと簡単である.rolz_table自体は良いハッシュリストであり、LZ 77のように検索構造を別途作成する必要はありません.解凍はLZ 77に比べて複雑であり、圧縮プロセスと同様にrolz_全体を構築しなければならない.tableは、その後、テーブルを調べてindexを繰り返し列の位置に変換するので、ROLZ解凍はLZ 77に対して少し遅い.
個人的にはROLZ+算術符号化の完全な実装comprolzがあり、現在圧縮率は7 zに相当している.以下にも簡単なROLZ+Polar符号化実装(圧縮率はgzよりやや高い)を添付し、3次Hashコンテキストを使用して、各コンテキストに15個のバケツエントリがある.
1 /*******************************************************************************
2 * RichSelian's nooblike compressor: ROLZ + Polar coding
3 ******************************************************************************/
4 #include <stdio.h>
5 #include <string.h>
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 * ROLZ
137 ******************************************************************************/
138 #define ROLZ_BUCKET_SIZE 65536
139 #define MATCH_IDX_SIZE 15 /* make element of rolz_table[] 64 Bytes */
140 #define MATCH_LEN_MIN 2
141 #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 * MAIN
257 ******************************************************************************/
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 }