Zig-Zag编码及解码
Zig-Zag编码及解码的一个方法。
27 Nov 2013
Zig-zag是一种蛇形编码，把一个矩阵转化为另一个矩阵，矩阵的行列相等。例如：
A B C D A B E I
E F G H ==> F C D G
I J K L <== J M N K
M N O P H L O P
经过分析发现，编码后的行列与编码前的行列有对应关系，这种对应关系是有规律的。
行:0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
列:0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
转变为：
行:0 0 1 2 1 0 0 1 2 3 3 2 1 2 3 3
列:0 1 0 0 1 2 3 2 1 0 1 2 3 3 2 3
发现转换后的行和列的队列是有规律的，所以可以写个程序构造这个队列。不难看出，第一个元素和最后一个元素与原矩阵相同，所以构造队列要从两头开始，中间汇合。
从第一个元素开始正向构造，然后从最后一个元素开始反向构造。接头的地方就是矩阵的对角线的下方。
1 static void make_queue(int init, int *queue, int len)
2 {
3 int i, tmp;
4 int loop = init;
5
6 i = 1;
7 while(1){
8 tmp = loop;
9 while(loop > 0){
10 queue[i]=queue[i-1]+1;
11 if(++i >= len){return;}
12 loop-- ;
13 }
14 while(loop < tmp){
15 queue[i]=queue[i-1]-1;
16 if(++i >= len){return;}
17 loop++;
18 }
19 queue[i]=queue[i-1];
20 if(++i >= len){return;}
21
22 loop += 2;
23 }
24 }
25 static void make_queue_backword(int init, int *queue, int start, int len)
26 {
27 int i, tmp;
28 int loop = init;
29
30 i = len-2;
31 while(1){
32 tmp = loop;
33 while(loop > 0){
34 queue[i]=queue[i+1]-1;
35 if(--i < start){return;}
36 loop-- ;
37 }
38 while(loop < tmp){
39 queue[i]=queue[i+1]+1;
40 if(--i < start){return;}
41 loop++;
42 }
43 queue[i]=queue[i+1];
44 if(--i < start){return;}
45 loop += 2;
46 }
47 }
构造好两个队列后就可以编码解码了，其实编码解码的过程差不多。解码就是把下标反映射回去。
1 static void zig_zag(int *dest, int *src, unsigned int d, int decode)
2 {
3 unsigned int m, i;
4 unsigned int n = d*d;
5 int * row_queue = malloc(sizeof(int)*n);
6 int * col_queue = malloc(sizeof(int)*n);
7
8 m = 0;
9 for(i=1; i<=d; i++){
10 m += i;
11 }
12 row_queue[0]=col_queue[0]=0;
13 make_queue(0, row_queue, m);
14 make_queue(1, col_queue, m);
15
16 row_queue[n-1]=col_queue[n-1]=d-1;
17 make_queue_backword(0, row_queue, m, n);
18 make_queue_backword(1, col_queue, m, n);
19
20 if(decode){
21 for(m=0; m<n; m++){
22 dest[row_queue[m]*d+col_queue[m]] = src[m];
23 }
24 }else{
25 for(m=0; m<n; m++){
26 dest[m]=src[row_queue[m]*d+col_queue[m]];
27 }
28 }
29
30 free(row_queue);
31 free(col_queue);
32 }
好了，测试一下：
1 static void zig_zag_test_print_matrix(int *q, int d)
2 {
3 int i,j;
4 for(i=0;i<d;i++){
5 for(j=0; j<d; j++){
6 fprintf(stdout, "%2d ", q[i*d+j]);
7 }
8 fprintf(stdout, "\n");
9 }
10 }
11 static void zig_zag_test()
12 {
13 int q[16]={0};
14 int p[16];
15 int i;
16 int d = 4;
17 int n = d*d;
18 int m;
19
20 m = 0;
21 for(i=1; i<=d; i++){
22 m += i;
23 }
24 for(i=0;i<n;i++){
25 p[i]=i;
26 }
27
28 q[n-1]=d-1;
29 q[0]=0;
30 make_queue(0, q, m);
31 make_queue_backword(0, q, m, n);
32 for(i=0;i<n;i++){
33 fprintf(stdout, "%d ", q[i]);
34 }
35 fprintf(stdout, "\n");
36 make_queue(1, q, m);
37 make_queue_backword(1, q, m, n);
38 for(i=0;i<n;i++){
39 fprintf(stdout, "%d ", q[i]);
40 }
41 fprintf(stdout, "\n");
42
43 zig_zag(q, p, d, 0);
44 zig_zag_test_print_matrix(q, d);
45 fprintf(stdout, "==============\n");
46 memcpy(p, q, sizeof(p));
47 zig_zag(q, p, d, 1);
48 zig_zag_test_print_matrix(q, d);
49 }
50 int main()
51 {
52 zig_zag_test();
53 return 0;
54 }
方法有点笨，空间复杂性比较高，不知道有没有更好的方法。