言語処理100本ノック2020 (45~49)

# はじめに
本記事は言語処理100本ノックの解説です。
100本のノックを全てこなした記録をQiitaに残します。
使用言語はPythonです。

https://nlp100.github.io/2020/ja/

今回は第5章: 係り受け解析(45~49)までの解答例をご紹介します。
5章前半(40~44)の解答例はこちらです。

https://qiita.com/Dukapan100knock/items/86d6649096127f2f8d7a

# 45. 動詞の格パターンの抽出
>今回用いている文章をコーパスと見なし，日本語の述語が取りうる格を調査したい． 動詞を述語，動詞に係っている文節の助詞を格と考え，述語と格をタブ区切り形式で出力せよ． ただし，出力は以下の仕様を満たすようにせよ．
>
>・動詞を含む文節において，最左の動詞の基本形を述語とする
・述語に係る助詞を格とする
・述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる
「ジョン・マッカーシーはAIに関する最初の会議で人工知能という用語を作り出した。」という例文を考える． この文は「作り出す」という１つの動詞を含み，「作り出す」に係る文節は「ジョン・マッカーシーは」，「会議で」，「用語を」であると解析された場合は，次のような出力になるはずである．
>```
>作り出す	で は を
>```
>このプログラムの出力をファイルに保存し，以下の事項をUNIXコマンドを用いて確認せよ．
>
>・コーパス中で頻出する述語と格パターンの組み合わせ
・「行う」「なる」「与える」という動詞の格パターン（コーパス中で出現頻度の高い順に並べよ）

**準備**
問題44で使用した以下のプログラムから「kakari_list」を求めます。
```python:コード
import MeCab
import unidic
mecab= MeCab.Tagger("")
text_dic = {}
i = 0
kakari_prelist = []
kakari_list = []
for line in all_sentense:
    text = ""
    for sign_check in line["morphs"]:
        if mecab.parse(sign_check).split("\t")[1].split(",")[0] in "補助記号":#記号の除去
            pass
        else:
            text += sign_check.split("\t")[0]
    #辞書に追加、かかり元を参照する
    text = str(i) + " "+ text #44番かかり受け木作成用に追加
    text_dic[i] = text
    i += 1
    ##出力
    if line["srcs"]==[]:
        pass
    else:
        pnum = line["srcs"]
        for j in pnum:
            kakari_prelist.append(text_dic[int(j)] + '\t' + text)
    if line["dst"]==-1:
        if kakari_prelist:
            kakari_list.append(kakari_prelist)#44番用, #45番用
        kakari_prelist = []
        text_dic = {}
        i = 0
kakari_list
```
```text:出力結果
[['2 AI\t3 エーアイとは',
  '4 計算\t5 という',
  '7 コンピュータ\t8 という',
  '5 という\t9 道具を',
  '6 概念と\t9 道具を',
  '8 という\t9 道具を',
  '9 道具を\t10 用いて',
  '10 用いて\t12 研究する',
  '11 知能を\t12 研究する',
  '12 研究する\t13 計算機科学',
  '13 計算機科学\t14 の',
  '14 の\t15 一分野を',
  '15 一分野を\t16 指す',
  '0 人工知能\t17 語',
  '1 じんこうちのう\t17 語',
  '3 エーアイとは\t17 語',
  '16 指す\t17 語'],
~~~~~~~~~省略~~~~~~~~~
```
**コード**
```python:コード
import MeCab
import re
mecab= MeCab.Tagger("")
f = open("[PATH]/verb_pattern.txt", "a")
for lines in kakari_list:#2次元リスト、かかり受け対応している
    Flag = 0
    joshi_dic = {}
    for text in lines:#各文章ごとの処理
        word = text.split("\t")#かかり受けを分ける
        #後半の形態素解析
        word2nd = mecab.parse(word[1].split(" ")[1]).split("\n")
        for item in word2nd:
            verb =re.split("[\t,]", item)#リストを整える
            if verb[0] == "EOS" or len(verb) == 1:#EOS、スペースのみリストを除去
                continue
            if verb[1] == "動詞":#後半に動詞が含まれているか判定
                if Flag == 1:#最左動詞の判定用(例)述べて+いる→述べるのみ判定できるように
                    continue
                Flag = 1#Flagをあげる
                #その時に前半の形態素解析で助詞が含まれているか見る
                word1st = mecab.parse(word[0].split(" ")[1]).split("\n")
                for item2 in word1st:
                    joshi = re.split("[\t,]", item2)#前半リストを整える
                    if joshi[0] == "EOS" or len(joshi) == 1:#EOS、スペースのみリストを除去
                        continue
                    if joshi[1]=="助詞":#助詞を見つけた時にリストに格納
                        key_verb = word[1].split(" ")[0] + ":" + verb[11]
                        joshi_dic.setdefault(key_verb, []).append(joshi[0])
        Flag = 0#Flagを下ろす
        i += 1
    for k, v in joshi_dic.items():#Fileに書き込み
        k = k.split(":")[1]
        v = sorted(v)#助詞は辞書順で並べなさいとのこと
        text = str(k) + "\t" + " ".join(v) + "\n"
        f.write(text)
f.close()
```

```text:verb_pattern.txt
用いる	を
する	て を
指す	を
代わる	に を
行う	て に
関する	の や
述べる	で の は
する	で を
する	を
する	を
~~~省略~~~
```
**UNIXコマンドによる確認**
>・コーパス中で頻出する述語と格パターンの組み合わせ
```text:コマンド
$ cat "[PATH]/verb_pattern.txt" |sort|uniq -c|sort -nr
```
```text:出力結果
332 する	を
116 する	が
 88 する	と
 72 する	に
 68 する	は を
~~~~~~省略~~~~~~
```
>・「行う」「なる」「与える」という動詞の格パターン（コーパス中で出現頻度の高い順に並べよ）
```text:コマンド
$ cat "[PATH]/verb_pattern.txt" |grep "行う"|sort|uniq -c|sort -nr
$ cat "[PATH]/verb_pattern.txt" |grep "なる"|sort|uniq -c|sort -nr
$ cat "[PATH]/verb_pattern.txt" |grep "与える"|sort|uniq -c|sort -nr
```
```text:出力結果
#行う
30 行う	を
  6 行う	に を を
  6 行う	に
~~~~~~省略~~~~~~

#なる
 10 なる	に は
  6 異なる	も
  6 異なる	が で
~~~~~~省略~~~~~~

#与える
  6 与える	に は を
  6 与える	が など に
  6 与える	が
```
**コメント**
割と難しかった。仕様も細かく決められているし。複雑なプログラムは読解するよりも自分で一から作った方が良いかもです。

# 46. 動詞の格フレーム情報の抽出
>45のプログラムを改変し，述語と格パターンに続けて項（述語に係っている文節そのもの）をタブ区切り形式で出力せよ．45の仕様に加えて，以下の仕様を満たすようにせよ．
>
>項は述語に係っている文節の単語列とする（末尾の助詞を取り除く必要はない）
述語に係る文節が複数あるときは，助詞と同一の基準・順序でスペース区切りで並べる
「ジョン・マッカーシーはAIに関する最初の会議で人工知能という用語を作り出した。」という例文を考える． この文は「作り出す」という１つの動詞を含み，「作り出す」に係る文節は「ジョン・マッカーシーは」，「会議で」，「用語を」であると解析された場合は，次のような出力になるはずである．
>```
>作り出す	で は を	会議で ジョンマッカーシーは 用語を
>```

```python:コード
import MeCab
import re
mecab= MeCab.Tagger("")
frame_list = []
for lines in kakari_list:
    joshi_dic = {}
    Flag = 0
    for text in lines:
        word = text.split("\t")
        word2nd = mecab.parse(word[1].split(" ")[1]).split("\n")
        for item in word2nd:
            verb =re.split("[\t,]", item)
            if verb[0] == "EOS" or len(verb) == 1:
                continue
            if verb[1] == "動詞":
                if Flag == 1:
                    continue
                Flag = 1
                word1st = mecab.parse(word[0].split(" ")[1]).split("\n")
                for item2 in word1st:
                    joshi = re.split("[\t,]", item2)
                    if joshi[0] == "EOS" or len(joshi) == 1:
                        continue
                    if joshi[1]=="助詞":
                        key_verb = word[1].split(" ")[0] + ":" + verb[11]
                        #joshi_dicのvalueを助詞と文節の二次元リストにした
                        joshi_dic.setdefault(key_verb, []).append([joshi[0], word[0].split(" ")[1]])
        Flag = 0
    for k, v in joshi_dic.items():#frame_listに書き出し
        k = k.split(":")[1]
        v = sorted(v, key=lambda x:x[0])
        text1 = []
        text2 = []
        for v2 in v:
            text1.append(v2[0])
            text2.append(v2[1])
        temp = str(k) + "\t" + " ".join(text1) + "\t" + " ".join(text2)
        frame_list.append(temp)
frame_list
```
```text:出力結果
 '作り出す\tで は を\t会議で ジョンマッカーシーは 用語を',
 'する\tは を\t彼はまた プログラミング言語を',
 'する\tを\tテストを',
 'する\tて と は を\t方法として 方法として アランチューリングは チューリングテストを',
 ~~~~~~~~~省略~~~~~~~~~
```
**コメント**
問題文の例の部分を出力結果として掲載しました。そこが合っているから他もあっていると信じています...
リスト「frame_list」は問題47で使います。

# 47. 機能動詞構文のマイニング
>動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい．46のプログラムを以下の仕様を満たすように改変せよ．
>
>「サ変接続名詞+を（助詞）」で構成される文節が動詞に係る場合のみを対象とする
述語は「サ変接続名詞+を+動詞の基本形」とし，文節中に複数の動詞があるときは，最左の動詞を用いる
述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる
述語に係る文節が複数ある場合は，すべての項をスペース区切りで並べる（助詞の並び順と揃えよ）
例えば「また、自らの経験を元に学習を行う強化学習という手法もある。」という文から，以下の出力が得られるはずである．
>```
>学習を行う	に を	元に 経験を
>```


```python:コード
#47
import MeCab
import re
import copy
mecab= MeCab.Tagger("")
result47 = []

for line in frame_list:#46のframelistを使用
    base_verb = line.split("\t")[0]#元の動詞
    joshi_list = line.split("\t")[1].split(" ")#助詞
    verbs_list = line.split("\t")[2].split(" ")#述語になり得る部分
    for verbs, joshi in zip(verbs_list, joshi_list):
        joshi_list_temp = copy.copy(joshi_list)#述語になる名詞は除かれるのでコピーをとっておく
        verbs_list_temp = copy.copy(verbs_list)
        verbs_m = mecab.parse(verbs)#mecabに食わせる
        verbs_m =re.split("[\t,]", verbs_m)#リストの整形
        if verbs_m[0] == "EOS" or len(verbs_m) == 1:
            continue
        if verbs_m[3]=="サ変可能":#サ変を見つける
            if joshi == "を":#をの判定
                verb_result = verbs_m[0]+ joshi + base_verb#出力用の文字列
                joshi_list_temp.remove("を")#述語になったので除去する
                verbs_list_temp.remove(verbs)#同上
                if len(verbs_list_temp)==0:#もし述語になったせいでかかる名詞がなくなったらそれは無くす
                    continue
                #書き出し
                result47.append(verb_result+"\t" + " ".join(joshi_list_temp)+"\t"+" ".join(verbs_list_temp))
            else:
                pass
result47
```
```text:出力結果
 '学習を行う\tに を\t元に 経験を',
 '推論をする\tて で に は を を\t生成規則を通して ACTRでは 元に ACTRでは 統計的学習を 生成規則を通して',
 '統計をする\tて で に は を を\t生成規則を通して ACTRでは 元に ACTRでは 推論ルールを 生成規則を通して',
 '生成をする\tて で に は を を\tACTRでは 元に ACTRでは 推論ルールを 統計的学習を 生成規則を通して',
 '進化を見せる\tて て に は\t加えて 生成技術において 生成技術において 敵対的生成ネットワークは',
  ~~~~~~~~~省略~~~~~~~~~
```

**コメント**
本章の問題は提示される条件がかなり細かいですね。仕様通りにプログラムを書く練習になります。


# 48. 名詞から根へのパスの抽出
>文中のすべての名詞を含む文節に対し，その文節から構文木の根に至るパスを抽出せよ． ただし，構文木上のパスは以下の仕様を満たすものとする．
>
>・各文節は（表層形の）形態素列で表現する
・パスの開始文節から終了文節に至るまで，各文節の表現を” -> “で連結する
「ジョン・マッカーシーはAIに関する最初の会議で人工知能という用語を作り出した。」という例文を考える． CaboChaを係り受け解析に用いた場合，次のような出力が得られると思われる．
>```
>ジョンマッカーシーは -> 作り出した
>AIに関する -> 最初の -> 会議で -> 作り出した
>最初の -> 会議で -> 作り出した
>会議で -> 作り出した
>人工知能という -> 用語を -> 作り出した
>用語を -> 作り出した
>```
>KNPを係り受け解析に用いた場合，次のような出力が得られると思われる．
>```
>ジョンマッカーシーは -> 作り出した
>ＡＩに -> 関する -> 会議で -> 作り出した
>会議で -> 作り出した
>人工知能と -> いう -> 用語を -> 作り出した
>用語を -> 作り出した
>```
```python:コード
#48
with open('[PATH]/ai.ja.txt.parsed', "r") as f:
    lines = f.readlines()
    text_dic = {}
    dic_list = []
    text = ""
    Flag_N = 0
    Flag_lastline = 0
    index_num = 0
    for line in lines:
        if line == "EOS\n": #文章の終わり
            if Flag_lastline == 1:
                if Flag_N == 1:
                    text = "N:"+ text
                    Flag_N = 0
                text_dic[index_num] = [text, num]
                dic_list.append(text_dic)
                text_dic = {}
                Flag_lastline = 0
            continue

        if line[0] == "*":
            if Flag_N == 1:
                text = "N:"+ text
                Flag_N = 0
            if int(line.split(" ")[1])==0:
                pass
            else:
                text_dic[index_num] = [text, num]
            num = int(line.split(" ")[2][:-1])#かかり先
            index_num = int(line.split(" ")[1])#かかり元
            text = ""
            if num == -1:
                Flag_lastline = 1
            continue
        if line.split("\t")[1][0:2]=="記号":
            continue
        text += line.split("\t")[0]
        if line.split("\t")[1].split(",")[0]=="名詞":
            Flag_N = 1

def MakeTree(dic_list):#かかりむすびの木を作る
    result = []
    for text in dic_list.items():
        if text[1][0].split(":")[0]=="N":
            temp = ""
            num = int(text[0])
            while True:
                word = dic_list[num][0]
                num = int(dic_list[num][1])
                if num == -1:
                    temp += word
                    temp = temp.replace("N:","")
                    break
                else:
                    temp += word + "->"
            result.append(temp)
    return result

result_list48 = []
for index_dic in dic_list:
    index = MakeTree(index_dic)
    if len(index) == 0:
        continue
    result_list48.extend(index)
result_list48
```
```text:出力結果
 'ジョンマッカーシーは->作り出した',
 'AIに関する->最初の->会議で->作り出した',
 '最初の->会議で->作り出した',
 '会議で->作り出した',
 '人工知能という->用語を->作り出した',
 '用語を->作り出した',
 '彼はまた->開発した',
 'プログラミング言語を->開発した',
  ~~~~~~~~~省略~~~~~~~~~
```
**コメント**
問題文のCaboChaを係り受け解析結果と同じになりました。処理中の変数に目印となる「N:」みたいな値を追加して後続の処理で活用する方法はおすすめです。
リスト「dic_list」関数「MakeTree()」は問題49で使います。


# 49. 名詞間の係り受けパスの抽出
>文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ．ただし，名詞句ペアの文節番号がiとj（i<j）のとき，係り受けパスは以下の仕様を満たすものとする．
>
>・問題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を
>```
```python:コード
import itertools
import MeCab
mecab= MeCab.Tagger("")
result_list49 = []

def XYEncoder(text, z):#名詞をXYに置き換える
    mtext = mecab.parse(text)
    result = ""
    Flag = 0
    mtext = mtext.split("\n")
    temp = []
    for m in mtext:
        if m.split("\t")[0] == "EOS" or len(m) == 0:
            continue
        hinshi = m.split("\t")[1].split(",")[0]
        temp.append(hinshi)
        if hinshi!="名詞" and hinshi!="形状詞" and hinshi!="代名詞":
            result += m.split("\t")[0]
        elif Flag == 1:
            continue
        else:
            result += z
            Flag = 1
    return result

def Clener(text):#文字のIDを消し去る
    for i in range(len(text)):
        text[i] = text[i].split(":")[0]
    return text

def Remakedict(predic):#単語ごとにIDを渡す
    numembid = 0
    for n, text in predic.items():
        temp = [text[0] + ":{}".format(str(numembid)), text[1]]
        predic[n] = temp
        numembid += 1
    return predic

def Pairmaker(predic, sent_list):#名詞の組み合わせと名詞のみの係結び木を抽出する
    n_list = []
    kakari_dic = {}
    i = 0
    for n, text in predic.items():
        if text[0].split(":")[0]=="N":
            n_list.append(n)
            kakari_dic[n] = sent_list[i]
            i += 1
    return n_list, kakari_dic
#dic_listは問題48で作った
for predic in dic_list:#各文ごとに回す
    result_list = []
    predic = Remakedict(predic)#単語ごとにIDを渡す
    sent_list = MakeTree(predic)#かかりむすびの木を作る(問題48の関数)
    n_list, kakari_dic = Pairmaker(predic, sent_list)#名詞の組み合わせと名詞のみの係結び木を抽出する
    conb_list = list(itertools.combinations(n_list, 2))#単語の組み合わせの全パターンを返す
    for conb in conb_list:#全パターンを回す
        sent1 = kakari_dic[conb[0]].split("->")#それぞれの係結びの木を辞書から呼ぶ
        sent2 = kakari_dic[conb[1]].split("->")
        break_Flag = 0
        for sen2 in reversed(sent2):#メインの処理
            for sen1 in reversed(sent1):
                if sen2 == sen1:
                    last_word = sen2
                    sent1 = sent1[:-1]
                    sent2 = sent2[:-1]
                    if len(sent2)==0:
                        sent1.append(last_word)
                        break_Flag = 2
                        break
                    elif len(sent2)==1:
                        if len(sent1) == 1:
                            break_Flag = 1
                        else:
                            sent1[len(sent1)-1]=sent2[0]
                            break_Flag = 2
                        break
                    else:
                        sen2 = sent2[len(sent2)-1]
                else:
                    break_Flag = 1
                    break

            if break_Flag == 1:
                sent1[0] = XYEncoder(sent1[0], "X")
                sent2[0] = XYEncoder(sent2[0], "Y")
                sent1 = Clener(sent1)
                sent2 = Clener(sent2)
                last_word = last_word.split(":")[0]
                result49 = "->".join(sent1) + "|" + "->".join(sent2) + "|" + last_word
                break_Flag = 0
                break
            elif break_Flag == 2:
                sent1[0] = XYEncoder(sent1[0], "X")
                sent1[-1] = XYEncoder(sent1[-1], "Y")
                sent1 = Clener(sent1)
                result49 = "->".join(sent1)
                break_Flag = 0
                break

        if "X" not in result49 or "Y" not in result49:
            pass
        else:
            result_list.append(result49)#結果を追加
    if len(result_list) == 0:#空のリストがきたらスキップ
        continue
    result_list49.append(result_list)#最終結果、本文の一文ごとに区切って追加
#result_list49
```
```text:出力結果
[['X|Yのう|語',
  'X|Y->エーアイとは|語',
  'X|Yとは|語',
  'X|Y->という->道具を->用いて->研究する->計算機科学->の->一分野を->指す|語',
  'X|Yと->道具を->用いて->研究する->計算機科学->の->一分野を->指す|語',
  'X|Y->という->道具を->用いて->研究する->計算機科学->の->一分野を->指す|語',
  'X|Yを->用いて->研究する->計算機科学->の->一分野を->指す|語',
  'X|Yを->研究する->計算機科学->の->一分野を->指す|語',
  'X|Yする->計算機科学->の->一分野を->指す|語',
  'X|Y->の->一分野を->指す|語',
  'X|Yを->指す|語',
   ~~~~~~~~~省略~~~~~~~~~
```

**コメント**
一応、問題文と同じ文章では同じ結果になりました。解答例では先頭の部分を載せています。難しい問題でした。。。

# 他章の解答例

https://qiita.com/Dukapan100knock/items/d418f2aa37b2b3d16428