「言語処理100本ノック」 第4章をPythonで解く

言語処理100本ノックの4章を解きました。
4章は、MeCabを用いた形態素解析に関する問題です。
解答例としてどうぞ。質問，ご指摘などがありましたら、コメントしてください。

言語処理100本ノック第4章

前準備

夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をMeCabを使って形態素解析し，その結果をneko.txt.mecabというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

import MeCab

mecab = MeCab.Tagger("-Ochasen")

with open('neko.txt', 'r') as neko, open('neko.txt.mecab', 'a') as neko_mecab:
    neko = neko.read()
    neko = mecab.parse(neko)
    neko_mecab.write(neko)

30. 形態素解析結果の読み込み

形態素解析結果（neko.txt.mecab）を読み込むプログラムを実装せよ．ただし，各形態素は表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をキーとするマッピング型に格納し，1文を形態素（マッピング型）のリストとして表現せよ．第4章の残りの問題では，ここで作ったプログラムを活用せよ．

mecab_list = []

with open('neko.txt.mecab', 'r') as neko_mecab:
    lines = neko_mecab.readlines()
    
    for line in lines:
        line = line.split("\t")
        
        if line[0] != 'EOS\n':
            mecab_dict = {}
            mecab_dict['surface'] = line[0]
            mecab_dict['base']    = line[2]

            if '-' in line[3]:
                hinshi = line[3].split('-')
                mecab_dict['pos']  = hinshi[0]
                mecab_dict['pos1'] = hinshi[1]
            else:
                mecab_dict['pos']  = line[3]
            
            mecab_list.append(mecab_dict)

31. 動詞

動詞の表層形をすべて抽出せよ．

verb_list = []

for word in mecab_list:
    if word['pos'] == '動詞':
        verb_list.append(word['surface'])

32. 動詞の原形

動詞の原形をすべて抽出せよ．

verb_prot_list = []

for word in mecab_list:
    if word['pos'] == '動詞':
        verb_prot_list.append(word['base'])

33. サ変名詞

サ変接続の名詞をすべて抽出せよ．

sahen_meishi_list = []

for word in mecab_list:
    if word['pos'] == '名詞' and word['pos1'] == 'サ変接続':
        sahen_meishi_list.append(word['base'])

34. 「AのB」

2つの名詞が「の」で連結されている名詞句を抽出せよ．

rentai_list = []
for i in range(len(mecab_list)):
    if mecab_list[i]['surface'] == 'の':
        if mecab_list[i-1]['pos'] == '名詞' and mecab_list[i+1]['pos'] == '名詞':
            word = mecab_list[i-1]['surface'] + mecab_list[i]['surface'] + mecab_list[i+1]['surface']
            rentai_list.append(word)

35. 名詞の連接

名詞の連接（連続して出現する名詞）を最長一致で抽出せよ．

rensetsu_meishi_list = []

meishi_count = 0
for i in range(len(mecab_list)):
    if mecab_list[i]['pos'] == '名詞':
        word += mecab_list[i]['surface']
        meishi_count += 1
    else:
        if word != '' and meishi_count > 1:
            rensetsu_meishi_list.append(word)
    
        word = ''
        meishi_count = 0

36. 単語の出現頻度

文章中に出現する単語とその出現頻度を求め，出現頻度の高い順に並べよ．

word_count = {}

for word in mecab_list:
    if word['surface'] in word_count:
        word_count[word['surface']] += 1
    else:
        word_count[word['surface']] = 1
     
word_count = sorted(word_count.items(), key=lambda x: x[1], reverse=True)

37. 頻度上位10語

出現頻度が高い10語とその出現頻度をグラフ（例えば棒グラフなど）で表示せよ．

import matplotlib.pyplot as plt
import japanize_matplotlib

label = []
number = []

for word in word_count:
    label.append(word[0])
    number.append(word[1])
    
    if len(label) == 10:
        break
        
plt.bar(range(10), number, tick_label=label)

38. ヒストグラム

単語の出現頻度のヒストグラム（横軸に出現頻度，縦軸に出現頻度をとる単語の種類数を棒グラフで表したもの）を描け．

import matplotlib.pyplot as plt
import japanize_matplotlib

number = []
for word in word_count:
    number.append(word[1])
    
plt.hist(number, bins=100)

39. Zipfの法則

単語の出現頻度順位を横軸，その出現頻度を縦軸として，両対数グラフをプロットせよ．

import matplotlib.pyplot as plt
import japanize_matplotlib

number = []
for word in word_count:
    number.append(word[1])
    
plt.hist(number, bins=100, log=True)

AtCoderで解いた問題が600問を超えた

600問解いて

AtCoderを始めてから1年半ほど経過したのですが、AC数が600問を超えていました。ここ数ヶ月はコンテストに参加しておらず、気が向いたときに過去問をコツコツ解いてました。

また、レートの方は、ちょうど一年前くらいに800(緑)に到達したのですが、現在は1050程度でいまだに緑で留まっているという状態です。これはおそらく自分の適正レートが1000前後であると思われます。ここから抜け出すには定期的に過去問を解き、D問題にもどんどんチャレンジしていく必要がありそうです。

しかし、自分の中で競技プログラミングはやりきったなという気持ちになっているため、しばらくお休みして、別の分野の勉強に時間を使っていこう思っています。また自分の中で競プロ熱が高まってきたら、今度は水色を目指したいです。

scikit-learnのcross_val_scoreで他クラス分類の交差検定の結果をF値で出したい時の注意点

Pythonの機械学習ライブラリscikit-learnのcross_val_scoreを利用して、他クラス分類タスクの交差検定の結果をF値で出力したいときに、つまづいた点があったため、メモとして残しておきます。

エラーの内容

from sklearn.model_selection import cross_val_score
from sklearn.model_selection import StratifiedKFold

stratifiedkfold = StratifiedKFold(n_splits=10)

scores = cross_val_score(model, data, labels, cv=stratifiedkfold, scoring='f1')

交差検定を行いたい時に、sklearnのcross_val_scoreを利用しています。

デフォルトの設定だと、accuracyが結果として出るのですが、結果をF値で出したい時、scoring='f1'と設定しても、データセットが他クラスだと以下のようなエラーが起こります。

 Target is multiclass but average='binary'. Please choose another average setting, one of [None, 'micro', 'macro', 'weighted'].

解決方法

他クラス分類の場合は、F値の平均をどのように算出するかを指定する必要があります。

こちらを参考に、F値の平均の算出方法も指定することで、解決します。

例としてF値のマクロ平均を結果として出力したい場合は、以下のようにscoring='f1_macro'とします。

from sklearn.model_selection import cross_val_score
from sklearn.model_selection import StratifiedKFold

stratifiedkfold = StratifiedKFold(n_splits=10)

scores = cross_val_score(model, data, labels, cv=stratifiedkfold, scoring='f1_macro')

print('Cross-Validation scores: {}'.format(scores))
# スコアの平均値
print('Average score: {}'.format(np.mean(scores)))

ソートアルゴリズムの理論と実装

コーディング面接対策として、初歩的なアルゴリズムの考え方とPythonでの実装例をメモ的にまとめます。

第1回目は、ソートアルゴリズムです。ソートアルゴリズムの種類は結構ありますが、今回は下記の2つについてです。(今後追加していく可能性あり）

• バブルソート
• マージソート

アルゴリズムの理論

バブルソート

• 配列のi番目の要素に入れる値を決めるため、i+1から配列の末尾までの要素を確認していき、i+1以降で最小の値を格納したインデックスと値を入れ替える (iの初期値は0)
• 同様の処理をi = (配列の長さ - 1)まで行う
• 配列の初期状態に依存せず、たとえソートされている配列にも同様の処理を行うため、平均計算量，最悪計算量共にO(N²)となります。

マージソート

• ソートされた二つの配列をソートされた状態で連結する処理はO(N)の計算量で可能
• 配列を再帰的に半分に分割していき、一つの値からなる配列を作る (値が一つなのでソート済みである）
• 分割した配列をソート済みの状態で連結していく
• 配列を分割する回数はlogN(底は2)回であり、配列をマージする処理の計算量の合計は各層ごとにO(N)となるため、全体での計算量はO(NlogN)となる。
• 配列の初期状態に依存せず、たとえソートされている配列にも同様の処理を行うため、平均計算量，最悪計算量共にO(NlogN)となります。

Pythonで実装

import time
import random

# バブルソート
def bubble_sort(A):
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if A[i] > A[j]:
                tmp = A[i]
                A[i] = A[j]
                A[j] = tmp

    return A


# マージソート
def marge_sort(A):
    
    if len(A) == 1:
        return A

    left = marge_sort(A[:len(A)//2])
    right = marge_sort(A[len(A)//2:])

    count_left = 0
    count_right = 0
    res = []
    for i in range(len(left) + len(right)):
        if count_left == len(left):
            res.append(right[count_right])
            count_right += 1
            
        elif count_right == len(right):
            res.append(left[count_left])
            count_left += 1

        elif left[count_left] > right[count_right]:
            res.append(right[count_right])
            count_right += 1

        else:
            res.append(left[count_left])
            count_left += 1

    return res


if __name__ == '__main__':
    a = [random.randint(1, 1000) for _ in range(1000)]
    s = time.time()
    b = bubble_sort(a)
    print(time.time() - s)

    a = [random.randint(1, 1000) for _ in range(1000)]
    s = time.time()
    b = marge_sort(a)
    print(time.time() - s)

実行結果は下記の通りになりました。

0.03351020812988281
0.0031762123107910156

PythonでWeb APIを利用する方法

Web APIは、多くのWebサービスで提供されています。

本記事では、PythonでどのようにAPIリクエストを送信するのかを解説します。

サンプルとして、iTunes APIを利用して、映画情報を取得するコードをPythonで書いてみます。

PythonでWeb APIを利用する方法

利用するライブラリ

PythonでのAPIリクエストはrequestsを利用して行います。下記のコマンドでインストール可能です。

pip install requests

基本的な使い方は以下の通りです。 urlには、APIのエンドポイントのURLを書き込みます。 paramsには、辞書型でクエリを入れます。

import requests

requests.get(url, params=params)

また、公式ドキュメントに書かれているように、リクエストの結果は、下記のようにステータスコード, json形式で確認することができます。

import requests

result = requests.get(url, params=params)

result.status_code  # ステータスコードを表示
result.json()       # jsonファイルが辞書型で返される

iTunes APIで試す

それでは、実際にiTunes APIで試してみましょう。 今回は、キーワードに「ハリー・ポッター」を指定して、ジャンルを「映画」とすることで、「ハリー・ポッター」シリーズの映画情報を取得してみます。

また、iTunes APIの詳細はこちらがわかりやすいです。

上記のページから、各クエリを確認します。必須クエリは、termとcountryです。termには今回調べたい「ハリー・ポッター」を指定して、日本語情報が欲しいので、countryにはjaを指定します。また、映画に関する情報が欲しいため、mediaにはmovieを指定します。

import requests

url = 'https://itunes.apple.com/search'
params = {'term': 'ハリー・ポッター', 'country': 'jp', 'media':'movie'}

results = requests.get(url, params=params).json()

条件に合った映画情報が辞書型で返されます。この状態だとごちゃごちゃしていて、よくわからないので、辞書キーの1つであるtrackNameで検索してみましょう。

for result in results['results']:
    print(result['trackName'])

すると、下記のように映画タイトルを取得することができます。

ハリー・ポッターと秘密の部屋 (字幕/吹替)
ハリー・ポッターとアズカバンの囚人 (字幕/吹替)
ハリー・ポッターと不死鳥の騎士団 (字幕/吹替)
ハリー・ポッターと賢者の石 (字幕/吹替)
ハリー・ポッターと炎のゴブレット (字幕/吹替)
ハリー・ポッターと死の秘宝 PART 1 (字幕/吹替)
ハリー・ポッターと死の秘宝 PART 2 (字幕/吹替)
ハリー・ポッターと謎のプリンス (字幕/吹替)

「言語処理100本ノック」 第3章をPythonで解く

言語処理100本ノックの3章を解きました。
3章は、正規表現を用いてwikipediaの文書を処理する問題です。
解答例としてどうぞ。質問，ご指摘などがありましたら、コメントしてください。

言語処理100本ノック第3章

20. JSONデータの読み込み

Wikipedia記事のJSONファイルを読み込み，「イギリス」に関する記事本文を表示せよ．問題21-29では，ここで抽出した記事本文に対して実行せよ．

import json

def chose_uk():
    with open('jawiki-country.json', 'r') as json_file:
        for line in json_file:
            line = json.loads(line)
            if line['title'] == 'イギリス':
                uk_file = line
                break
                
    return uk_file
    
    
if __name__ == '__main__':     
    print(chose_uk())

jsonファイルを読み込むために標準ライブラリのjsonを利用します。

21. カテゴリ名を含む行を抽出

記事中でカテゴリ名を宣言している行を抽出せよ．

import re
import json

uk_file = chose_uk()

lines = uk_file['text'].split('\n')

pattern = r"\[\[Category:.*\]\]"

for line in lines:
    if re.match(pattern, line):
        print(line)

[[Category〜]]となっている部分を正規表現で抜き出します。

22. カテゴリ名の抽出

記事のカテゴリ名を（行単位ではなく名前で）抽出せよ．

import re
import json

uk_file = chose_uk()

lines = uk_file['text'].split('\n')

pattern = r"\[\[Category:.*\]\]"

for line in lines:
    if re.match(pattern, line):
        line = re.sub(r"\[\[Category:", " ", line)
        line = re.sub(r"(\|.*)*(\|\*)*(\]\])", " ", line)
        print(line)

21で行った処理に加えて、[[ ]]などの余分な部分を正規表現で指定して削除します。

23. セクション構造

記事中に含まれるセクション名とそのレベル（例えば"== セクション名 =="なら1）を表示せよ．

import re
import json

uk_file = chose_uk()

lines = uk_file['text'].split('\n')

pattern = r"=.+="

for line in lines:
    if re.match(pattern, line):
        result = line.count('=') // 2 - 1
        line = re.sub(r"=", "", line)
        print(line, 'レベル: {}'.format(result))

=で囲まれている部分を見つけて、=の数を数えてレベルを決めます。

24. ファイル参照の抽出

記事から参照されているメディアファイルをすべて抜き出せ

import re
import json

uk_file = chose_uk()

lines = uk_file['text'].split('\n')

pattern = r".*(ファイル|File):"

for line in lines:
    if re.match(pattern, line):
        line = re.sub(r".*(ファイル|File):", "", line)
        line = re.sub(r"\|.*", "", line)
        print(line)

25. テンプレートの抽出

自然数Nをコマンドライン引数などの手段で受け取り，入力のうち末尾のN行だけを表示せよ．確認にはtailコマンドを用いよ．

import re
import json

def make_uk_dict():
    uk_file = chose_uk()

    lines = uk_file['text'].split('\n')

    pattern = r"\|.*\s=\s.*"

    uk_dict = {}
    for line in lines:
        if re.match(pattern, line):      
            key = re.sub(r"(=.*|\|)", "", line)
            value = re.sub(r".*=", "", line)

            uk_dict[key] = value
            
    return uk_dict


if __name__ == '__main__':     
    uk_dict = make_uk_dict()
    for key in uk_dict:
        print(key, uk_dict[key]) 

26. 強調マークアップの除去

25の処理時に，テンプレートの値からMediaWikiの強調マークアップ（弱い強調，強調，強い強調のすべて）を除去してテキストに変換せよ（参考: マークアップ早見表）

import re
import json

def delete_markup(uk_dict):
    pattern = r".*'+.*'+"
    
    for key in uk_dict:
        if re.match(pattern, uk_dict[key]): 
            uk_dict[key] = re.sub(r"'+", "", line)
            
    return uk_dict

if __name__ == '__main__':
    uk_dict = make_uk_dict()
    print(delete_markup(uk_dict))

27. 内部リンクの除去

26の処理に加えて，テンプレートの値からMediaWikiの内部リンクマークアップを除去し，テキストに変換せよ（参考: マークアップ早見表）

import re
import json

def delete_link(uk_dict):
    pattern = r".*\[\[.*\]\].*"

    for key in uk_dict:
        if re.match(pattern, uk_dict[key]): 
            if re.match(r"^(?!.*:).+$", uk_dict[key]):
                uk_dict[key] = re.sub(r".*\[\[.*\|", "", uk_dict[key])
                uk_dict[key] = re.sub(r"\[\[", "", uk_dict[key])
                uk_dict[key] = re.sub(r"\]\]\）|\]\]", "", uk_dict[key])
                
    return uk_dict
                
                
if __name__ == '__main__':
    uk_dict = make_uk_dict()
    uk_dict = delete_markup(uk_dict)
    uk_dict = delete_link(uk_dict)
    print(uk_dict)

28. MediaWikiマークアップの除去

各行を3コラム目の数値の逆順で整列せよ（注意: 各行の内容は変更せずに並び替えよ）．確認にはsortコマンドを用いよ（この問題はコマンドで実行した時の結果と合わなくてもよい）．

import re
import json

def delete_media_markup(uk_dict):
    pattern = r".*{{.*\|.*\|.*}}.*"

    for key in uk_dict:
        if re.match(pattern, uk_dict[key]): 
            if re.match(pattern, uk_dict[key]):
                uk_dict[key] = re.sub(r"{{.*\|.*\|", "", uk_dict[key])
                uk_dict[key] = re.sub(r"}}", "", uk_dict[key])
                
    return uk_dict
            

if __name__ == '__main__':
    uk_dict = make_uk_dict()
    uk_dict = delete_markup(uk_dict)
    uk_dict = delete_link(uk_dict)
    uk_dict = delete_media_markup(uk_dict)
    print(uk_dict)
            

29. 国旗画像のURLを取得する

テンプレートの内容を利用し，国旗画像のURLを取得せよ．（ヒント: MediaWiki APIのimageinfoを呼び出して，ファイル参照をURLに変換すればよい）

import re
import json
import requests

if __name__ == '__main__':
    uk_dict = make_uk_dict()
    uk_dict = delete_markup(uk_dict)
    uk_dict = delete_link(uk_dict)
    uk_dict = delete_media_markup(uk_dict)

    params = {'action':'query', 
              'titles':'File:' + uk_dict["国旗画像 "], 
              'format':'json', 
              'prop':'imageinfo', 'iiprop':'url', 
              'User-Agent':'knakajima'
             }
    url = 'https://www.mediawiki.org/w/api.php'
    result = requests.get(url, params).json()

    print(result['query']['pages']['-1'])

「サイバーエージェント 学生版ヒダッカソン -API編-」に参加してきました。

2019年9月19日-20日の二日間で行われたサイバーエージェントのAPI開発ハッカソンに参加してきました。初めてのハッカソン参加ということで、参加前はとても不安でしたが、結果的には参加してよかったと思えるような内容でした。

「ハッカソンの振り返り」、「これから参加する人に雰囲気を伝える」という意味も込めて、ハッカソンの参加記をここに記録しておきます。

 ハッカソン参加記

ハッカソン1日目

1日目の午前中は、競技の説明、同じグループの人との自己紹介を行いました。自分のグループは4人で、M1が3人でB3が1人という感じでした。今回のハッカソンは個人戦ですが、4-5人のグループに一人メンターさんがついて、気軽に質問ができる状況でした。

お昼ご飯は、サイバーエージェントさんが用意してくださったお弁当をグループで食べて、12:30から競技開始で、18:00までひたすら開発という感じでした。初日はDockerを使った環境構築や、cookieを用いたセッション管理につまづき、一つも実装を通せないという結果に終わりました。初日の競技終了後に、各自でslackに進捗を書くのですが、半分ほどの人が自分と同じような状況ということを知り、少し安心しました。

ハッカソン2日目

二日目は、午前中にサイバーエージェントのエンジニアの方から業務内容の紹介があり、競技は午後からスタート。初日の夜に家で実装を進めたこともあり、少しずつ、実装を進めることができて、いくつかの実装を通して、得点を獲得することができました。最終的な結果は、30人中20位くらいという結果ではありましたが、自分の中では健闘したと思います。

二日目で競技が終わった後は、表彰会と打ち上げがありました。打ち上げでは、別のチームの参加者や、メンターさんと話す機会になりました。

振り返り・感想

周りの参加者やメンターさんの技術レベルが高く、とても刺激を得ることができました。また、今の自分に不足している技術が明確に可視化されたと思います。具体的には、HTTP周りの知識、SQL、Dockerです。

今は研究室に所属していて、Web関連の知識を補強する機会は少ないですが、時間を見つけて力をつけて行きたいと思える二日間でした。