ランレングス圧縮

可逆圧縮アルゴリズムのひとつであるランレングス圧縮を実装してみます。
ランレングス圧縮は連続するデータをその一つのデータとそのデータが連続している長さの組に変換します。

この圧縮は同じ値が連続するデータをく含んでいる場合には変換後のデータのサイズを小さくできますが、バラバラな値を多く含んでいる場合には逆に大きくなってしまいます。実際にこのアルゴリズムが使われる場合には、連続しないデータを含んでいてもそれほど圧縮率が下がらないような工夫がされます。

sample/RunLengthEncodingSample.java

package sample;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;

public class RunLengthEncodingSample {

    private static void writePair(OutputStream out, int b, int runLength)
	    throws IOException {
	if (runLength >= 0) {
	    out.write(b);
	    out.write(runLength);
	}
    }

    public static void encode(InputStream in, OutputStream out)
	    throws IOException {
	int b, prev = -1, runLength = -1;
	while ((b = in.read()) >= 0) {
	    if (b == prev) {
		runLength++;
		if (runLength > 255) {
		    writePair(out, b, 255);
		    runLength = 0;
		}
	    } else {
		writePair(out, prev, runLength);
		prev = b;
		runLength = 0;
	    }
	}
	writePair(out, prev, runLength);
    }

    public static void decode(InputStream in, OutputStream out)
	    throws IOException {
	int b, runLength;
	while ((b = in.read()) >= 0) {
	    if ((runLength = in.read()) >= 0) {
		for (; runLength >= 0; runLength--) {
		    out.write(b);
		}
	    } else {
		throw new IOException("入力データのフォーマットが不正です。");
	    }
	}
    }

    private static void check(String testData) throws IOException {
	byte[] testDataBinary = testData.getBytes("ISO-8859-1");
	ByteArrayOutputStream encOut = new ByteArrayOutputStream();
	encode(new ByteArrayInputStream(testDataBinary), encOut);

	ByteArrayOutputStream decOut = new ByteArrayOutputStream();
	decode(new ByteArrayInputStream(encOut.toByteArray()), decOut);

	System.out.println("符号化前のサイズ：　" + testDataBinary.length);
	System.out.println("符号化後のサイズ：　" + encOut.toByteArray().length);
	if (encOut.toByteArray().length < testDataBinary.length) {
	    System.out.println("データのサイズが減少しました。");
	} else if (encOut.toByteArray().length > testDataBinary.length) {
	    System.out.println("データのサイズが増大しました。");
	} else {
	    System.out.println("データのサイズは変化しませんでした。");
	}

	if (Arrays.equals(decOut.toByteArray(), testDataBinary)) {
	    System.out.println("正常にデータを復元しました。");
	} else {
	    System.out.println("データの復元に失敗しました。");
	}
    }

    public static void main(String[] args) throws IOException {
	check("aaaaaabbbbbbbbbbbccccccddd");
	System.out.println();
	check("abcdefghijklmnopqrstuvwxyz");
    }
}

2010年8月3日 | カテゴリー：アルゴリズム