ランレングス符号化
山崎講師ランレングス符号化【Run-length encoding、RLE】は、データ圧縮技術の一種で、同じデータが連続する場合に、その出現回数を繰り返し数として短いデータで表現する手法です。圧縮後のデータを元に戻せる可逆圧縮のアルゴリズムです。
具体的には、例えば「AAAAAAAAAAABBBBCCCDDE」のような文字列をランレングス符号化すると、「A11B4C3DDE」というように、同じ文字が連続する部分を文字と出現回数で表現します。この例ではデータ量は約半分になっています。
このように、同じデータが繰り返し現れる場合には非常に効率的な圧縮が可能ですが、ランレングス符号化はデータにパターンが少ない場合や、ランレングス符号化によってデータサイズが大きくなる場合には効果がありません。以下のプログラムでは3文字以上同じ文字列が連続した場合のみ圧縮することでデータサイズが大きくならないようにしています。
ランレングス符号化は、データ圧縮の分野で幅広く使われています。特に、画像や音声などのデータでは、同じ値やパターンが連続することが多く、ランレングス符号化によって効果的に圧縮できる場合があります。例えば、白黒画像のFAXなどでは白と黒のピクセルが連続するため、大変有効な圧縮アルゴリズムです。
具体的には、以下のような場面でランレングス符号化が使われます。
- ビットマップ画像の圧縮：ビットマップ画像は、ピクセルごとに色情報を持つため、同じ色が連続する場合にはランレングス符号化が効果的です。
- 音声ファイルの圧縮：音声ファイルでは、同じ周波数や音量の波形が続くことが多く、ランレングス符号化によって圧縮できます。
なお、ランレングス符号化は単純な圧縮手法であり、他の高度な圧縮技術と組み合わせて使用することで、より高い圧縮効果を得ることができます。
＜サンプルプログラム＞
public class RunLengthEncoding {
public static String encode(String input) {
if (input == null)
return "";
// 文字列を文字配列に変換する
char[] chars = input.toCharArray();
// 出力用の文字列を初期化する
StringBuilder output = new StringBuilder();
// 同一文字の出現回数を数えるカウンターを初期化する
int count = 1;
// 入力文字列を1文字ずつ走査する
for (int i = 1; i <= chars.length; i++) {
if (i == chars.length || chars[i] != chars[i - 1]) {
// 異なる文字が出現した場合、出現回数を出力文字列に追加する
if (count > 2) {
output.append(chars[i - 1]).append(count);
} else if (count == 2) {
output.append(chars[i - 2]).append(chars[i - 1]);
} else {
output.append(chars[i - 1]);
}
count = 1;
} else {
// 同一文字が続く場合、カウンターをインクリメントする
count++;
}
}
// 出力文字列を返す
return output.toString();
}
public static String decode(String input) {
if (input == null)
return "";
// 文字列を文字配列に変換する
char[] chars = input.toCharArray();
// 出力用の文字列を初期化する
StringBuilder output = new StringBuilder();
// 数字の開始位置を保持する変数を初期化する
int digitStart = -1;
// 入力文字列を1文字ずつ走査する
for (int i = 0; i < chars.length; i++) {
if (Character.isDigit(chars[i])) {
// 数字の場合、数字の開始位置を記憶する
if (digitStart == -1) {
digitStart = i;
}
} else {
// 数字以外の場合、数字の終了位置までの文字列を繰り返し出力する
if (digitStart != -1) {
int count = Integer.parseInt(input.substring(digitStart, i));
char c = chars[digitStart - 1];
for (int j = 1; j < count; j++) {
output.append(c);
}
digitStart = -1;
}
// 数字でない場合、単純に文字を出力する
output.append(chars[i]);
}
}
// 最後の文字が数字で終わっていた場合は、数字の終了位置までの文字列を繰り返し出力する
if (digitStart != -1) {
int count = Integer.parseInt(input.substring(digitStart));
char c = chars[chars.length - 1];
for (int j = 0; j < count; j++) {
output.append(c);
}
}
// 出力文字列を返す
return output.toString();
}
public static void main(String[] args) {
String input = "AAAAAAAAAAABBBBCCCDDE";
String compressed = encode(input);
String decompressed = decode(compressed);
System.out.println("入力文字列: " + input);
System.out.println("圧縮文字列: " + compressed);
System.out.println("伸長文字列: " + decompressed);
}
}＜出力結果＞
| 入力文字列: AAAAAAAAAAABBBBCCCDDE 圧縮文字列: A11B4C3DDE 伸長文字列: AAAAAAAAAAABBBBCCCDDE |
