情報処理IIIA（Javaプログラミング入門）第12回

目次	索引
12.1 文字列 12.1.1 文字列の操作 12.1.2 文字列バッファ 12.1.3 整数と文字列 12.2 文字と文字列 12.2.1 文字の操作 12.2.2 データ圧縮 12.2.3 暗号 12.3 演習12 12.4 レポート課題	暗号化暗号文解読鍵シーザー暗号力まかせ法テキストパターン平文復号復号符号化文字列探索文字列バッファランレングス符号

文字列、すなわち String クラスのインスタンスは、一度生成されますとその内容は変更できません。文字列 "Good morning!" の mor を eve に置き換えることができないのです。内容を変更するには、文字列ではなく文字列バッファというものを用います。 文字列バッファ （ string buffer ）とは、組み込みのクラス StringBuffer のインスタンスのことです。文字列バッファに対しては、文字の置き換え、追加、挿入などができます。文字列を加工するには、いったん文字列バッファに変換し、処理のあと再び文字列に変換すればよいのです。

文字列を文字列バッファに変換するには、 StringBuffer クラスのコンストラクタを用います。逆に、文字列バッファを文字列に変換するには、インスタンスメソッド toString() を呼び出します。

String s1 = "Good morning!";
StringBuffer s2 = new StringBuffer(s1);
s2.setCharAt(5, 'e');
s2.setCharAt(6, 'v');
s2.setCharAt(7, 'e');
String s3 = s2.toString();

としますと、 s3 には文字列 "Good evening!" が格納されます。ここで、メソッド

void setCharAt (int i, char c)

は、そのインスタンスの i 番目の文字を c に置き換えるものです。

また、 StringBuffer クラスについては以下の通りです。

StringBuffer append (String s): そのインスタンスに文字列 s を追加する。
StringBuffer append (char c): そのインスタンスに文字 c を追加する。
char charAt (int i): そのインスタンスの i 番目の文字を返す。
StringBuffer insert (int i, String s): そのインスタンスの i 番目の位置に文字列 s を挿入する。
StringBuffer insert (int i, char c): そのインスタンスの i 番目の位置に文字 c を挿入する。
int length (): そのインスタンスの文字数を返す。
void setCharAt (int i, char c): そのインスタンスの i 番目の文字を文字 c に置き換える。
String toString (): そのインスタンスを文字列に変換して返す。

12.1.3 整数と文字列

Integer クラスでは、整数（ int 型）の変換に関するメソッドがいくつか提供されています。その中では、以下のものが重要です。

static int parseInt (String s): 文字列 s を整数（ int 型）に変換して返す。
static String toString (int i): 整数（ int 型）を文字列に変換して返す。

ここで、コマンドライン引数から整数を一つ取り出すプログラム

/* 1*/ class FirstArgument
/* 2*/     public static void main (String[] args) {
/* 3*/         int x = Integer.parseInt(args[0]);
/* 4*/         System.out.println(x);
/* 5*/     }
/* 6*/ }

b00a001@Ampere:~/java% java FirstArgument 100
100
b00a001@Ampere:~/java%

を思い出してください。このプログラムの3行目の意味が、ここでやっと明らかになります。

このプログラムを実行しますと、変数 args には文字列の配列が格納されます。この配列は、 args[0] がはじめのコマンドライン引数、 args[1] が次のコマンドライン引数、…となるものです。上記の場合では、 args[0] に文字列 "100" が格納されます。そして、クラスメソッド parseInt によって文字列 "100" が整数 100 に変換されます。最後に、この整数 100 が変数 x に格納されるのです。

12.2 文字と文字列

12.2.1 文字の操作

前回説明した通り、文字は内部では整数として処理されます。したがって、文字が等しいかどうかは、関係演算子 == を用いて表します。また、 > や < などは、文字符号の大小関係を意味します。

例えば、

if (c == 'Z') {
    ...
}

は c が文字 Z ならば…ですし、

if (c > 'Z') {
    ...
}

は c の文字符号が Z の文字符号より大きいならば…です。

文字を1増加させることは、文字符号を1増加させることになります。ただし、このことを

c = c + 1;

と書きますと、エラーになります。これは、足し算によって右辺が整数（ int 型）と見なされるからです。整数を文字に変換するには、

c = (char) (c + 1);

と書きます。逆に、整数と見なされることを利用することもできます。文字 c が数字である場合、式

c - '0'

はその数字の表す数になります。

文字に関するメソッドは、組み込みのクラスである Character クラスで提供されています。この中で重要なものは以下の通りです。

static boolean isDigit (char c): 文字 c が数字ならば true を返す。そうでなければ false を返す。
static boolean isLowerCase (char c): 文字 c がアルファベットの小文字ならば true を返す。そうでなければ false を返す。
static boolean isSpace (char c): 文字 c がホワイトスペース（スペース、水平タブ、改行など）ならば true を返す。そうでなければ false を返す。
static boolean isUpperCase (char c): 文字 c がアルファベットの大文字ならば true を返す。そうでなければ false を返す。
static char toLowerCase (char c): 文字 c がアルファベットの大文字ならば、それを小文字に変換して返す。そうでなければそのまま返す。
static char toUpperCase (char c): 文字 c がアルファベットの小文字ならば、それを大文字に変換して返す。そうでなければそのまま返す。

12.2.2 データ圧縮

文字列の応用例として、 ランレングス符号 （ run-length coding ）というデータ圧縮法を取り上げます。ここでは、ランレングス符号を復号して、もとのイメージを画面に出力します。なお、復号（ decode ）するとは 符号化 （ encode ）されたデータを元に戻すことです。ランレングス符号は、ファックス伝送の基本にもなっています。ファックス伝送の仕組みを簡単に紹介し、その中でランレングス符号について説明します。

ファックス伝送は、はじめに送信側が紙面イメージを読み込みます。このとき、紙面イメージを75分の1インチ程度の単位で格子状に分割します。そして、光学的な方法でそれぞれの升を白か黒かに決定します。升を横にたどっていき、右端に達したら左端に戻るということを、紙面がつきるまで繰り返し、白黒の列を作ります。最後に、この白黒データを受信側に送信します。

図 12.1 白黒データと紙面イメージ

受信側では、まずこの白黒データを受け取ります。そして、白黒データと一緒に紙面の升をたどっていき、データが黒ならばその部分を黒く記録します。これを繰り返しますと、もとの紙面イメージができあがるのです。

ここで、白と黒をそれぞれ W と B で表わすことにしまして、送信側が白黒データ

WWWWWBBBBBBBWWWWWWWWWWWWWWWWWWWWWWWWWWWBBBBBWWWWWW

を構成したとします。白黒データが長ければ長いほど、伝送に時間がかかりますので、なるべく短くしたいです。そこで、5個の W 、7個の B 、27個の W 、…、すなわち

5W7B27W5B6W

という符号化データを送ることにします。これがランレングス符号です。受信側では、 5W を WWWWW に置き換え、 7B を BBBBBBB に置き換え、…という復号操作を行ないますと、データを元に戻すことができます。

ランレングス符号は、同じ文字が何度も繰り返されるデータほど効果を発揮します。なお、実際に圧縮する場合には、数の表現に工夫が必要です。

今、受信側がランレングス符号

16WE7W2B7WE7W2B7WE6W1B1W2B6WE6W1
B1W2B6WE5W1B3W2B5WE5W1B3W2B5WE4W
1B5W2B4WE4W1B5W2B4WE3W1B7W2B3WE3
W10B3WE2W1B9W2B2WE2W1B9W2B2WE1W1
B11W2B1WE1W1B11W2B1WE3B9W4BE

を受け取ったとします。これを復号して、元の紙面イメージを画面に出力することが、このプログラムの目的です。画面では、例えば白を . で、黒を * で表します。なお、文字 E は紙の右端を表すものとします。画面では改行します。

アルゴリズムは次のようになります。

ループ制御変数 i を宣言する。
文字を格納する変数 c を宣言する。
白黒の繰返し回数を表す変数 times を宣言し、初期値を0とする。
String 型の変数 code を宣言し、受信した符号で初期化する。
i の値を0から符号の長さ未満の間増加させながら以下を繰り返す。｛
c の値を符号の i 番目の文字とする。
もし c が数字ならば、｛
times の値を10倍して c の表す数を加える。
｝そうでなくて、 c が W ならば、｛
. を times 回、改行なしで出力する。
times の値を0にする。
｝そうでなくて、 c が B ならば、｛
* を times 回、改行なしで出力する。
times の値を0にする。
｝そうでなくて、 c が E ならば、｛
改行する。
times の値を0にする。
｝どれでもないならば、｛
（何もしない）
｝
｝

プログラムは以下のようになります。

/* 1*/ class RunLength {
/* 2*/     public static void main (String[] args) {
/* 3*/         int i;
/* 4*/         char c;
/* 5*/         int times = 0;
/* 6*/         String code = "16WE7W2B7WE7W2B7WE6W1B1W2B6WE6W1"
/* 7*/                       + "B1W2B6WE5W1B3W2B5WE5W1B3W2B5WE4W"
/* 8*/                       + "1B5W2B4WE4W1B5W2B4WE3W1B7W2B3WE3"
/* 9*/                       + "W10B3WE2W1B9W2B2WE2W1B9W2B2WE1W1"
/*10*/                       + "B11W2B1WE1W1B11W2B1WE3B9W4BE";
/*11*/         for (i = 0; i < code.length(); i++) {
/*12*/             c = code.charAt(i);
/*13*/             if (Character.isDigit(c)) {
/*14*/                 times = times * 10 + c - '0';
/*15*/             } else if (c == 'W') {
/*16*/                 printChars('.', times);
/*17*/                 times = 0;
/*18*/             } else if (c == 'B') {
/*19*/                 printChars('*', times);
/*20*/                 times = 0;
/*21*/             } else if (c == 'E') {
/*22*/                 System.out.println();
/*23*/                 times = 0;
/*24*/             } else {
/*25*/             }
/*26*/         }
/*27*/     }
/*28*/     static void printChars (char c, int times) {
/*29*/         int i;
/*30*/         for (i = 0; i < times; i++) {
/*31*/             System.out.print(c);
/*32*/         }
/*33*/     }
/*34*/ }

b00a001@Ampere:~/java% java RunLength
................
.......**.......
.......**.......
......*.**......
......*.**......
.....*...**.....
.....*...**.....
....*.....**....
....*.....**....
...*.......**...
...**********...
..*.........**..
..*.........**..
.*...........**.
.*...........**.
***.........****
b00a001@Ampere:~/java%

12.2.3 暗号

もう一つの応用例として、シーザー暗号を取り上げます。 シーザー暗号 （ Caesar cipher ）とはシーザー（カエサル）が用いたとされる暗号化の方法です。また、 暗号化 （ encryption ）とは、秘密にしたいメッセージ（平文、 plaintext ）を特定の方法で第三者には読めない形式（ 暗号文 、 ciphertext ）にすることです。

暗号を用いた通信は、一般的には次の通りです。まず、メッセージの送信者は、暗号化の方法の他に、鍵（ key ）とよばれるデータを決定します。そして、メッセージと鍵から暗号文を構成し、受信者に送信します。受信者は、暗号化の方法とその鍵を知っています。暗号文を受けとりますと、鍵を使って暗号文を元のメッセージに戻します（復号、 decryption ）。第三者は、暗号化の方法は知っていても鍵を知らないので、元のメッセージに戻すことが困難になります。なお、鍵を使わずに元のメッセージに戻すことを解読（ cryptanalysis ）と言います。

図 12.2 暗号化と復号

ここでは簡単のため、平文はアルファベット大文字の並びとします。また、スペースや各種記号は解読のヒントになりますので取り除いておきます。

シーザー暗号では、鍵 K は整数です。平文のアルファベットを一文字ずつ K だけずらしたアルファベットに置き換えて、暗号化を行ないます。例えば K = 3 でしたら、平文

MYNAMEISKYOKOAZUMA（私の名前は東京子です。）

は暗号文

PBQDPHLVNBRNRDCXPD

に暗号化されます。アルファベットの置き換えは以下の表の通りです。 Y が B に置き換えられることに注意してください。

表 12.1 シーザー暗号でのアルファベットの置き換え（鍵 K = 3 の場合）

平文	A	B	C	D	E	F	G	H	I	J	K	L	M
暗号文	D	E	F	G	H	I	J	K	L	M	N	O	P

平文	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
暗号文	Q	R	S	T	U	V	W	X	Y	Z	A	B	C

この表を逆にたどりますと復号ができます。 K = 26 - 3 = 23 としてもう一度暗号化することでも復号可能です。

なお、シーザー暗号はすぐに解読されます。なぜならば、 K = 1 の場合、 K = 2 の場合、…、 K = 25 の場合をすべて確かめ、その中から意味の通るものを選べばよいからです。ここでシーザー暗号を取り上げたのは、暗号の仕組みに慣れるためです。

アルゴリズムは次のようになります。

ループ制御変数 i を宣言する。
文字を格納する変数 c を宣言する。
鍵を格納する変数 key を宣言し、コマンドライン引数 args[0] で初期化する。
String 型の変数 plain を宣言し、コマンドライン引数 args[1] の平文で初期化する。
i の値を0から平文の長さ未満の間増加させながら以下を繰り返す。｛
c の値を平文の i 番目の文字とする。
もし c がアルファベットの大文字ならば、｛
c の値を key ずらす。
もし c が Z 以降になったならば、｛
c の値を 26 戻す。
｝
｝
c の値を改行なしで出力する。
｝
改行する。

プログラムは以下のようになります。

/* 1*/ class CaesarCipher {
/* 2*/     public static void main (String[] args) {
/* 3*/         int i;
/* 4*/         char c;
/* 5*/         int key = Integer.parseInt(args[0]);
/* 6*/         String plain = args[1];
/* 7*/         for (i = 0; i < plain.length(); i++) {
/* 8*/             c = plain.charAt(i);
/* 9*/             if (Character.isUpperCase(c)) {
/*10*/                 c = (char) (c + key);
/*11*/                 if (c > 'Z') {
/*12*/                     c = (char) (c - 26);
/*13*/                 }
/*14*/             }
/*15*/             System.out.print(c);
/*16*/         }
/*17*/         System.out.println();
/*18*/     }
/*19*/ }

b00a001@Ampere:~% java CaesarCipher 3 MYNAMEISKYOKOAZUMA
PBQDPHLVNBRNRDCXPD
b00a001@Ampere:~% java CaesarCipher 23 PBQDPHLVNBRNRDCXPD
MYNAMEISKYOKOAZUMA
b00a001@Ampere:~%

12.3 演習12

文字列探索を行うプログラムを作成してください。ここで、 文字列探索 （ string search ）とは、ある文字列（ テキスト 、 text ）の中に別の文字列（ パターン 、 pattern ）が現れるかどうかを調べることです。パターンが現れる場合は、最初に現れる位置を見つけることにします。

文字列探索は応用上重要ですので、色々なアルゴリズムが提案されています。ここでは、力まかせ法とよばれるアルゴリズムを紹介します。

力まかせ法 （ brute-force algorithm ）では、はじめにテキストとパターンを左に揃えます。パターンの左端から一文字ずつテキストと比較して、一致する間は右に読み進みます。もしパターンを読み終えたならば、パターンは現れると結論づけます。もしテキストを読み終えたならば、パターンは現れないと結論づけます。途中で文字が一致しなかったら、パターンを一つ右にずらし、パターンの左端からやり直します。

力まかせ法で間違えやすい点は、途中で文字が一致しなかったときに、パターンを「そこの」一つ右にずらしてしまうことです。例として、

MEDITERRANEAN

（地中海）というテキストと RAN というパターンで文字列探索を行います。テキストに文字 R が現れるまでは、パターンを一つずつ右にずらしています。下図の丸印の位置で R が現れますが、次の文字は一致しません。ここで、パターンを「そこの」一つ右にずらしてしまいますと、見つけるべき文字列 RAN を見落としてしまうのです。

図 12.3 文字列探索（失敗例）

文字が一致しなかったときに、パターンを「前回の」一つ右にずらせば、見落としはなくなります。

図 12.4 文字列探索（成功例）

プログラムでは、テキストとパターンをコマンドライン引数で与えます。パターンが現れる場合は、最初に現れる位置（0文字目から数える）を出力します。パターンが現れない場合は、"Not found."と出力するものとします。また、反復の途中でプログラムを終わらせるには、 return; と書きます。 main もメソッドですので、そこでメソッドの実行が終了するわけです。

アルゴリズムは次のようにします。

テキストを読む位置を表す変数 textPos を宣言し、0 で初期化する。
パターンを読む位置を表す変数 patternPos を宣言し、0 で初期化する。
パターンの左端に対応するテキストの位置を表す変数 textPos0 を宣言し、0 で初期化する。
String 型の変数 text を宣言し、コマンドライン引数 args[0] で初期化する。
String 型の変数 pattern を宣言し、コマンドライン引数 args[1] で初期化する。
以下を無限に繰り返す。｛
もし patternPos がパターンの長さ以上ならば、｛
textPos0 の値を出力する。
return で終了する。
｝そうでなくて、 textPos がテキストの長さ以上ならば、｛
"Not found."と出力する。
return で終了する。
｝そうでなくて、テキストの textPos 番目の文字と、パターンの patternPos 番目の文字が等しいならば、｛
textPos の値を1増加させる。
patternPos の値を1増加させる。
｝どれでもないならば、｛
textPos0 の値を1増加させる。
textPos の値を textPos0 とする。
patternPos の値を0とする。
｝
｝

b00a001@Ampere:~/java% java StringSearch MEDITERRANEAN RAN
7
b00a001@Ampere:~/java% java StringSearch CHOCOCOCOA COCOA
5
b00a001@Ampere:~/java% java StringSearch INTERNATIONAL ALL
Not found.
b00a001@Ampere:~/java%

12.4 レポート課題

今日の演習12に従ってJavaプログラムを作成し、そのプログラムをkonishi@twcu.ac.jpあてにメールで提出してください。メールには、学生番号、氏名、科目名、授業日（12/12）を明記してください。

[小西ホームページ] [目次・索引] [前の授業] [次の授業]