ScalaでSGBのデータ処理

Table of Contents

1 概要

Stanford Graph Base (SGB)のデータ sgb-words.txt を使って, Scalaでのプログラミングについて学ぶ.

以下は,作成中である.

1.1 注意

本Webページの作成には Emacs org-mode を用い, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.

2 sgb-words.txt

sgb-words.txt は,チューリング賞受賞者の Knuth氏 が収集した, 5文字からなる英単語のデータファイルである. 同氏による著名な教科書"The Art of Computer Programming"の演習問題などで利用されている.

全部で5757語が含まれており,出現頻度の高いものから順に1行に1語が記載されている (複数形や過去形なども含まれている). 1行目は which で,最後の5757行目は pupal である.

このデータを XXX ディレクトリに保存するには以下のようにする.

$ cd ~/XXX
$ curl -O http://www-cs-faculty.stanford.edu/~knuth/sgb-words.txt

以下のようにすると5757行,5757語,34542バイトであることが確認できる.

$ wc sgb-words.txt 
5757  5757 34542 sgb-words.txt

行数だけを表示したい場合には,以下のようにする.

$ wc -l sgb-words.txt 
5757 sgb-words.txt

出現頻度が1000番目の単語は何だろうか? 以下のように less コマンドを -N オプションを指定して起動し, スペースキーを押してスクロールしていけば,確認できる.

$ less -N sgb-words.txt

less コマンドを終了するには,'q'のキーを押す. また,'h'のキーを押せばヘルプが表示される.

あるいは head コマンドと tail コマンドを組み合すほうが簡単だ.

$ head -1000 sgb-words.txt | tail -1
ditch

"head -1000 sbg-words.txt"によって,最初の1000行が取り出され, "tail -1"によって,その最後の1行目が取り出されている. ここで,縦棒 '|' は,その前のコマンドの標準出力を,その後のコマンドの 標準入力に接続する指示であり,パイプと呼ばれる.

英字'e'を含む単語がいくつあるかを調べるにはどうすれば良いだろうか? 以下のように grep コマンドを使えば,それがわかる.

$ grep e sgb-words.txt | wc -l
2658

"grep e sbg-words.txt"によって,'e'を含む行が取り出され, "wc -l"によって,その行数が求められている.

grep コマンドの -v オプションを指定すると,英字'e'を含まない行を取り出せる.

$ grep -v e sgb-words.txt | wc -l
3099

英字'e'も'a'も含まない単語はいくつあるだろうか? 後述の正規表現を用いる方法もあるが,パイプを使えば以下のようにできる.

$ grep -v e sgb-words.txt | grep -v a | wc -l
1770

そのような単語で,最も出現頻度の高いものから最初の5個は何だろうか?

$ grep -v e sgb-words.txt | grep -v a | head -5
which
would
words
could
first

もちろん,以下のようにして最初の5個を見てみるのでも良い.

$ grep -v e sgb-words.txt | grep -v a | less

grep コマンドの -n オプションを指定すると,何行目にあるかがわかる.

$ grep -n japan sgb-words.txt
5048:japan

あるいは less コマンド中で,'/'キーを押し,検索語"japan"を指定する方法もある.

$ less -N sgb-words.txt

2.1 練習問題

  1. 出現頻度が2000番目の単語は何か.
    (解答例)

    以下のようにする.

    $ head -2000 sgb-words.txt | tail -1
    galls
    
  2. 英字'e'も'a'も含まない単語で,最も出現頻度の低いものは何か.
    (解答例)

    以下のようにする.

    $ grep -v e sgb-words.txt | grep -v a | tail -1
    biffy
    

    次のようにすれば,元々で何番目の出現頻度の単語なのかがわかる.

    $ grep -n -v e sgb-words.txt | grep -v a | tail -1
    5756:biffy
    
  3. 英字'e'も'a'も含まない単語で,10番目の出現頻度のものは何か.
    (解答例)

    以下のようにする.

    $ grep -v e sgb-words.txt | grep -v a | head -10 | tail -1
    found
    
  4. 出現頻度が1000番目以内で,英字'e'も'a'も含まない単語はいくつあるか.
    (解答例)

    以下のようにする.

    $ head -1000 sgb-words.txt | grep -v e | grep -v a | wc -l
    285
    
  5. 英字'k', 'o', 'b', 'e'をすべて含む単語はあるか.
    (解答例)

    以下のようにする.

    $ grep k sgb-words.txt | grep o | grep b | grep e
    broke
    bloke
    kebob
    

3 正規表現

grep コマンドを使うと,指定した文字列を含む(あるいは含まない)行を検索できた. egrep コマンドを使うと,オートマトンの講義等で学ぶ正規表現を用いて検索できる (より正確には, grep では簡単な正規表現しか利用できないが, egrep では 通常の正規表現が利用できる).

例えば,'a'から始まる単語は以下のようにして検索できる(最初の3語だけを表示している).

$ egrep '^a' sgb-words.txt | head -3
about
after
again

ここで'^'は,文字列の先頭を表す正規表現の記号である. また,上記および以下ではshellによる式の評価を避けるため, 正規表現の文字列は常にシングルクォート(')で囲んで記述している. shellによって評価されない式の場合は,シングルクォートで囲む必要はないが, 簡単のためそのようにする.

次に,'a'から終わる単語は以下のようにして検索できる(最初の3語だけを表示している).

$ egrep 'a$' sgb-words.txt | head -3
extra
opera
drama

ここで'$'は,文字列の最後を表す正規表現の記号である.

任意の1文字を表すには'.'を用いる.したがって,以下は2文字目が'a'の単語を検索している.

$ egrep '^.a' sgb-words.txt | head -3
water
large
earth

いずれかの文字とマッチさせたい場合は,それらの文字を'[]'で囲む. 例えば,以下は'a', 'e', 'i', 'o', 'u'のいずれかの文字で始まる単語を検索している.

$ egrep '^[aeiou]' sgb-words.txt | head -3
about
other
after

文字コードが連続している場合は'-'を使って,文字の範囲を指定できる. 以下は'w', 'x', 'y', 'z'のいずれかの文字で終わる単語を検索している.

$ egrep '[w-z]$' sgb-words.txt | head -3
every
below
study

すると,以下はどんな単語を検索しているだろうか?

$ egrep '[a-e][a-e][a-e][a-e][a-e]' sgb-words.txt

これは,'a'から'e'までの文字だけの単語を検索している(すべての単語が5文字なことに注意). 繰り返しを表す'*'を用いれば,これは以下のようにもできる(こちらのほうが簡単だ).

$ egrep '^[a-e]*$' sgb-words.txt

つまり,先頭の後,'a'から'e'の文字が0回以上繰り返され,文字列の最後に至る場合だけが マッチする(オートマトンの動作を思い出そう).

1回以上の繰り返しには'+'を用いる.今の場合,どちらでも同じになる.

$ egrep '^[a-e]+$' sgb-words.txt

では,母音 '[aeiou]' 以外の文字だけからなる単語を探すにはどうすれば良いか? オプション -v を用いれば可能だ.

$ egrep -v '[aeiou]' sgb-words.txt | head -3
gypsy
myths
hymns

しかし,このオプションを用いずに,正規表現だけで書くことはできないだろうか. 母音以外の文字にマッチする正規表現は,すべてを列挙して '[bcdfghjklmnpqrstvwxyz]' と書ける(大変だ). あるいは,文字の範囲も利用して '[b-df-hj-np-tv-z]' でも良い(少し短くなった).

ところが,便利な表現がある.'[]'中の先頭に'^'を書くと,指定された文字以外とマッチする. すなわち '[^aeiou]' は母音以外の文字とマッチする正規表現である. 結局,以下で母音以外の文字だけからなる単語を探すことができる.

$ egrep '^[^aeiou]*$' sgb-words.txt | head -3
gypsy
myths
hymns

正規表現には,他にも様々な表現方法があるが,とりあえず以上で説明を終える.

3.1 練習問題

  1. 先頭が'z'の単語はいくつあるか.
    (解答例)

    以下のようにする.

    $ egrep '^z' sgb-words.txt | wc -l
    
  2. 最後から2番目の文字が'z'の単語はいくつあるか.
    (解答例)

    以下のようにする.

    $ egrep 'z.$' sgb-words.txt | wc -l
    
  3. 先頭が'a'で最後も'a'の単語はいくつあるか.
    (解答例)

    以下のようにする.

    $ egrep '^a...a' sgb-words.txt | wc -l
    

    もちろん,以下のようにもできる

    $ egrep '^a' sgb-words.txt | egrep 'a$' | wc -l
    
  4. 'k', 'o', 'b', 'e'の文字だけからなる単語はあるか.
    (解答例)

    以下のようにする.

    $ egrep '^[kobe]+$' sgb-words.txt
    
  5. 2文字目が母音以外の単語はいくつあるか.
    (解答例)

    以下のようにする.

    $ egrep '^.[^aeiou]' sgb-words.txt | wc -l
    
  6. 'q'の次が'u'以外の単語はあるか.
    (解答例)

    以下のようにする.

    $ egrep 'q[^u]' sgb-words.txt
    qophs
    

    'q'で終わる単語がないかどうかも確認しておく.

    $ egrep 'q$' sgb-words.txt
    
  7. 正規表現 '^[^e]*e[^e]*$' はどのような単語にマッチするか.
    (解答例)

    'e'以外の文字が0回以上繰り返された後,'e'があり, また'e'以外の文字が0回以上繰り返されている. すなわち,文字'e'を1つだけ含む単語にマッチする.

Date: 2017-09-30 16:09:16 JST

Author: 田村直之

Validate XHTML 1.0