株式会社イーブ｜未経験・転職の方も就職可能。Javaプログラマー育成のエキスパート

HOME｜ JAVA技術者育成｜ システム開発｜ 求人情報｜ 個人情報保護｜ 移転案内

アルゴリズム

ランレングス圧縮

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

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");
    }
}

この記事のURL　｜　 更新日時: 2010年8月 3日 23:53

ユークリッドの互助法

ユークリッドの互助法という名前のアルゴリズムを紹介します。これは最大公約数を求めるアルゴリズムで、

ある整数x,yの最大公約数gcd(x,y)の解を求めるとして、yが0であればx、そうでなければgcd(y, x % y)が解となる。

という至って単純なアルゴリズムです。

以下のコードはこのアルゴリズムを再帰で実装したものです。ループで実装したコードはコメントアウトされています。(再帰のほうが断然エレガントである)

sample/GCDSample.java

package sample;

public class GCDSample {


	public static int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x % y);
	}

/*
	public static int gcd(int x, int y) {
		while (y != 0) {
			int t = x % y;
			x = y;
			y = t;
		}
		return x;
	}
*/

	public static void main(String[] args) {
		System.out.println(gcd(1071, 1029);
	}
}

この記事のURL　｜　 更新日時: 2010年7月20日 20:00

ループと再帰の関係

プログラマなら誰もが知っている再帰ですが、よくC言語のポインタと並んで初心者がよくつまづく概念としても有名(?）です。今回はこの再帰(特に末尾再帰について)と基本的な制御構造の一つであるループとの関係について考えてみます。

ループ構文というのは大抵の言語に存在する制御構造ですが、世の中にはループ構文が存在しない言語もたくさんあります(gotoでジャンプしてるわけではありませんよ)。このような言語ではループの代わりに再帰呼び出しを使います。一見するとループと再帰呼び出しは別物のように見えますが、よーく見ていくと実はループと再帰呼び出し(特に末尾再帰)はとてもよく似ているのです。

例えば、次のようなループである範囲の整数を順に標準出力に出力するメソッドは

void loopSample(int min, int max) {
for (int i = min; i < max; i++) {
System.out.println(i);
}
}

ループを使わないで、これと同じ動作をするメソッドは次のように書けます。

void recSample(int min, int max) {
if (min < max) {
System.out.println(min);
recSample(min + 1, max);
}
}

これは末尾再帰という形で再帰呼び出しをすることでループと同等のコードを再帰で記述しています。
では末尾再帰はただの再帰とどう違うのでしょうか。
重複のない順列の個数を求めるループと(末尾再帰でない)普通の再帰呼び出しと末尾呼び出しのコードを比較してみましょう。

①ループ
int loopPermutation(int n, int m) {
int result = 1;
for (int i = m; i > n; i--) {
result *= i;
}
return result;
}

②再帰
int recPermutation(int n, int m) {
if (n >= m) {
return 1;
} else {
return m * recPermutation(n, m - 1);
}
}

③末尾再帰
int tailRecPermutation(int n, int m, int acc) {
if (n <= m) {
return acc;
} else {
return tailRecPermutation(n - 1, m, n * acc);
}
}

重複のない順列の個数というのは、n個の異なる要素からm個の要素を選び出した順列の個数で nPm と表されます(中学で習いましたね)。この値はnの階乗を(n-m)の階乗で割ることで求めることができるのですが、これは n * (n - 1) * ... * (m + 2) * (m + 1)、つまりnから(m+1)までの積求めることができます。

このアルゴリズムをループ、再帰で記述すればそれぞれ①、②のようになることでしょう。②の再帰版は①と同様に動作しますが、再帰が深くなるとスタックオーバーフローを起こします。これは引数やローカル変数をスタックに積んでメソッドを呼び出すためです。

これに対して③の末尾再帰版は引数が一つ増えており、この引数で計算結果を引き回しています。
これらのコードがどのように動作するかを見るために、上の3つのメソッドを実装しているクラスを継承して次のようなコードを実装して動かしてみます。

@Override
int loopPermutation(int n, int m) {
int result = 1;
for (int i = n; i > m; i--) {
result *= i;
System.out.println("Loop loopPermutation(" + this.count + "): i = " + i + ", result = " + result);
this.count++;
}
this.count = 0;
return result;
}
@Override
int recPermutation(int n, int m) {
System.out.println(indent(this.count) + "Call   recPermutation(" + this.count + "): n = " + n + ", m = " + m);
this.count++;
int result = super.recPermutation(n, m);
this.count--;
System.out.println(indent(this.count) + "Return recPermutation(" + this.count + "): result = " + result);
return result;
}
@Override
int tailRecPermutation(int n, int m, int acc) {
System.out.println(indent(this.count) + "Call   tailRecPermutation(" + this.count + "): n = " + n + ", m = " + m + ", acc = " + acc);
this.count++;
int result = super.tailRecPermutation(n, m, acc);
this.count--;
System.out.println(indent(this.count) + "Return tailRecPermutation(" + this.count + "): result = " + result);
return result;
}

このコードを実行すると次のような出力が得られます。

①loopPermutation:
Loop loopPermutation(0): i = 4, result = 4
Loop loopPermutation(1): i = 3, result = 12

②recPermutation:
Call   recPermutation(0): n = 4, m = 2
  Call   recPermutation(1): n = 3, m = 2
    Call   recPermutation(2): n = 2, m = 2
    Return recPermutation(2): result = 1
  Return recPermutation(1): result = 3
Return recPermutation(0): result = 12

③tailRecPermutation:
Call   tailRecPermutation(0): n = 4, m = 2, acc = 1
  Call   tailRecPermutation(1): n = 3, m = 2, acc = 4
    Call   tailRecPermutation(2): n = 2, m = 2, acc = 12
    Return tailRecPermutation(2): result = 12
  Return tailRecPermutation(1): result = 12
Return tailRecPermutation(0): result = 12

②と③のReturnに注目してください。②では呼び出しから返るたびに返り値が異なっています。これに対して③では返り値がすべて同じです。これにより③のコードはReturnするコードを削除することができるようになり、またスタックに引数やローカル変数を保存しておく必要がなくなり、最適化することで結局ループと同じになるのです。

でも③の末尾再帰のコードを大きな数値で実行してみるとスタックオーバーフローするじゃないか、と言う人も居るかもしれません。その通りです。残念ながらJavaはこのような末尾再帰の最適化はしてくれないのでした。(何)

この記事のURL　｜　 更新日時: 2010年7月 6日 20:32

↓ エラトステネスの篩
↓ 探索アルゴリズム (4)
↓ 探索アルゴリズム (3)
↓ 探索アルゴリズム (2)
↓ 探索アルゴリズム (1)
↓ ソートアルゴリズム (14)
↓ フィボナッチ数
↓ ソートアルゴリズム (13)
↓ ソートアルゴリズム(12)
↓ ソートアルゴリズム(11)
↓ ソートアルゴリズム(10)
↓ ソートアルゴリズム(9)
↓ ソートアルゴリズム(8)
↓ ソートアルゴリズム(7)
↓ ソートアルゴリズム(6)
↓ ソートアルゴリズム（5)
↓ ソートアルゴリズム(4)
↓ ソートアルゴリズム(3)
↓ ソートアルゴリズム(2)
↓ ソートアルゴリズム(1)