morikomorou’s blog

自分が学んだことなどの備忘録的なやつ

【python】言語処理100本ノック2020を解く(第5章後半)


はじめに

前回までの続きで言語処理100本ノック解いていきたいと思います。

今回は第5章後半です。前回に引き続き係り受け解析の章やっていきます。




第5章: 係り受け解析

40~46は前回記事で紹介したので、47からです。
続きなので、これまでの変数とかは過去記事参考願います。

47. 機能動詞構文のマイニング

動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい.46のプログラムを以下の仕様を満たすように改変せよ.

  • 「サ変接続名詞+を(助詞)」で構成される文節が動詞に係る場合のみを対象とする
  • 述語は「サ変接続名詞+を+動詞の基本形」とし,文節中に複数の動詞があるときは,最左の動詞を用いる
  • 述語に係る助詞(文節)が複数あるときは,すべての助詞をスペース区切りで辞書順に並べる
  • 述語に係る文節が複数ある場合は,すべての項をスペース区切りで並べる(助詞の並び順と揃えよ)

例えば「また、自らの経験を元に学習を行う強化学習という手法もある。」という文から,以下の出力が得られるはずである.

学習を行う に を 元に 経験を

こちらも形態素を探索して、細かく条件分けし、条件に合ったもののみ抽出します。
大体は46番と考え方は同じです。

def get_info_mining(sentence):
    particles = []
    for chunk in sentence:
        predicate = ''
        for morph in chunk.morphs:
            if morph.pos == '動詞':
                if len(chunk.srcs):
                    modifier = []
                    mod_dic = {}
                    particle = ''
                    flg2 = 0
                    for src in chunk.srcs:
                        flg = 0
                        for x in sentence[src].morphs:
                            if x.pos == '名詞' and x.pos1 == 'サ変接続' and not flg2:
                                predicate += x.surface
                                flg = 1
                                continue
                            elif x.pos == '助詞' and x.surface == 'を' and flg == 1 and not flg2:
                                predicate += 'を'
                                flg = 0
                                flg2 = 1
                                continue
                            elif x.pos != '記号':
                                flg = 0
                                particle += x.surface
                            if x.pos == '助詞':
                                flg = 0
                                modifier.append(x.surface)
                                mod_dic[x.surface] = particle
                                particle = ''
                            else:
                                flg = 0
                        particle = ''
                    if len(modifier) and flg2:
                        modifier = sorted(list(set(modifier)))
                        particles.append(predicate + morph.base + '\t' + ' '.join(modifier) + '\t' + ' '.join([mod_dic[x] for x in modifier]))
                break
    return particles

for sentence in sentences:
    particles = get_info_mining(sentence)
    for particle in particles:
        print(particle)

以下出力です。(全文の中にこれだけしかないのは少し気がかりです。)

行動を代わる	に	人間に
記述をする	と	主体と
注目を集める	が	サポートベクターマシンが
経験を行う	に を	元に 学習を
-推論統計学習をする	て で に は を を通して	なされて ACTRで 元に は ルールを 生成規則を通して
活躍敵対生成生成進化を見せる	て において は	加えて 技術において 的ネットワークは
製作開発を行う	は	エイダ・ラブレスは
処理を行う	に により	Webに ティム・バーナーズリーにより
意味をする	に	データに
付加処理を行う	て に	して コンピュータに
研究を進める	て	費やして
命令をする	で	機構で
運転をする	に	元に
特許をする	が に まで	日本が に 2018年まで
運転をする	て に	基づいて 柔軟に
注目を集める	から は	ことから ファジィは
制御を用いる	て も	受けて 他社も
制御をする	から	少なさから
処理改善を果たす	が で に	チームが 画像コンテストで 2012年に
研究を続ける	が て	ジェフホーキンスが 向けて
開発接地()をする	に は	8月に は
注目を集める	に	急速に
主導投資を行う	で に	民間企業で 全世界的に
実装探索を行う	で	無報酬で
推論をする	て	経て
共同研究を始める	とも は	マックスプランク研究所とも Googleは
研究を行う	て	始めて
研究開発をする	で は	官民一体で は
研究開発をする	で	日本で
投資をする	に は まで	に 韓国は 2022年まで
反乱を起こす	て に対して	於いて 人間に対して
歩行監視を行う	に まで	人工知能に 者まで
手続きを経る	を	ウイグル族を
プログラム制御をする	は	AIは
判断を介す	から	観点から
禁止を求める	が に は	ヒューマン・ライツ・ウォッチが 4月に は
開発競争を行う	は をめぐって	米国中国ロシアは 軍事利用をめぐって
暴露拒否整合追及を受ける	て で と とともに は	されて 性で すると とともに は
共同研究をする	が	Microsoftが
発表解任をする	て は	含まれて Google社員らは
要請解散をする	が で は	倫理委員会が 理由で Googleは
存在を見いだす	に	ものに
話をする	は	哲学者は
議論を行う	まで	これまで

48. 名詞から根へのパスの抽出

文中のすべての名詞を含む文節に対し,その文節から構文木の根に至るパスを抽出せよ. ただし,構文木上のパスは以下の仕様を満たすものとする.

  • 各文節は(表層形の)形態素列で表現する
  • パスの開始文節から終了文節に至るまで,各文節の表現を” -> “で連結する

ジョン・マッカーシーはAIに関する最初の会議で人工知能という用語を作り出した。」という例文を考える. CaboChaを係り受け解析に用いた場合,次のような出力が得られると思われる.

ジョンマッカーシーは -> 作り出した
AIに関する -> 最初の -> 会議で -> 作り出した
最初の -> 会議で -> 作り出した
会議で -> 作り出した
人工知能という -> 用語を -> 作り出した
用語を -> 作り出した

KNPを係り受け解析に用いた場合,次のような出力が得られると思われる.

ジョンマッカーシーは -> 作り出した
AIに -> 関する -> 会議で -> 作り出した
会議で -> 作り出した
人工知能と -> いう -> 用語を -> 作り出した
用語を -> 作り出した

まず、パスの始点となる文節を順番に探索します。文節の中に名詞が含まれていればそこをパスの始点とします。
あとは、chunk.dstを順番にたどっていき、chunk.dst=-1になるまで文節をパスに追加していくだけです。

def get_path(sentence):
    for chunk in sentence:
        modifier_pos = [x.pos for x in chunk.morphs]
        if '名詞' in modifier_pos and chunk.dst != -1:
            path = [''.join([x.surface if x.pos != '記号' else '' for x in chunk.morphs])]
            nxt = chunk.dst
            while nxt != -1:
                path.append(''.join([x.surface if x.pos != '記号' else '' for x in sentence[nxt].morphs]))
                nxt = sentence[nxt].dst
            print(' -> '.join(path))

get_path(sentences[1])

出力は以下。

人工知能 -> 語 -> 研究分野とも -> される
じんこうちのう -> 語 -> 研究分野とも -> される
AI -> エーアイとは -> 語 -> 研究分野とも -> される
エーアイとは -> 語 -> 研究分野とも -> される
計算 -> という -> 道具を -> 用いて -> 研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
概念と -> 道具を -> 用いて -> 研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
コンピュータ -> という -> 道具を -> 用いて -> 研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
道具を -> 用いて -> 研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
知能を -> 研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
研究する -> 計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
計算機科学 -> の -> 一分野を -> 指す -> 語 -> 研究分野とも -> される
一分野を -> 指す -> 語 -> 研究分野とも -> される
語 -> 研究分野とも -> される
言語の -> 推論 -> 問題解決などの -> 知的行動を -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
理解や -> 推論 -> 問題解決などの -> 知的行動を -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
推論 -> 問題解決などの -> 知的行動を -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
問題解決などの -> 知的行動を -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
知的行動を -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
人間に -> 代わって -> 行わせる -> 技術または -> 研究分野とも -> される
コンピューターに -> 行わせる -> 技術または -> 研究分野とも -> される
技術または -> 研究分野とも -> される
計算機 -> コンピュータによる -> 情報処理システムの -> 実現に関する -> 研究分野とも -> される
コンピュータによる -> 情報処理システムの -> 実現に関する -> 研究分野とも -> される
知的な -> 情報処理システムの -> 実現に関する -> 研究分野とも -> される
情報処理システムの -> 実現に関する -> 研究分野とも -> される
設計や -> 実現に関する -> 研究分野とも -> される
実現に関する -> 研究分野とも -> される
研究分野とも -> される




49. 名詞間の係り受けパスの抽出

文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ.ただし,名詞句ペアの文節番号がiとj(i

  • 問題48と同様に,パスは開始文節から終了文節に至るまでの各文節の表現(表層形の形態素列)を” -> “で連結して表現する
  • 文節iとjに含まれる名詞句はそれぞれ,XとYに置換する


また,係り受けパスの形状は,以下の2通りが考えられる.

  • 文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
  • 上記以外で,文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス,文節kの内容を” | “で連結して表示


ジョン・マッカーシーはAIに関する最初の会議で人工知能という用語を作り出した。」という例文を考える. CaboChaを係り受け解析に用いた場合,次のような出力が得られると思われる.

Xは | Yに関する -> 最初の -> 会議で | 作り出した
Xは | Yの -> 会議で | 作り出した
Xは | Yで | 作り出した
Xは | Yという -> 用語を | 作り出した
Xは | Yを | 作り出した
Xに関する -> Yの
Xに関する -> 最初の -> Yで
Xに関する -> 最初の -> 会議で | Yという -> 用語を | 作り出した
Xに関する -> 最初の -> 会議で | Yを | 作り出した
Xの -> Yで
Xの -> 会議で | Yという -> 用語を | 作り出した
Xの -> 会議で | Yを | 作り出した
Xで | Yという -> 用語を | 作り出した
Xで | Yを | 作り出した
Xという -> Yを

KNPを係り受け解析に用いた場合,次のような出力が得られると思われる.

Xは | Yに -> 関する -> 会議で | 作り出した。
Xは | Yで | 作り出した。
Xは | Yと -> いう -> 用語を | 作り出した。
Xは | Yを | 作り出した。
Xに -> 関する -> Yで
Xに -> 関する -> 会議で | Yと -> いう -> 用語を | 作り出した。
Xに -> 関する -> 会議で | Yを | 作り出した。
Xで | Yと -> いう -> 用語を | 作り出した。
Xで | Yを | 作り出した。
Xと -> いう -> Yを

問題文が長くて訳が分からなくなりそうですが、順番に見ていきましょう。
まずは、すべての名詞句のペアを探す必要があるので、1文中の文節の中で名詞を含む文節番号を抜き出します。

sentence = sentences[2]
nouns = []
# 名詞を含むchunkを抽出
for i, chunk in enumerate(sentence):
    print(i, ''.join([morph.surface for morph in chunk.morphs]))
    if '名詞' in [morph.pos for morph in chunk.morphs]:
        nouns.append(i)
print('---------------------------')
print('名詞を含む文節番号: ', nouns)

結果は以下です。

0 『日本大百科全書(ニッポニカ)』の
1 解説で、
2 情報工学者・通信工学者の
3 佐藤理史は
4 次のように
5 述べている。
---------------------------
名詞を含む文節番号:  [0, 1, 2, 3, 4]

次にこれらの全組み合わせを調べる必要があるので全組み合わせを求めます。

from itertools import combinations

print([x for x in combinations(nouns, 2)])
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

ちゃんと求まってそうです。タプルの左がわが右側より小さい数字になっていることも確認しておきます。

あとは、係り受けパスを求めます。
先ほど求めたペアの文節番号が小さい側(左側)をX、大きい側をYとすると、パスは以下の2種類に分かれます。

  1. Xから根までのパスの中にYが含まれる。
  2. Xから根までのパスの中にYが含まれない。

上記の1のパターンの場合は簡単で、以下のように出力するだけです。
Xから根までのパス中のYまでを->つなぎで出力。(X -> ... -> ... -> Y)

2のパターンの場合は少々複雑になります。
まず、X,Yそれぞれから根までのパスを求めます。
次に、Xから根までのパスを最初から探索していった際に、Yから根までのパスに含まれているものが最初に現れたものをKとします。
最後にそれぞれのパスにおいてKの1個前の文節番号をX(K-1), Y(K-1)とした場合に、下記のように出力します。
X-> ... -> X(K-1) | Y -> ... -> Y(K-1) | K -> ... -> 根

以上を踏まえて、以下のように実装できます。

from itertools import combinations

def get_path_to_root(now, sentence):
    # 文節番号nowから根までのパスを求める
    # 出力は文節番号のリスト
    chunk = sentence[now]
    path = []
    if chunk.dst != -1:
        path.append(now)
        nxt = chunk.dst
        while nxt != -1:
            path.append(nxt)
            nxt = sentence[nxt].dst
    return path


sentence = sentences[2]
nouns = []
# 名詞を含むchunkを抽出
for i, chunk in enumerate(sentence):
    if '名詞' in [morph.pos for morph in chunk.morphs]:
        nouns.append(i)

# 名詞を含むchunkの全ペアを作成
for i, j in combinations(nouns, 2):
    pathx = get_path_to_root(i, sentence) # Xから根までのパス
    pathy = get_path_to_root(j, sentence) # Yから根までのパス
    path1 = []
    path2 = []
    path3 = []
    flg = 0
    if j in pathx:
        # パターン1
        for k in pathx:
            if k == i:
                morphs = 'X' + ''.join([x.surface if x.pos == '助詞' else '' for x in sentence[k].morphs])
                path1.append(''.join(morphs))
            elif k != j:
                morphs = ''.join([x.surface if x.pos != '記号' else '' for x in sentence[k].morphs])
                path1.append(''.join(morphs))
            else:
                morphs = 'Y' + ''.join([x.surface if x.pos == '助詞' else '' for x in sentence[k].morphs])
                path1.append(''.join(morphs))
                break
        print(' -> '.join(path1))
    else:
        # パターン2
        for k in pathx:
            if k == i:
                morphs = 'X' + ''.join([x.surface if x.pos == '助詞' else '' for x in sentence[k].morphs])
                path1.append(''.join(morphs))
            elif k not in pathy:
                morphs = ''.join([x.surface if x.pos != '記号' else '' for x in sentence[k].morphs])
                path1.append(''.join(morphs))
            else:
                break
        for l in pathy:
            if l == j:
                morphs = 'Y' + ''.join([x.surface if x.pos == '助詞' else '' for x in sentence[l].morphs])
                path2.append(''.join(morphs))
            elif l != k:
                morphs = ''.join([x.surface if x.pos != '記号' else '' for x in sentence[l].morphs])
                path2.append(''.join(morphs))
            elif l == k or flg:
                flg = 1
                morphs = ''.join([x.surface if x.pos != '記号' else '' for x in sentence[l].morphs])
                path3.append(''.join(morphs))
        print(' -> '.join(path1) + ' | ' + ' -> '.join(path2) + ' | ' + ' -> '.join(path3))

出力は以下。

Xの -> Yで
Xの -> 解説で | Yの -> 佐藤理史は | 述べている
Xの -> 解説で | Yは | 述べている
Xの -> 解説で | Yのに | 述べている
Xで | Yの -> 佐藤理史は | 述べている
Xで | Yは | 述べている
Xで | Yのに | 述べている
Xの -> Yは
Xの -> 佐藤理史は | Yのに | 述べている
Xは | Yのに | 述べている

おわりに

5章はこれで終わりです。
次からはいよいよ機械学習とかに入っていくのでどんどん難しくなってきます。。。