カテゴリー別アーカイブ: CodeIQ

CodeIQの問題と解説

[解説]「再帰関数で逆順並べ替え」

問題文

再帰関数で逆順並べ替え
基本関数だけで逆順アルゴリズムを実現してみよう!
今回の問題は基本的な関数のみを使って、リスト項目を逆順にするアルゴリズムを考えてみます。

問題
4つの関数car, cdr, cons, nullpのみを使って、リストの項目を逆順にする関数reverse_auxとreverse2をつくってください。

例えば、reverse2は['A','B','C','D']を、逆順の['D','C','B','A']に並べ替えます。

reverse2()は1変数、reverse_aux()は2変数のリストを取ります。
最終的には、reverse2が必要なのですが、その前段階としてreverse_auxを作ってください。


reverse_aux(x, y)の性質は以下の通りです。

reverse_auxは、リストx, yを取ります。
例えば、

reverse_aux( [‘A’, ‘B’, ‘C’, ‘D’], [‘E’, ‘F’, ‘G’] )

= [‘D’, ‘C’, ‘B’, ‘A’, ‘E’, ‘F’, ‘G’]

 のように、リストxを逆順にして、リストyはそのままで連結します。 まず、reverse_auxを作ってください。 
●基本関数 使って良い関数はcar, cdr, cons, nullpのみです。
・carは先頭の項目を返す関数です。
例えば、

car([‘A’, ‘B’, ‘C’]) = ‘A’

・cdrは先頭項目を除いたリストを返す関数です。   例えば、

cdr([‘A’, ‘B’, ‘C’]) = [‘B’, ‘C’]

 ・consは一つの項目とリストを引数する関数です。consは項目xをリストyの最初に付け足したリストを返す関数です。
例えば、

cons(‘X’, [‘A’, ‘B’, ‘C’]) = [‘X’, ‘A’, ‘B’, ‘C’]

 ・nullp()は1変数の関数で、true <- nullp([]) となり、それ以外の時(アトムあるいは有限要素数のリストの場合)はfalseを返します。
reverse_auxを定義する前に、予め自分の処理系でcar, cdr, cons, nullpを定義してください。 その時は、どんな組み込み関数を使っても構いませんが、reverse_auxだけは、上記の基本関数のみを使ってください。ただし、ifなどの条件文やreturnなどはOKです。
最後に、reverse_auxを使って、reverse2を作ってください。 名前がreverse2なのは、built-in関数との競合を防ぐためです。問題なければ、reverseでも結構です。 作成したコードは、ファイル名を reverse.txt として、アップロードしてください。

その他注意事項 今回の問題は、純LISP に関する問題です。 LISPで解くと簡単にできますが、他の言語処理系だと基本関数定義の所で手間取るかもしれません。 結構大変かと思いますが、頑張ってください。 言語はPythonを希望しますが、解答の論理構造がわかるものであれば、どの言語処理系でも解答可能です。

解説

今回は純LISPに関する問題です。純LISPとはatom, eq, car, cdr, consとう5つの基本関数でプログラミング言語です。実際には、cond, quote, lambda, defineという関数も必要となりますが、必要最小限のもので、プログラミング言語を作ることができるというのは非常に面白い考えだと思います。まるで、数学の有限の公理で色々な証明を行うのに似ています。

Pythonでの解答例


#!/usr/bin/python

#
# reverse.py
#

def car(x): return x[0]

def cdr(x): return x[1:]

def cons(x, y): return [x] + y

def nullp(x): return len(x) == 0

def reverse_aux(x, y):

print x, y # Show variables
if nullp(x):
return y
else:
return reverse_aux(cdr(x), cons(car(x), y))

def reverse2(x):

return reverse_aux(x, [])

####
print reverse_aux([‘A’,’B’,’C’,’D’], [‘E’,’F’,’G’])


reverse_aux(X, Y) の解説をします。

diagram

X=[‘A’,’B’,’C’,’D’], Y=[‘E’,’F’,’G’] とすると、cdr(X)=[‘B,’C’,’D’]を次のreverse_auxのX’に引き継ぎます。更に、car(X)=’A’とY=[‘E’,’F’,’G’] をcons()で結合したものを次のreverse_auxのY’に引き継ぎます。処理がreverse_auxで再帰的に行われ、X部分の要素が逆順になります。

うまく、再帰関数で定義できたでしょうか。再帰関数を使うと、whileやfor文などを使わずに、繰返し処理が表現できますね。

広告

[問題解説12] 男性と女性の殺人被害者数の関係は?

かなり遅くなってしまいましたが、「男性と女性の殺人被害者数の関係は?」の問題解説をします。

今回の問題は、前回の問題「ヒストグラムと散布図を描いてみよう」の発展問題です。

データとプログラムは下記のGitHubリポジトリーにおいてあります。

問題

世界各国の殺人被害者データを用いて女性被害者数から男性被害者数を予測してみましょう。

UNODC(United Nations Office on Drugs and Crime : 国連薬物犯罪事務所)から公開されている世界176ヶ国の殺人被害者の男女別のデータがあります。女性被害者数から男性被害者数を予測してみましょう。

homicide_log.zipをダウンロードしてください。解凍して、homicide_log.csvを読み込んでください。
男性・女性の殺人被害者数のデータは10を底とする対数化してあります。
元データは下記のページから入手しました。
Global Study on Homicide(殺人に関するグローバル調査)

■課題

1.回帰分析を行ってください。

Rの回帰分析関数 lm() を使用して予測式を求める計算をしてください。

2.予測式の値を答えてください。

男性被害者数をM、女性被害者数をFとすると、以下の予測式が成り立ちます。
M = a * F + b
a, b を小数点3桁まで答えてください。解答方法はプログラムの最終行に以下のように記述してください。
# a = x.xxx
# b = y.yyy
3.散布図を作成し、予測式の直線を表示してください。 X軸は女性被害者、Y軸は男性被害者。2Dの散布図を作成してください。表示範囲はX軸、Y軸ともに[-1,3]とする。 その散布図に重ねて、予測式の直線を青色で表示してください。

■解答方法 R言語のプログラムを作成し、上記1~3の課題に答えてください。プログラムファイル名は predict.txt として、アップロードしてください。 散布図は predict.pdf というファイル名でPDFとして出力するプログラムにしてください。

[問題解説12] 男性と女性の殺人被害者数の関係は? の続きを読む

06「アッカーマンの呪い」の使用言語ランキング

CodeIQの出題「アッカーマンの呪い」の挑戦者の使用言語ランキングを発表します。

f:id:infoarchitect:20130903104143p:image:w640

Ruby(18)がトップです。

意外なのが、Haskell(13)がJavaと共に3位でした。

再帰関数の問題はHaskellが得意なのでしょうか。

意外に伸び悩んだのがPython(6)とPerl(2)。

Google検索で答えを探したという挑戦者もいましたが、これはルール違反ですね。

09再帰の海に棲むドラゴンを描いてみよう【問題と解説】

CodeIQの再帰の海に棲むドラゴンを描いてみように挑戦ありがとうございます。

今回は再帰関数に潜む美しい数学的図形を堪能してもらいたいと思って、出題しました。

問題文

再帰の海に棲むドラゴンを描いてみよう

今回の問題は再帰関数を使ってC曲線とドラゴン曲線という再帰曲線を描く問題です。

準備問題 (解答を提出する必要はありません)

この問題はタートルグラフィックスという描画方法を使って作図をします。

タートルグラフィックスとは、描画の際に描画ポイントをダイレクトに示すのではなく、

ペンの場所 (x0, y0) から右に10ピクセル、90度回転、左に10ピクセル進む等のコマンドで描画する方法です。

描画のためのクラスTurtleを定義してください。

Turtleクラスには現在の描画座標 (x0, y0) をプロパティとして持っています。

Turtleクラスには下記のメソッド(関数)を定義してください。

1)new(width, height)

  描画するキャンバスのサイズを指定して、Turtleオブジェクトを生成する。

  ここでは、width=1200, height=800としてください。

2)set_initial_point(x, y)

  描画開始の座標を指定します。

3)plot_line(length, theta)

  角度 theta でlengthピクセル描画します。

  角度 theta の単位はラジアンです。つまり、90度はπ/2。

4)save(o_file)

  ファイル名 o_file にpngまたはjpeg形式でイメージを出力する。

f:id:infoarchitect:20131210135929p:image:w360:right

Turtleと同じ機能を示す関数やライブラリがある場合はTurtleを作成する必要はありません。

C曲線 (解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません)

再帰関数を利用して、C曲線を描いてみましょう。

Turtleに対して、メソッドccurve(length, theta) を再帰的に定義して曲線を描きましょう。

与えられた線の上側にπ/2ラジアン(45度)回転した線分を2つ描きます。これを何度も繰り返し行います。lengthの値が4px以下になった場合に描画するようにしてください。

描画の開始座標はset_initial_point(800, 300)。

ccurve(400, 0) で描画を開始します。

f:id:infoarchitect:20131210140636p:image:w360:right

ドラゴン曲線(解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません)

C曲線を描くことができたら、次はいよいよドラゴン曲線に挑戦してみます。

メソッドdragon(length, theta, flip)を再帰的に定義してドラゴン曲線を描いてみましょう。

C曲線の場合は、新しい線は元の線の同じ側に作っていましたが、ドラゴン曲線は新しい線を作る側が交互に変わっていきます。ドラゴン曲線のステップ2では、最初の線(左)は上側に、次の線(右)は下側に作られています。同じ手順が繰り替えされ、曲線が作られていきます。

lengthの値が5px以下になった時に描画を行います。

f:id:infoarchitect:20131210140634p:image:w360:right

ヒント

変数flipは+1, -1の値を取り、線を上側に描くか、下側に書くかの情報を表しています。ステップ1以降、flipの値は以下のように+1, -1が交替で現れます。

+1,-1,+1,-1,…,+1,-1,+1,-1

描画は下記の値で試してください。

set_initial_point(300, 300)

dragon(600, 0, +1)

ここでは数学の座標系を使って説明しましたが、計算機の座標系ではy軸が反転していますので、注意してください。

描画下限値lengthの値を変えてみて、綺麗に描画される値を探してみてください。

【解説】再帰の海に住むドラゴンを描いてみよう 

今回は再帰関数を用いてC曲線とドラゴン曲線を描く問題です。

準備問題は言語やOS等によって異なりますので、個々に対応してください。

タートルグラフィックスは直前の描画終了点を記憶し、描画の長さlengthと描画の方向角度thetaを入力変数として描画を行うシステムです。

C曲線

アルゴリズムが正しければ、以下のような綺麗な図形が現れます。

まるで、宮殿のようですね。

ここでは開口部が上を向いていますが、右に立てて描画することも可能です。形がCの形に似ているので、C曲線と名付けられました。

f:id:infoarchitect:20131210141257p:image:w640

PythonによるC曲線とドラゴン曲線のプログラム例

#!/usr/bin/python
#
#                                dragon.py
#
from PIL import Image, ImageDraw
from math import cos, sin, pi, sqrt
class Turtle:
def __init__(self, width=1200, height=800):
mode = "RGB"        # Black and White
bg = "#ffffff"
self.window = Image.new(mode, (width,height), bg)
self.dr = ImageDraw.Draw(self.window)
def set_initial_point(self, x, y):
self.x0, self.y0 = x, y
def plot_line(self, length, theta):
x1 = self.x0 + length*cos(theta)
y1 = self.y0 + length*sin(theta) ###        #self.dr.line*1
### here is a bug for Hatena Diary display        self.dr.line*2
self.x0, self.y0 = x1, y1
def save(self, o_file, form="PNG"):
self.window.show()
self.window.save(o_file, form)
def ccurve(self, length, theta):
if length <= 4:
self.plot_line(length, theta)
else:
self.ccurve(length/sqrt(2), theta + pi/4)
self.ccurve(length/sqrt(2), theta - pi/4)
def dragon(self, length, theta, flip):
if length <= 5:
self.plot_line(length, theta)
else:
self.dragon(length/sqrt(2), theta + flip*pi/4, 1)
self.dragon(length/sqrt(2), theta - flip*pi/4, -1)
if __name__ == '__main__':
d = Turtle(1200, 800)
d.set_initial_point(400, 300)    # C-CURVE
d.ccurve(400, 0)
d.save("ccurve.png")
d = Turtle(1200, 800)
d.set_initial_point(300, 300)    # DRAGON CURVE
d.dragon(600, 0, +1)
d.save("dragon.png")

C曲線の解説

C曲線を描くには元の親関数から次々に子供関数を再帰的に定義していく必要があります。

例えば、最初のステップ0では長さlength=1, 角度theta=0 (0度)とすると、次のステップ1では2つの子供関数に引き継がれます。

最初の子供関数では次のようになります。

length = length ÷ √2 = 1/√2

theta = theta + π/4 = π/4 = 45度

もうひとつの子供関数では次のようになります。

length = length ÷ √2 = 1/√2

theta = theta – π/4 = -π/4 = -45度

この操作が繰り返され、長さlengthはどんどん短くなっていきます。

length = 1, 1/√2, 1/(√2)^2, 1/(√2)^3,1/(√2)^4,…

繰り返していくと、最後に綺麗なC曲線ができます。

停止条件がないと無限に計算して止まらなくなるので、lengthがある値以下になったら終了するように設定しておきます。

ドラゴン曲線

アルゴリズムが正しければ、以下のような得体の知れない生き物のような図になります。

解答者の中にはグラデーションをつけて、より神秘的なドラゴンを描いてくれた人もいました。

f:id:infoarchitect:20131210141442p:image:w640

ドラゴン(竜)に見えますか。ドラゴンと言うよりリーフィーシードラゴンですね。

f:id:infoarchitect:20131210141920j:image:w360

(ウィキペディアより転載)

ドラゴン曲線の解説

ドラゴン曲線の手順は少し面倒です。C曲線と似ていますが、規則的に線の上側(正の角度)と下側(負の角度)に入れ替わるように描画していきます。

親関数は2つの子供関数に引き継がれます。ここで、最初の子供関数を長男関数、二番目の子供関数を次男関数と名づけます。

flipの値を次のように決めます。

上側ならば、flip = +1

下側ならば、flip = -1

長男関数も次男関数も親関数から上側に描くか下側に描くかの情報を引き継ぎますが、必ず長男関数は上側を、次男関数は下側としてflip値を引き継ぎます。

親関数は自分が受け取ったflip値に基づいて、長男及び次男関数を上側ならば、/\の形に、下側ならば\/の形で描画するように指示します。

つまり、

上側(flip = +1) →子供関数それぞれのthetaの増減値を+π/4, -π/4

下側(flip = -1)→子供関数それぞれのthetaの増減値を-π/4, +π/4

各パラメーターをいじってみて、綺麗に描画できる値を探してみてください。

*1:self.x0, self.y0, x1, y1), (0,0,255

*2:self.x0, self.y0, x1, y1), (0,0,255

設問1:トークンの出現頻度を集計してみよう!

CodeIQで作成した設問1

Pythonの自然言語処理パッケージNLTKをインストールすること。以下のURLを参照して下さい。

http://www.nltk.org/

NLTKにはフリーの電子書籍を有する「グーテンベルク電子出版アーカイブ」プロジェクト

のデータが含まれています。nltkによるgutenbergのデータのダウンロードが必要です。

http://www.gutenberg.org/

gutenbergに収録されているジェーン・オースティンの「分別と多感」のテキストausten-sense.txtを読み込んで、テキスト内のトークン(単語)の出現頻度の一覧を作成してください。

トークンには、カンマ「,」、ピリオド「.」などの記号が含まれているため、アルファベット文字でのみ構成されるトークンだけを出力対象とします。アルファベットは全て小文字に置き換えて、NLTKのFreqDist関数を使って、トークンの頻度を集計してください。

出力ファイルはカンマ区切りのCSV形式で以下の通り。

頻度順(降順)で出力すること。

1カラム目 トークン

2カラム目 頻度

3カラム目 全体に占めるパーセンテージ(出力形式は%f)

to,4116,3.40918

the,4105,3.40006

of,3572,2.95859

(以下省略)

参考文献

・Steven Bird 「入門 自然言語処理」オライリー・ジャパン

 http://www.amazon.co.jp/gp/product/4873114705

・上記の書籍の英語版はオンラインで読めます。

 Natural Language Processing with Python — Analyzing Text with the Natural Language Toolkit

 Steven Bird, Ewan Klein, and Edward Loper

 O’Reilly Media, 2009.

 http://nltk.org/book/

 Kindle版

 http://www.amazon.co.jp/gp/product/B0043D2E22

解答例1

[プログラム]

問題のプログラムのポイントは以下の3点です。

1. NLTKのインストールとデータのダウンロード

2. トークンの条件による絞り込み

3. DistFreqオブジェクトの使い方

NLTKからausten-sense.txtをダウンロードできたでしょうか。

トークンのリストを取得できたら、以下の様にアルファベットのみを含むトークンに

絞り、小文字化します。

text = [w.lower() for w in text0 if w.isalpha()]

Pythonでは、集合の数学記号 {x|x in A}

等のように1行でデータの抜き出しと変換を行う事できます。私も何年もPythonをやってきましたが、こんなにエレガントに書けるなんて長い間知りませんでした。

この書記法に慣れていきましょう。

トークンリストからFreqDistオブジェクトを生成し、ループを回して頻度を出力すれば終わりです。

問題では頻度順ソートについては書きませんでしたが、FreqDistオブジェクトの keys() メソッドは頻度の降順でキーのリストを出してくれるので、わざわざソートする必要はあ

りません。便利ですね。

プログラムの解答例は以下の通りです。

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
#                           gutenberg.py
#
import nltk
i_file, o_file = 'austen-sense.txt', 'austen-sense.out'
### データのダウンロード ###
text0 = nltk.corpus.gutenberg.words(i_file)
### アルファベットのみを含むトークンを小文字化する ###
text = [w.lower() for w in text0 if w.isalpha()]
### FreqDistオブジェクト ###
fdist1 = nltk.FreqDist(text)
o_handle = open(o_file, 'w')
words = len(text)
for k in fdist1.keys():
w = '%s,%d,%f\n' % (k, fdist1[k], 100.0*float(fdist1[k])/words)
o_handle.write(w)

[出力結果で気づいた点]

出力結果は以下の通りです。

to,4116,3.40918
the,4105,3.40006
of,3572,2.95859
and,3491,2.89150
her,2551,2.11293
a,2092,1.73275
i,2004,1.65986
in,1979,1.63915
was,1861,1.54142
it,1757,1.45528
she,1613,1.33601
that,1385,1.14716
be,1305,1.08090
for,1262,1.04528
not,1248,1.03369
as,1221,1.01132
you,1191,0.98647
he,1108,0.91773
his,1021,0.84567
had,998,0.82662
with,992,0.82165
but,886,0.73385
at,839,0.69492
have,819,0.67836
is,760,0.62949
by,750,0.62121
s,701,0.58062
on,696,0.57648
elinor,685,0.56737
all,656,0.54335
so,644,0.53341
him,642,0.53175
my,628,0.52016
which,593,0.49117
could,578,0.47874
no,568,0.47046
marianne,566,0.46880
from,541,0.44810
mrs,530,0.43899
they,521,0.43153

目で見てみると、ほとんど英語ではto, the, and等の高頻度のトークンは意味を担う語ではなく、文法的な語が多い事に気づきます。。ElinorとMarianneはこの小説にでてくる登場人物の名前です。呼びかけや説明文で、人名がでてくるは当然かもしれません。

人名以外に、この小説の特徴を表すトークンを見つけるのにはもう少し解析が必要なようですね。

トップ50の累積頻度をfdist1.plot(50, cumulative=True)で表示してみると、以下の様に

なります。

f:id:infoarchitect:20130201114813p:image:w360

テキストの全語数が120733なので60000/120733=50.0%となり、たった50の語が半数を占めている事になります。

10「ローマ数字変換器を作ってみよう」の問題と解説

今回はローマ数字を(通常の)アラビア数字に変換するプログラムです。

99名もの方が挑戦してくれました。本当にありがとうございます。

問題文

ローマ数字変換器を作ってみよう!

ローマ数字をアラビア(通常の)数字に変換するプログラムをPythonで作ってみましょう。

■ローマ数字について

ローマ数字はラテン文字の一部を使って、I, II, III, IV, X, XVなどのように数を表す方法です。I, V, X, L, C, D, Mがそれぞれ1, 5, 10, 50, 100, 500, 1000を表します。

通常は大きい数字から左から順に加算していきます。しかし例外的な減算則があり、4や9などはそれより小さい数の文字を左においてIVやIXと書きます。つまり、

IV = – I + V 4 = – 1 + 5

IX = – I + X 9 = – 1 + 10

のように表します。XIVは14となります。

XIV = X + (= I + V) 14 = 10 + (- 1 + 5)

詳しくは下記を参考。

http://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%83%9E%E6%95%B0%E5%AD%97

■プログラムについて

あまり複雑になりすぎない簡単なPythonプログラムにしてください。

使われるローマ文字はI, V, X, L, C, D, Mでこれらの組み合わせとなります。

4, 9, 40, 90 ,400, 900等の減算則に注意してローマ数字からアラビア(通常の)数字へのプログラムを作成してください。

実行関数はmain()として、main(‘XIV’)の結果は以下のようにprintで表示されるようにしてください。

XIV = 14

下記の結果を出力するプログラムを送ってください。

main(‘XLIX’)

main(‘MDCCCLXXXVIII’)

main(‘MCMXLV’)

main(‘MMMCMXCIX’)

構文解析ツールついては適切なフィードバックはできませんので、それを使わずに解答してください。私の回答不要の場合は使ってもOKです(評点は付けます)。

■解答方法

作成したPythonプログラムをテキストファイル(roman.txt)に変換しアップロードしてください。

ローマ数字は簡単な規則でできていると思っていましたが、実際に解答者のやり方を見ると、いろいろなやり方(まとめ方)があるので、びっくりしました。

半分ぐらいがアルファベット文字列を他の文字列に置き換えてしまうという方法でした。まず例外(減算)処理のIV(4)やIX(9)をIIIIやVIIII等に変換し、その後、通常の(加算)処理として他の文字をI(1)やX(10)に置き換えるやり方です。

IV → IIII

IX → VIIII 等

私が考えたのは、文字を逐一変換していく方法です。この方法で重要なのは文字の評価を左からするのではなく、右から評価していくという事です。

通常の評価では隣り合った文字は、後の文字 ≧ 前の文字 となります。例えば、VIではV(5) > I(1) となるのでVの評価値は+5となります。

…XVII… ← 評価方向

一方、例外となる減算処理では、後の文字 < 前の文字 となります。例えば、CXでは X(10) < C(100) となるので、Xの評価値は-10はとなります。

…MXCXX… ← 評価の方向

このやり方では、IIX(8)やXXC(80)等のイレギュラーな文字列は扱えませんが、同じ文字(例えばIII)をひとまとまりとしてグルーピングすれば、そのようなイレギュラーな文字列も扱えます。

解答例

#!/usr/bin/python
#
#                               roman2.py
#
class Parser:
def __init__(self):
self.value = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1, '$':0}
def compute(self, w):
num = 0
prev = '$'
for x in w[::-1]:
if self.value[x] >= self.value[prev]:
factor = +1     # ADDITION
else:
factor = -1     # SUBTRACTION
#print x, '%+d' % (factor * self.value[x])
num += factor * self.value[x]
prev = x            # STORE THE PREVIOUS CHARACTER
return num
def main(s):
p = Parser()
print s, '=', p.compute(s)
#####
main('XLIX')
main('MDCCCLXXXVIII')
main('MCMXLV')
main('MMMCMXCIX')

どうでしょうか。皆さんはどんなローマ数字変換器ができたでしょうか。

CodeIQで問題作成してますので、他の問題も挑戦してみてください。

https://codeiq.jp/ace/kawagashira_nobuyuki/

設問2:英語の男女人名の違いを調べてみよう!

CodeIQに出題した設問2の解説。

Pythonの自然言語処理パッケージNLTKをインストールすること。以下のURLを参照して下さい。

http://www.nltk.org/

NLTKにはフリーの英語人名データが収録されています。

下記のようにパッケージを読み込んでプログラミングしてください。

from nltk.corpus import names

下記のコマンドで男女の人名ファイル名を取得できます。

names.fileids()

namesに収録されている男女の人名ファイルを読み込んで、語末のアルファベット1文字による人名の頻度表を作成してください。例えば、’John’であれば、’n’が1回と数えます。

NLTKのConditionalFreqDist関数を使って、頻度の集計をしてください。

ConditionalFreqDist内のペアは(‘a’, ‘female.txt’)のような順序でプログラムを作成すること。

出力ファイルは、ヘッダーを付けて、カンマ区切りのCSV形式で以下の通り。

アルファベット順で出力すること。

1カラム目 語末の1文字

2カラム目 女性人名の頻度

3カラム目 男性人名の頻度

WordEnding,female.txt,male.txt

,1,0

a,1773,29

c,0,25

b,9,21

(以下省略)

[注意]namesの収録データ不備により、女性名’Gale ‘が含まれており、語末をとると空白’ ‘になってしまいます。今回は出力ファイルからこの欄を除く必要はありません。

nltkでデータをダウンロード出来ない時は、下記のサイト内の32. Names Corpusからダウンロードしてください。

http://nltk.googlecode.com/svn/trunk/nltk_data/index.xml

提出物

解答は、テキストファイルをアップロードしていただきます。1枚のテキストファイルにして、提出してください。

提出する内容は以下の通り。

1. 出現頻度を出力するPythonの処理プログラム。

2. 男女の人名の語末文字の上位3位は何であるか。上位3位の語末文字から何が言えるか、気づいた点を書いてください。

参考文献

・Steven Bird 「入門 自然言語処理」オライリー・ジャパン

 http://www.amazon.co.jp/gp/product/4873114705

・上記の書籍の英語版はオンラインで読めます。

 Natural Language Processing with Python — Analyzing Text with the Natural Language Toolkit

 Steven Bird, Ewan Klein, and Edward Loper

 O’Reilly Media, 2009.

 http://nltk.org/book/

解答のポイントは次の三つです。

1. NLTKで複数のファイルを扱う。

2. ConditionalFreqDist関数を使って、条件付き頻度分布オブジェクトを生成する。

3. 頻度出力の為のループの書き方。

プログラムの例は以下の通り。

#!/usr/bin/python
#
#                               names.py
#
import nltk
from nltk.corpus import names
def main(o_file):
cdf = nltk.ConditionalFreqDist(
(word.lower()[-1:], fileid)
for fileid in names.fileids()
for word in names.words(fileid))
### OUTPUT ###
o_handle = open(o_file, 'w')
s = 'WordEnding,'
s += ','.join(names.fileids())
o_handle.write('%s\n' % s)
for target in cdf.keys():
s = target
for fileid in names.fileids():
s += ',%d' % cdf[target][fileid]
o_handle.write('%s\n' % s)
###
main('names.out')

出力は以下の通り。

WordEnding,female.txt,male.txt
,1,0
a,1773,29
c,0,25
b,9,21
e,1432,468
d,39,228
g,10,32
f,2,25
i,317,50
h,105,93
k,3,69
j,1,3
m,13,70
l,179,187
o,33,165
n,386,478
p,2,18
s,93,230
r,47,190
u,6,12
t,68,164
w,5,17
v,2,16
y,461,332
x,10,10
z,4,11

気づいた点。

頻度の上位三位を調べると、女性名はa,e,yで語尾で多く、男性名はn,e,yが多い。語尾がaならば、女性名、語尾がnならば男性名と言えそうです。

更なる分析が必要となりますね。