2017-06-15, 2017-06-22 第10, 11回目 応用１

本日のテーマ

2017-06-15，2017-06-22の２回の間に以下の10個のプログラムを提出してください．

1. コマンドラインで受け取った文字列が特定の文字列かを確認する
2. 文字列の逆順表示
3. yesコマンド：特定文字列を繰り返す．
4. sortコマンド：ファイルの内容をソートする．
5. tacコマンド：ファイルの内容を逆順に表示する．
6. アナログ時計
7. freqコマンド：与えられたテキストファイルに現れる単語の頻度を求める．
8. tailコマンド：与えられたテキストファイルの最後の数行を出力する．
9. 逆ポーランド記法の計算機
10. ２つの文字列間の類似度・距離

応用1 プログラム集の作成

ページのトップに戻る

1. コマンドラインで受け取った文字列が特定の文字列かを確認する

コマンドラインで渡された文字列が特定の文字列（"KSU_AP"）であれば， 「渡された文字列は”KSU_AP”です」と出力してください． 特定の文字列でなければ，「渡された文字列は”KSU_AP”ではなく，”(実際に渡された文字列)”です．」 と出力するプログラムを作成してください．

コマンドライン引数で複数の文字列が渡された場合，全ての文字列に対して判定を行ってください．

クラス名は，ComparingStringとしてください．

実行例

$ java ComparingString hoge KSU KSU_AP KSU_AP2
渡された文字列は "KSU_AP"ではなく"hoge"です．
渡された文字列は "KSU_AP"ではなく"KSU"です．
渡された文字列は "KSU_AP" です．
渡された文字列は "KSU_AP"ではなく"KSU_AP2"です．

参考

• 条件分岐
• 繰り返し
• クラス定義の基本形
• 値の一致性
• コマンドライン引数

ページのトップに戻る

2. 文字列の逆順表示

コマンドライン引数で渡された文字を出力した後，その文字列を逆順に表示してください． クラス名は，ArgsReverserとしてください．

実行例

$ java ArgsReverser abcdefg
abcdefg, gfedcba
$ java ArgsReverser abcdefg foobar
abcdefg, gfedcba
foobar, raboof
$ java ArgsReverser Haruaki Tamada
Haruaki, ikauraH
Tamada, adamaT

ヒント

文字列からn番目の文字を取得する．

• valueというString型の変数で考えます．
• valueのn番目の文字はvalue.charAt(n)で取得できます．
  • 返り値はCharacter型の変数です．
  • nはInteger型です．
  • nが0からvalue.length() - 1以下の範囲で value.charAt(n)は有効な値を返します．
• System.out.printf でCharacter型を出力するときのフォーマット記述子は%cです．
• また，Character型の変数をSystem.out.printに渡しても改行なしで出力されます．

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 文字列の長さを取得する

3. yesコマンド：特定文字列を繰り返す．

無限にyを出力するコマンドyesを作成してください． もし，コマンドライン引数に何か文字が指定された場合，その文字を無限回出力してください． 終了するときは，Ctrl-C で終了してください． クラス名は，Yesにしましょう．

実行例

$ yes
y
y
y
... 途中省略
^C # Ctrl-C を入力し，強制終了
$ yes no
no
no
... 途中省略
^C # Ctrl-C を入力し，強制終了
$ java Yes
y
y
... 途中省略
^C # Ctrl-C を入力し，強制終了
$ java Yes yes
yes
yes
... 途中省略
^C # Ctrl-C を入力し，強制終了

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 知らなかったyesコマンドの真の力

ページのトップに戻る

4. sortコマンド：ファイルの内容をソートする．

コマンドライン引数で与えられたファイルの内容を行単位でソートして出力するコマンド Sorterを作成してください．

実行例

$ cat string.txt
String class represents character strings.
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Strings are constant; their values cannot be changed after they are created.
String buffers support mutable strings.
Because String objects are immutable they can be shared.
$ sort string.txt
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Because String objects are immutable they can be shared.
String buffers support mutable strings.
String class represents character strings.
Strings are constant; their values cannot be changed after they are created.
$ java Sorter string.txt
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Because String objects are immutable they can be shared.
String buffers support mutable strings.
String class represents character strings.
Strings are constant; their values cannot be changed after they are created.
$ cat string2.txt
abra
cada
bra
abc
def
$ java Sorter string2.txt
abc
abra
bra
cada
def

string.txtが必要であればリンクをクリックし，ダウンロードしてください．

ヒント

• まず，ファイルから1行ずつ文字列を読み込みましょう．
• 読み込んだ文字列を ArrayList に追加しましょう．
• Collections.sort に ArrayListの実体を渡し，ソートしましょう．
• ArrayListの要素を順に出力しましょう．

Listのソート

配列のソートはArrays.sortメソッドで行いました． 同じように，Listをソートするメソッドも標準的に用意されています．Collectionsを 利用すると，Listの内容を辞書順に並び替えられます． なお，Collectionsを利用するときは，java.util.Collectionsのインポートが必要です．

ArrayList<String> list = // ArrayListの実体を作成する．
Collections.sort(list); // => list の内容が要素を並び替えたものになっている．

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 配列とList
• 例外機構
• 典型的なファイルからのデータの読み込み方法

ページのトップに戻る

5. tacコマンド：ファイルの内容を逆順に表示する．

ファイルを逆順に表示するコマンドtacを作成してください． 複数のファイルが指定された場合，各ファイルの内容を逆順に表示してください．

クラス名は Tac（catの逆）とします．

実行例

$ cat sample2.txt
ABCDEFG

1234567890
$ java Tac sample2.txt
1234567890

ABCDEFG
$ cat sample3.txt
abracadabra
$ java Tac sample3.txt
abracadabra

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 配列とList
• 例外機構
• 典型的なファイルからのデータの読み込み方法

ページのトップに戻る

6. アナログ時計

EZ.javaを利用して，アナログ時計を描画してください． クラス名は Clockとします．

実行例

この時の時刻は，19時22分25秒．

ヒント

基本的な描画方法

1. 現在時刻を取得する．
2. 背景を描画する．
3. 短針，長針，秒針の両端座標を計算で求める．
4. 短針，長針，秒針をそれぞれ描画する．
5. 適当な時間(1,000ミリ秒（1秒）)スリープする．
   • ただし，何秒かに一回程度，描画されない秒が出てくる．
   • 針の両端座標の計算処理の積み重ねのため．
   • これを防ぐためには，スリープの秒数を少なくする．
   • ただし，そのぶん処理が重くなり，チラツキの原因となる．
   • これらの問題は，ここでは解決する必要はない．
6. 全ての描画をクリアする．
7. 1に戻る．

度数法から弧度法（ラジアン）に変更する

• Math.toRadians に度数法の値(0〜360度)を渡せばラジアン値が得られる．

Double degree = // 度数法による角度
Double radian = Math.toRadians(degree); // 弧度法による角度

針の両端座標の計算

• 中心座標は常に同じ．もう一方の端を毎秒，計算により求める．
• 秒針は degreeOfSeconds = date.getSeconds() * 6.0 - 90 で得られる角度を元に計算する．
• 長針も秒針と同様．date.getSeconds()の代わりに date.getMinutes() を利用する．
• 短針は，degreeOfHours = (date.getHours() * 5 + date.getMinutes() / 12.0) * 6.0 - 90 で値を得る．
  • date.getHours() * 30 - 90で計算すると，例えば，6:30 の時でも短針は一番下を指したままである． そうではなく，長針が進むに従って，短針も少しずつ移動して欲しいため，上記の処理としている．

参考

• 日付を表すDate型
• EZ.java
• アニメーション
• 例外機構
• Javaでのsin, cosの求め方

7. freqコマンド：与えられたテキストファイルに現れる単語の頻度を求める．

与えられたテキストファイル（英文）の中に現れる単語の頻度を求めるプログラムを作成してください． 単語の頻度とは，その単語が文書中に何回現れたかを示す値です．

実行例

$ cat string.txt
String class represents character strings.
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Strings are constant; their values cannot be changed after they are created.
String buffers support mutable strings.
Because String objects are immutable they can be shared.
$ java Frequencies string.txt
All: 1
"abc",: 1
constant;: 1
be: 2
string: 1
instances: 1
.... 以下略

string.txtが必要であればリンクをクリックし，ダウンロードしてください．

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 配列とList
• 例外機構
• 典型的なファイルからのデータの読み込み方法
• Map
• 文字列を特定の文字で区切る（split）

ページのトップに戻る

8. tailコマンド：与えられたテキストファイルの最後の数行を出力する．

与えられたテキストファイルの最後の数行を出力するプログラムを作成してください． 最後の数行もコマンドラインで与えられるものとします． また，数値は必ず正の値が与えられるものと考えて構いません．

実行例

$ cat string.txt
String class represents character strings.
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Strings are constant; their values cannot be changed after they are created.
String buffers support mutable strings.
Because String objects are immutable they can be shared.
$ tail -1 string.txt
Because String objects are immutable they can be shared.
$ java Tail 2 string.txt
String buffers support mutable strings.
Because String objects are immutable they can be shared.
$ java Tail 10 string.txt
String class represents character strings.
All string literals in Java programs, such as "abc", are implemented as instances of this class.
Strings are constant; their values cannot be changed after they are created.
String buffers support mutable strings.
Because String objects are immutable they can be shared.

string.txtが必要であればリンクをクリックし，ダウンロードしてください． 総行数よりも大きな値が指定された場合でもエラーが発生しないようにしてください．

なお，tailコマンドのオプションで指定した-1は負の値を表しているのではなく、 1という数値を表しています。1に付けられている-はオプションを表す記号であり， 負の値を表す記号ではないことに注意してください．

ヒント

最後の数行がどの行から開始すれば良いのかは最初はわかりません． そのため，まずは，全ての行を ArrayListに保存しましょう．

全ての行を保存すると，必要な行を出力するためのインデックスは（全行数-指定行数）から始めれば良いとわかります． そこから最終行までを出力してください．

参考

• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 配列とList
• 例外機構
• 典型的なファイルからのデータの読み込み方法

ページのトップに戻る

9. 逆ポーランド記法の計算機

逆ポーランド記法での計算機を作成しましょう． 逆ポーランド記法とは，後置記法とも呼ばれます． 中置記法と呼ばれる通常の記法は，1 + 2 ですが，これを逆ポーランド記法で書くと，1 2 +となります． コマンドライン引数で，このような計算式を受け取り，計算結果を出力するプログラムを書いてください．

数値は全てDoubleで扱ってください． クラス名は，ReversePolishNotationCalculatorとしましょう．

実行例

$ java ReversePolishNotationCalculator "1 2 +"
3.000000 (1 2 +)
$ java ReversePolishNotationCalculator "1 2 +" "3 4 +"
3.000000 (1 2 +)
7.000000 (3 4 +)
$ java ReversePolishNotationCalculator "1 2 + 9 6 - *"
9.000000 (1 2 + 9 6 - *)

引数で受け取った文字列を逆ポーランド記法で書かれた数式と捉えて，計算してください． 計算結果を出力後，同じ行に計算の元となった数式を１行で出力してください． なお，演算子と数値の間は必ずスペースで区切られているという前提で計算してください．

複数の計算式が指定された場合，一つの数式を１行で出力するようにしてください．

なお，逆ポーランド記法で与えた計算式を中置記法で表すと，次の通りです．

• 1 2 + → 1 + 2
• 3 4 + → 3 + 4
• 1 2 + 9 6 - * → (1 + 2) * (9 - 6)

ヒント

与えられた文字列をスペースで区切って，最初から順に処理していきましょう． 今，見ている文字列（スペースを含まない）が数値の場合は，Listに追加しましょう． 数値でなく演算子の場合は，Listの後ろから2つの数値を取り出し（Listから削除し）， 演算子に従った処理を行って，計算結果をListに追加しましょう．

上記の繰り返しで逆ポーランド記法の計算機は実現できます． 上記の処理内容は，実は，スタック（Stack）そのものです．

参考

• 条件分岐
• 繰り返し
• クラス定義の基本形
• コマンドライン引数
• 配列とList
• 文字列を特定の文字で区切る（split）

ページのトップに戻る

10. ２つの文字列間の類似度・距離

コマンドライン引数で与えらえた2つの文字列の類似度を次の5つの方法で求めてください．

• Simpson係数
• Jaccard係数
• Dice係数
• コサイン類似度
• 編集距離（Levenshtein距離）

クラス名は，StringSimilaritiesとしてください．

Simpson係数（Simpson Index）

2つの集合があったとき，下図のように，両方の集合の要素数のうち短い方で積集合を割ったものが Simpson係数です．

文字列（String型）は，Character型の集合と考えられます． そのため，2つの文字列に含まれる文字種別の数，積集合を計算できれば，Simpson係数が求められます．

Jaccard係数（Jaccard Index）

2つの集合があったとき，右図のように積集合を和集合で割った値がJaccard係数です．

文字列（String型）は，Character型の集合と考えられます． そのため，2つの文字列の積集合，和集合を計算できれば，Jaccard係数が求められます．

Dice係数（Dice Index）

2つの集合があったとき，下図のように積集合の2倍の数を，集合の要素数の和で割ったものが Dice係数です．

文字列（String型）は，Character型の集合と考えられます． そのため，それぞれの文字列に含まれる文字種別の数，積集合を計算できれば，Dice係数が求められます．

コサイン類似度（Cosine similarity）

2つのベクトルを考え，そのベクトルの成す角のコサインがコサイン類似度です． 文字列を文字を要素とするベクトルと考え，2つの文字列から2つのベクトルを構築します．

2つのベクトル $\vec v_1$，$\vec v_2$があるとき，2つのベクトルのコサインは， $\cos \theta =(\vec v_1 \cdot \vec v_2)/(|\vec v_1||\vec v_2|)$で求められます． 文字列から，文字の頻度を計算し，それをベクトルとして扱えば，コサイン類似度が求められます．

"value1"と"value2" の2つの文字列を考えてみましょう． 2つの文字列からそれぞれベクトルを作成して，$\vec{v_1}= \{ 1,1,1,1,1,1,0 \}$， $\vec{v_2} = \{ 1,1,1,1,1,0,1 \}$とします． ベクトルの各要素は， {'v', 'a', 'l', 'u', 'e', '1', '2'}としています． $\cos\theta$を求める式に当てはめると，$\frac{5}{\sqrt{6}\sqrt{6}}$となり， "value1"と"value2" のコサイン類似度は，0.83333…と計算できます．

また，別の例として，"clock"と"watch" の2つの文字列を考えてみましょう． これらから，ベクトルの要素を数えると，$\vec{v_1}= \{ 0, 2, 0, 1, 1, 1, 0, 0 \}$， $\vec{v_2} = \{ 1, 1, 1, 0, 0, 0, 1, 1 \}$です． ベクトルの各要素は， {'a', 'c', 'h', 'k', 'l', 'o', 't', 'w'}としています． $\cos\theta$を求める式に当てはめると，$\frac{2}{\sqrt{7}\sqrt{5}}$となり， "clock"と"watch" のコサイン類似度は，0.338062…と計算できます．

編集距離（Edit Distance; Levenshtein Distance）

編集距離（Levenshtein距離）とは，2つの文字列がどの程度異なっているかを表す距離のことを指します． 一方の文字列から，もう一方の文字列に変更するまでに必要な，１文字の挿入，削除，置換の最小手順で距離を定義しています．

例えば，次の手順を行えば，"distance"から "similarity"に変更できます． この場合，8回の手順で変更できたため，編集距離は 8 となります．

1. "distance"
2. "sistance"．（1文字目のdをsに置換）
3. "simtance"．（3文字目のsをmに置換）
4. "simiance"．（4文字目のtをiに置換）
5. "similance"．（5文字目にlを追加）
6. "similarce"．（7文字目のnをrに置換）
7. "similarie"．（8文字目のcをiに置換）
8. "similarit"．（9文字目のeをtに置換）
9. "similarity"．（10文字目にyを追加）

実際に長さ$n$と$m$の文字列$S_n, S_m$間の編集距離を計算するには， $(n+1)(m+1)$の表が必要になります． この表のことを編集グラフ（Edit graph）と呼びます．

• 表の初期化処理は次の通りです．
  • $n=0$の$i$列目に$i$を代入します．
  • $m=0$の$j$行目に$j$を代入します．
  • 結果として，一番上の行，一番左の列のみに数値が入れられた表が得られます． 値は，左（下）になるにつれ1ずつ増えていきます．
• 表の空いている場所に次のルールに従って値を埋めていきます．
  • 注目しているセルの上，左のセルの値に1を足し，コストとします．($d_1$, $d_2$とします)
  • $S_n$の$i$番目の文字と$S_m$の$j$番目の文字を比較します． 異なっていればコストを1，同じであれば，コストを0とします．
  • 注目しているセルの左上のセルに，先ほど求めたコストを足します（$d_3$とします）
  • $d_1$，$d_2$，$d_3$を比べ，一番小さな値を注目しているセルの値として更新します．
  • 上記をすべてのセルに対して行います．
• すべての値が埋められた表が得られたとき，一番右下の値が編集距離です．

表の作成イメージは以下の通りです． まず，0行目，0列目を埋めます． その後，空いているセルを左上から順に埋めていきます． 当該セルの値は，上，左，左上の3つのセルの値から求められます． 基本的には，上，左，左上のセルの値に1を加算した値を求めます． ただし，それぞれの文字列の対応する文字が一致した場合，左上のセルの値をそのまま利用します（1の加算は行いません）． その上で，3つの数値を比較し，一番小さな値がそのセルの値として表が更新されます．

実行例

$ java StringSimilarities distance similarity
simpson(distance, similarity)=0.500000
jaccard(distance, similarity)=0.333333
dice(distance, similarity)=0.500000
cosine(distance, similarity)=0.530330
edit_distance(distance, similarity)=8
$ java StringSimilarities android ipodtouch
simpson(android, ipodtouch)=0.500000
jaccard(android, ipodtouch)=0.272727
dice(android, ipodtouch)=0.428571
cosine(android, ipodtouch)=0.502519
edit_distance(android, ipodtouch)=7

ヒント

文字列から重複なしの文字の集合を取得する．

以下のプログラムで，文字列から重複なしの文字の集合を取得できます．

ArrayList<Character> getList(String item){
    ArrayList<Character> list = new ArrayList<Character>();
    for(Integer i = 0; i < item.length(); i++){
        Character c = item.charAt(i);
        if(!list.contains(c)){
            list.add(c);
        }
    }
    return list;
}

表の作成

表の作成には，Table.javaを利用してください． Table.javaは左の１行目のように，どんな型を入れるTableにするか， 何行×何桁のTableにするかを決めます． そして，値を設定するには，setメソッドに値とx, yのインデックスを指定します． 値を取得するときは，x, yのインデックスを指定して取得します．

Table<String> table = new Table<String>(41, 21);
table.set("X", 0, 1);
String item = table.get(0, 1);

参考

• クラス定義の基本形
• コマンドライン引数
• 配列とList

ページのトップに戻る