游程编码算法

Author Avatar
Felix 5月 05, 2015

概述

利用比特流常见的冗余形式：连续的重复数据，来压缩数据。

0000000000000001111111000000011111111111    --40bit

在源数据中，记录重复bit的个数，记录到压缩数据中。

1111，0111，0111，1011                             --16bit

实现

* 压缩原理：
* 将源文件中连续的1或0的个数（count）写到压缩文件中,
* 比如count用8位表示，规定压缩文件的格式为：
* 0连续的个数-1连续的个数-0连续的个数-1连续的个数.....
* 个数的大小为0~255，
* 如何处理连续的0(或1)的个数过大，无法存到count中：
* count0(=255)-count1(=0)-count0(=?)-.......

压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private final static int R = 256;
   private final static int lgR = 8;			//存储cnt需要多少位
/**
    * 压缩
    */
   private static void compress() {
       boolean b, old = false;
       int cnt = 0;                            //记录连续的0或1的个数
       while (!BinaryStdIn.isEmpty()) {
           b = BinaryStdIn.readBoolean();
           if (b != old) {                     //该向输出流写数据了
               BinaryStdOut.write(cnt,lgR);
               cnt = 0;
               old = !old;
           } else {
               if (cnt == (R - 1)) {           // 处理连续的0(或1)的个数过大，无法存到count
                   BinaryStdOut.write(cnt,lgR);    //count0(=255)-count1(=0)-count0(=?)-.......
                   cnt = 0;
                   BinaryStdOut.write(cnt,lgR);
               }
           }
           cnt++;
       }
       BinaryStdOut.write(cnt,lgR);    //把剩余的cnt写出
       BinaryStdOut.close();
   }

解压

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	
/**
 * 解压
 */
private static void expand() {
    boolean bit = false;
    while (!BinaryStdIn.isEmpty()) {
        int run = BinaryStdIn.readInt(lgR);   //从输入流中读取lgR 位,这个数值代表了源文件中连续1或连续0的长度
        for (int i = 0; i < run; i++) {       //根据run的大小向输出流中写位
            BinaryStdOut.write(bit);
        }
        bit = !bit;                           //压缩的格式要求
    }
    BinaryStdOut.close();
}

测试用例

1
2
3
4
5
6
	
public static void main(String[] args) {
    if (args[0].equals("-")) compress();
    else if (args[0].equals("+")) expand();
    else throw new IllegalArgumentException("Illegal command line argument");
}
expand_less