yes
コマンド:特定文字列を繰り返す.sort
コマンド:ファイルの内容をソートする.tac
コマンド:ファイルの内容を逆順に表示する.freq
コマンド:与えられたテキストファイルに現れる単語の頻度を求める.tail
コマンド:与えられたテキストファイルの最後の数行を出力する.コマンドラインで渡された文字列が特定の文字列("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"です.
コマンドライン引数で渡された文字を出力した後,その文字列を逆順に表示してください.
クラス名は,ArgsReverser
としてください.
$ java ArgsReverser abcdefg
abcdefg, gfedcba
$ java ArgsReverser abcdefg foobar
abcdefg, gfedcba
foobar, raboof
$ java ArgsReverser Haruaki Tamada
Haruaki, ikauraH
Tamada, adamaT
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
に渡しても改行なしで出力されます.無限に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 を入力し,強制終了
コマンドライン引数で与えられたファイルの内容を行単位でソートして出力するコマンド 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が
必要であればこの文章をクリックし,ダウンロードしてください.
ArrayList
に追加しましょう.Collections.sort
に ArrayList
の実体を渡し,ソートしましょう.ArrayList
の要素を順に出力しましょう.配列のソートはArrays.sort
メソッドで行いました.
同じように,ArrayList
をソートするメソッドも標準的に用意されています.Collections.sort
メソッドを利用すると,ArrayList
の内容を辞書順に並び替えられます.
なお,Collections
を利用するときは,java.util.Collections
のインポートが必要です.
ArrayList<String> list = // ArrayListの実体を作成する.
Collections.sort(list); // => list の内容が要素を並び替えたものになっている.
ファイルを逆順に表示するコマンドtac
を作成してください.
複数のファイルが指定された場合,各ファイルの内容を逆順に表示してください.
クラス名は Tac
(cat
の逆)とします.
$ cat sample2.txt
ABCDEFG
1234567890
$ java Tac sample2.txt
1234567890
ABCDEFG
$ cat sample3.txt
abracadabra
$ java Tac sample3.txt
abracadabra
EZ.java
を利用して,アナログ時計を描画してください.
クラス名は Clock
とします.
この時の時刻は,19時22分25秒.
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 の時でも短針は一番下を指したままである.
そうではなく,長針が進むに従って,短針も少しずつ移動して欲しいため,上記の処理としている.EZ.refreshScreen()
を呼び出すと,今まで追加した要素を再描画します.
つまり,これまでに addLine
やaddCircle
などで追加した図形を再描画します.
ここでは,1秒ごとに新たな線を引きたいため,今まで追加した図形を削除する必要があります.
そのために,EZ.refreshScreen()
ではなく,EZ.removeAllEZElements()
を呼び出す必要があります.
もちろん,追加した EZLine
の実体に対して,適切に座標を変更した上で,EZ.refreshScreen()
を呼び出せば期待通りの動作となります.
与えられたテキストファイル(英文)の中に現れる単語の頻度を求めるプログラムを作成してください. 単語の頻度とは,その単語が文書中に何回現れたかを示す値です.
$ 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が
必要であればこの文章をクリックし,ダウンロードしてください.
与えられたテキストファイルの最後の数行を出力するプログラムを作成してください. 最後の数行もコマンドラインで与えられるものとします. また,数値は必ず正の値が与えられるものと考えて構いません.
$ 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
に保存しましょう.
全ての行を保存すると,必要な行を出力するためのインデックスは(全行数-指定行数)から始めれば良いとわかります. そこから最終行までを出力してください.
コマンドラインで与えられたファイル(複数可)をgzipを用いて圧縮してください.
クラス名は GZip
としてください.
gzipの圧縮には,GZIPOutputStream
が利用できます.GZIPOutputStream
を利用するには,java.util.zip.GZIPOutputStream
のインポートが必要です.
$ ls
GZip.java GZip.class
$ java GZip GZip.java # GZip.java を圧縮する.
GZip.java: 1152 bytes -> 426 bytes (36.98%)
$ ls
GZip.java GZip.java.gz GZip.class # Gzip.java.gz が作成されている
$ mv GZip.java GZip.java.back # Gzip.java の名前を変更する.
$ gunzip GZip.java.gz # Gzip.java.gz を解凍し,Gzip.javaを得る.
$ ls
GZip.java GZip.java.back GZip.java.gz GZip.class
$ java GZip GZip.java GZip.class
GZip.java: 1152 bytes -> 426 bytes (36.98%)
GZip.class: 1708 bytes -> 1010 bytes (59.13%)
FileOutputStream
を GZIPOutputStream
でラップすれば圧縮が行えます.
FileWriter
を PrintWriter
でラップするのと同じ要領でプログラムを書いてください.InputStream
)から1バイトずつ読み込み,出力ストリームに書き出してください.
InputStream
型のread
メソッド(引数なし)を用いてください.1バイト単位で読み込みます.GZIPOutputStream
のwrite
メソッドを用いてください.読み込んだ1バイトを書き出せば良いです.Reader
/Writer
ではなく InputStream
/OutputStream
を利用してください.File
型変数のlength()
メソッドで調べられます.InputStream
/OutputStream
型
EZ.java
を利用し,実行例のような図形を描きましょう.
このような図形をシェルピンスキーのギャスケットと呼びます.
デフォルトでは,$n=3$とし,コマンドライン引数により,$n$を指定できるようにしてください.
クラス名は SierpinskiGasket
としてください.
上の画像をクリックすると$n=0$から$n=5$まで変化します.
400 - 190 * Math.sqrt(2)
で求められます.drawGasket
メソッドに先ほどの頂点3点と$n$を渡します.drawGasket
の処理は次の通りです.
0. $n$が0の場合は何もせずに処理を終わらせます.
drawGasket
を呼び出します.drawGasket
を呼び出します.drawGasket
を呼び出します.座標を表す型 Point
型.
2つのPoint
型変数を受け取り,中点となるPoint
型変数を返す midpoint
メソッド.
2つのDouble
型を受け取り,Point
型変数を返すpoint
メソッド.
Point
型は Double
型で座標を保持していますが,EZ.drawLine
にはInteger
型で値を渡す必要がある点に注意しましょう.
Double
型の変数x
をInteger
型に変換するには,x.intValue()
のようにメソッドを呼び出してください.逆ポーランド記法での計算機を作成しましょう.
逆ポーランド記法とは,後置記法とも呼ばれます.
中置記法と呼ばれる通常の記法は,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行で出力してください. なお,演算子と数値の間は必ずスペースで区切られているという前提で計算してください.
複数の計算式が指定された場合,一つの数式を1行で出力するようにしてください.
なお,逆ポーランド記法で与えた計算式を中置記法で表すと,次の通りです.
1 2 +
→ 1 + 2
3 4 +
→ 3 + 4
1 2 + 9 6 - *
→ (1 + 2) * (9 - 6)
与えられた文字列をスペースで区切って,最初から順に処理していきましょう.
今,見ている文字列(スペースを含まない)が数値の場合は,ArrayList
に追加しましょう.
数値でなく演算子の場合は,ArrayList
の後ろから2つの数値を取り出し(ArrayList
から削除し),
演算子に従った処理を行って,計算結果をArrayList
に追加しましょう.
上記の繰り返しで逆ポーランド記法の計算機は実現できます. 上記の処理内容は,実は,スタック(Stack)そのものです.
コマンドライン引数で与えらえた2つの文字列の類似度を次の5つの方法で求めてください.
クラス名は,StringSimilarities
としてください.
2つの集合があったとき,下図のように,両方の集合の要素数のうち短い方で積集合を割ったものが Simpson係数です.
文字列(String
型)は,Character
型の集合と考えられます.
そのため,2つの文字列に含まれる文字種別の数,積集合を計算できれば,Simpson係数が求められます.
なお,それぞれの要素数は文字の長さではなく,文字列から重複を取り除いた長さを用いる点に注意してください.
つまり,android
という文字列の長さは,7ですが,重複を取り除いた時の長さは6になります
(d
が2つ含まれています).この6で計算してください.
2つの集合があったとき,右図のように積集合を和集合で割った値がJaccard係数です.
文字列(String
型)は,Character
型の集合と考えられます.
そのため,2つの文字列の積集合,和集合を計算できれば,Jaccard係数が求められます.
Simpson係数と同じく,文字列の長さではなく,重複を取り除いた長さを用いてください.
2つの集合があったとき,下図のように積集合の2倍の数を,集合の要素数の和で割ったものが Dice係数です.
文字列(String
型)は,Character
型の集合と考えられます.
そのため,それぞれの文字列に含まれる文字種別の数,積集合を計算できれば,Dice係数が求められます.
Simpson係数と同じく,文字列の長さではなく,重複を取り除いた長さを用いてください.
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…と計算できます.
$ java StringSimilarities distance similarity
simpson(distance, similarity)=0.500000
jaccard(distance, similarity)=0.333333
dice(distance, similarity)=0.500000
cosine(distance, similarity)=0.530330
$ java StringSimilarities android ipodtouch
simpson(android, ipodtouch)=0.500000
jaccard(android, ipodtouch)=0.272727
dice(android, ipodtouch)=0.428571
cosine(android, ipodtouch)=0.502519
以下のプログラムで,文字列から重複なしの文字の集合を取得できます.
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;
}
編集距離(Edit distance, Levenshtein距離; levenshtein distance)とは,2つの文字列がどの程度異なっているかを表す距離のことを指します. 一方の文字列から,もう一方の文字列に変更するまでに必要な,1文字の挿入,削除,置換の最小手順で距離を定義しています.
例えば,次の手順を行えば,"distance"
から "similarity"
に変更できます.
この場合,8回の手順で変更できたため,編集距離は 8 となります.
"distance"
"sistance"
.(1文字目のd
をs
に置換)"simtance"
.(3文字目のs
をm
に置換)"simiance"
.(4文字目のt
をi
に置換)"similance"
.(5文字目にl
を追加)"similarce"
.(7文字目のn
をr
に置換)"similarie"
.(8文字目のc
をi
に置換)"similarit"
.(9文字目のe
をt
に置換)"similarity"
.(10文字目にy
を追加)実際に長さ$n$と$m$の文字列$S_n, S_m$間の編集距離を計算するには, $(n+1)(m+1)$の表が必要になります. この表のことを編集グラフ(Edit graph)と呼びます.
表の作成イメージは以下の通りです. まず,0行目,0列目を埋めます. その後,空いているセルを左上から順に埋めていきます. 当該セルの値は,上,左,左上の3つのセルの値から求められます. 基本的には,上,左,左上のセルの値に1を加算した値を求めます. ただし,それぞれの文字列の対応する文字が一致した場合,左上のセルの値をそのまま利用します(1の加算は行いません). その上で,3つの数値を比較し,一番小さな値がそのセルの値として表が更新されます.
コマンドライン引数で与えられた全ての文字列間の編集距離を計算するプログラムを作成してください.
ファイル名はEditDistanceCalculator.java
としてください.
表の作成には,第9講で作成したTable.java
を利用してください.
Table table = new Table();
table.setSize(41, 21);
table.set(0, 1, 10);
Integer value = table.get(0, 1); // 10が取得できる.
$ java EditDistanceCalculator clock watch
edit_distance(clock, watch)=4
$ java EditDistanceCalculator macos linux windows android ios
edit_distance(macos, linux)=5
edit_distance(macos, windows)=5
edit_distance(macos, android)=6
edit_distance(macos, ios)=3
edit_distance(linux, windows)=5
edit_distance(linux, android)=7
edit_distance(linux, ios)=4
edit_distance(windows, android)=5
edit_distance(windows, ios)=4
edit_distance(android, ios)=6