言語処理100本ノック 2020 第5章: 係り受け解析

先日，[言語処理100本ノック2020](https://nlp100.github.io/ja/)が公開されました．私自身，自然言語処理を初めてから1年しか経っておらず，細かいことはよくわかっていませんが，技術力向上のために全ての問題を解いて公開していこうと思います．

すべてjupyter notebook上で実行するものとし，問題文の制約は都合よく破っていいものとします．
ソースコードはgithubにもあります．[あります](https://github.com/nymwa/nlp100/blob/master/chapter05.ipynb)．

4章は[こちら](https://qiita.com/nymwa/items/447211c40dc657132c91)．

環境はPython3.8.2とUbuntu18.04です．

# 第5章: 係り受け解析
> 夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をCaboChaを使って係り受け解析し，その結果をneko.txt.cabochaというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

必要なデータセットは[ここ](https://nlp100.github.io/ja/ch05.html)からダウンロードしてください．

ダウンロードしたファイルは`data`以下に置くものとします．

## CaboChaを使った係り受け解析

```shell:コード
cat data/neko.txt | cabocha -f3 > data/neko.txt.cabocha
```

fオプションを指定することで様々なフォーマットで出力できますが，今回はXML形式にしました．

## 40. 係り受け解析結果の読み込み（形態素）
> 形態素を表すクラスMorphを実装せよ．このクラスは表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をメンバ変数に持つこととする．さらに，CaboChaの解析結果（neko.txt.cabocha）を読み込み，各文をMorphオブジェクトのリストとして表現し，3文目の形態素列を表示せよ．

形態素を表すクラス`Morph`の実装です．

```python:コード
class Morph:
    def __init__(self, token):
        self.surface = token.text
        feature = token.attrib['feature'].split(',')
        self.base = feature[6]
        self.pos = feature[0]
        self.pos1 = feature[1]
        
    def __repr__(self):
        return self.surface
```

XMLを読み込みます．

```python:コード
import xml.etree.ElementTree as ET

with open("neko.txt.cabocha") as f:
    root = ET.fromstring("<sentences>" + f.read() + "</sentences>")
```

文ごとに`Morph`のリストを作り，`neko`リストに格納していきます．

```python:コード
neko = []
for sent in root:
    sent = [chunk for chunk in sent]
    sent = [Morph(token) for chunk in sent for token in chunk]
    neko.append(sent)
```

`neko`の前から3番目のぶんの形態素列を示します．

```python:コード
for x in neko[2]:
    print(x)
```

`Morph`クラスのオブジェクトを`print`すると`__repr__`が呼ばれて表層形が表示されます．

```text:出力
　
吾輩
は
猫
で
ある
。
```

## 41. 係り受け解析結果の読み込み（文節・係り受け）
> 40に加えて，文節を表すクラスChunkを実装せよ．このクラスは形態素（Morphオブジェクト）のリスト（morphs），係り先文節インデックス番号（dst），係り元文節インデックス番号のリスト（srcs）をメンバ変数に持つこととする．さらに，入力テキストのCaboChaの解析結果を読み込み，１文をChunkオブジェクトのリストとして表現し，8文目の文節の文字列と係り先を表示せよ．第5章の残りの問題では，ここで作ったプログラムを活用せよ．

チャンクのクラスと文のクラスを作ります．チャンクの係り先はチャンクオブジェクトを作ったときには生成されず，文のオブジェクトを作ったときに生成されるようにしました．

チャンクと文はリスト型を継承していて，それぞれ形態素とチャンクのリストとして扱えます．

```python:コード
import re

class Chunk(list):
    def __init__(self, chunk):
        self.morphs = [Morph(morph) for morph in chunk]
        super().__init__(self.morphs)
        self.dst = int(chunk.attrib['link'])
        self.srcs = []
    
    def __repr__(self): # 問42で使う
        return re.sub(r'[、。]', '', ''.join(map(str, self)))
```

チャンクは`__repr__`で各形態素をつなげた文字列に変換されます．
このとき，問題42の制約にあわせて句読点を取り除いています．

```python:コード
class Sentence(list):
    def __init__(self, sent):
        self.chunks = [Chunk(chunk) for chunk in sent]
        super().__init__(self.chunks)
        for i, chunk in enumerate(self.chunks):
            if chunk.dst != -1:
                self.chunks[chunk.dst].srcs.append(i)
```

```python:コード
neko = [Sentence(sent) for sent in root]
```

これで文ごとの解析結果をリストに格納できました．

```python:コード
from tabulate import tabulate
```

`tabulate.tabulate`を使って見やすく表示します．

```python:コード
table = [
    [''.join([morph.surface for morph in chunk]), chunk.dst]
    for chunk in neko[7]
]
tabulate(table, tablefmt = 'html', headers = ['番号', '文節', '係り先'], showindex = 'always')
```

```text:出力
  番号  文節          係り先
------  ----------  --------
     0  吾輩は             5
     1  ここで             2
     2  始めて             3
     3  人間という         4
     4  ものを             5
     5  見た。            -1
```

## 42. 係り元と係り先の文節の表示
> 係り元の文節と係り先の文節のテキストをタブ区切り形式ですべて抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

```python:コード
sent = neko[7]
for chunk in sent:
    if chunk.dst != -1:
        src = chunk
        dst = sent[chunk.dst]
        print(f'{src}\t{dst}')
```

チャンクごとにチャンクと係り先のチャンクを文字列にして表示するだけです．

```text:出力
吾輩は	見た
ここで	始めて
始めて	人間という
人間という	ものを
ものを	見た
```

## 43. 名詞を含む文節が動詞を含む文節に係るものを抽出
> 名詞を含む文節が，動詞を含む文節に係るとき，これらをタブ区切り形式で抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

```python:コード
def has_noun(chunk):
    return any(morph.pos == '名詞' for morph in chunk)

def has_verb(chunk):
    return any(morph.pos == '動詞' for morph in chunk)
```

```python:コード
sent = neko[7]
for chunk in sent:
    if chunk.dst != -1 and has_noun(chunk) and has_verb(sent[chunk.dst]):
        src = chunk
        dst = sent[chunk.dst]
        print(f'{src}\t{dst}')
```

チャンクが名詞・動詞を含むかを判定する関数を作り，条件に一致するものだけを表示します．

```text:出力
吾輩は 見た
ここで 始めて
ものを 見た
```

## 44. 係り受け木の可視化
> 与えられた文の係り受け木を有向グラフとして可視化せよ．可視化には，係り受け木をDOT言語に変換し，Graphvizを用いるとよい．また，Pythonから有向グラフを直接的に可視化するには，pydotを使うとよい．

```python:コード
from pydot import Dot, Edge, Node
from PIL import Image
```

```python:コード
sent = neko[7]

graph = Dot(graph_type = 'digraph')

# 節を作る
for i, chunk in enumerate(sent):
    node = Node(i, label = chunk)
    graph.add_node(node)
    
# 枝を作る
for i, chunk in enumerate(sent):
    if chunk.dst != -1:
        edge = Edge(i, chunk.dst)
        graph.add_edge(edge)
        
graph.write_png('sent.png')
Image.open('sent.png')
```

<img src="https://raw.githubusercontent.com/nymwa/nlp100/master/result/sent.png">

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

```python:コード
def get_first_verb(chunk):
    for morph in chunk:
        if morph.pos == '動詞':
            return morph.base

def get_last_case(chunk):
    for morph in chunk[::-1]:
        if morph.pos == '助詞':
            return morph.surface
        
def extract_cases(srcs):
    xs = [get_last_case(src) for src in srcs]
    xs = [x for x in xs if x]
    xs.sort()
    return xs
```

チャンクが動詞から始まるかを判定し，係り元のチャンクの助詞を抜き出します．

```python:コード
with open('result/case_pattern.txt', 'w') as f:
    for sent in neko:
        for chunk in sent:
            if verb := get_first_verb(chunk): # 動詞から始まる
                srcs = [sent[src] for src in chunk.srcs]
                if cases := extract_cases(srcs): # 助詞がある
                    line = '{}\t{}'.format(verb, ' '.join(cases))
                    print(line, file=f)
```

```shell:コード
cat result/case_pattern.txt | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
   2645 ある	が
   1559 つく	か が
    840 云う	は
    553 する	が で と
    380 つかむ	を
    364 思う	と
    334 見る	の
    257 かく	たり を
    253 かかる	が て
    205 ある	まで
```

```shell:コード
cat result/case_pattern.txt | grep 'する' | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
   1239 する	が
    806 する	て は
    313 する	が で と
    140 する	でも に
    102 する	まで
     84 する	と は は は
     59 する	から が で
     32 する	から て て を
     32 する	を んで
     24 する	として
```

```shell:コード
cat result/case_pattern.txt | grep '見る' | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
    334 見る	の
    121 見る	は を
     40 見る	て て は
     25 見る	たり て
     23 見る	から
     12 見る	から て て
      8 見る	て に は を
      7 見る	が ので
      3 見る	て ばかり
      3 見る	が て んで
```

```shell:コード
cat result/case_pattern.txt | grep '与える' | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
      7 与える	に を
      4 与える	で に を
      3 与える	て と は を
      1 与える	けれども は を
      1 与える	か として
      1 与える	が て と に は は を
      1 与える	て に に は を
```

## 46. 動詞の格フレーム情報の抽出
> 45のプログラムを改変し，述語と格パターンに続けて項（述語に係っている文節そのもの）をタブ区切り形式で出力せよ．45の仕様に加えて，以下の仕様を満たすようにせよ．
>
> 　・項は述語に係っている文節の単語列とする（末尾の助詞を取り除く必要はない）
> 　・述語に係る文節が複数あるときは，助詞と同一の基準・順序でスペース区切りで並べる
> 「吾輩はここで始めて人間というものを見た」という例文（neko.txt.cabochaの8文目）を考える． この文は「始める」と「見る」の２つの動詞を含み，「始める」に係る文節は「ここで」，「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は，次のような出力になるはずである．
> 
> 　始める  で      ここで
> 　見る    は を   吾輩は ものを

```python:コード
def extract_args(srcs):
    xs = [src for src in srcs if get_last_case(src)]
    xs.sort(key = lambda src : get_last_case(src))
    xs = [str(src) for src in xs]
    return xs
```

問題45のコードを改変し，元のチャンクも表示させます．

```python:コード
for sent in neko[:10]:
    for chunk in sent:
        if verb := get_first_verb(chunk): # 動詞で始まる
            srcs = [sent[src] for src in chunk.srcs]
            if cases := extract_cases(srcs): # 助詞がある
                args = extract_args(srcs)
                line = '{}\t{}\t{}'.format(verb, ' '.join(cases), ' '.join(args))
                print(line)
```

```python:出力
生れる	で	どこで
つく	か が	生れたか 見当が
泣く	で	所で
する	て は	泣いて いた事だけは
始める	で	ここで
見る	は を	吾輩は ものを
聞く	で	あとで
捕える	を	我々を
煮る	て	捕えて
食う	て	煮て
```

## 47. 機能動詞構文のマイニング
> 動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい．46のプログラムを以下の仕様を満たすように改変せよ．
>
> 　・「サ変接続名詞+を（助詞）」で構成される文節が動詞に係る場合のみを対象とする
> 　・述語は「サ変接続名詞+を+動詞の基本形」とし，文節中に複数の動詞があるときは，最左の動詞を用いる
> 　・述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる
> 　・述語に係る文節が複数ある場合は，すべての項をスペース区切りで並べる（助詞の並び順と揃えよ）
> 　・例えば「別段くるにも及ばんさと、主人は手紙に返事をする。」という文から，以下の出力が得られるはずである．
>
> 　返事をする      と に は        及ばんさと 手紙に 主人は
> このプログラムの出力をファイルに保存し，以下の事項をUNIXコマンドを用いて確認せよ．
>
> 　・コーパス中で頻出する述語（サ変接続名詞+を+動詞）
> 　・コーパス中で頻出する述語と助詞パターン

```python:コード
def is_sahen(chunk):
    return len(chunk) == 2 and chunk[0].pos1 == 'サ変接続' and chunk[1].surface == 'を'

def split_sahen(srcs):
    for i in range(len(srcs)):
        if is_sahen(srcs[i]):
            return str(srcs[i]), srcs[:i] + srcs[i+1:]
    return None, srcs
```

`split_sahen`で，動詞を含むチャンクの係り元のチャンクから「サ変接続動詞＋を〜」の形のチャンクを取り出してきます．

```python:コード
with open('result/sahen_pattern.txt', 'w') as f:
    for sent in neko:
        for chunk in sent:
            if verb := get_first_verb(chunk):
                srcs = [sent[src] for src in chunk.srcs]
                sahen, rest = split_sahen(srcs)
                if sahen and (cases := extract_cases(rest)):
                    args = extract_args(rest)
                    line = '{}\t{}\t{}'.format(sahen + verb, ' '.join(cases), ' '.join(args))
                    print(line, file=f)
```

```shell:コード
cat result/sahen_pattern.txt | cut -f 1 | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
     25 返事をする
     19 挨拶をする
     11 話をする
      9 質問をする
      7 真似をする
      7 喧嘩をする
      5 質問をかける
      5 相談をする
      5 昼寝をする
      4 演説をする
```

```shell:コード
cat result/sahen_pattern.txt | cut -f 1,2 | sort | uniq -c | sort -nr 2> /dev/null | head -n 10
```

```text:出力
     10 返事をする	と
      7 返事をする	と は
      7 挨拶をする	で
      5 質問をかける	と は
      5 喧嘩をする	で
      4 質問をえる	で
      4 話をする	に
      4 挨拶をする	から
      3 返事をする	から と
      3 談話を聞く	が
```

## 48. 名詞から根へのパスの抽出
> 文中のすべての名詞を含む文節に対し，その文節から構文木の根に至るパスを抽出せよ． ただし，構文木上のパスは以下の仕様を満たすものとする．
>
> 　・各文節は（表層形の）形態素列で表現する
> 　・パスの開始文節から終了文節に至るまで，各文節の表現を” -> “で連結する
> 「吾輩はここで始めて人間というものを見た」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．
>
> 　吾輩は -> 見た
> 　ここで -> 始めて -> 人間という -> ものを -> 見た
> 　人間という -> ものを -> 見た
> 　ものを -> 見た

```python:コード
def trace(n, sent):
    path = []
    while n != -1:
        path.append(n)
        n = sent[n].dst
    return path
```

```python:コード
sent = neko[7]
heads = [n for n in range(len(sent)) if has_noun(sent[n])]
for head in heads:
    path = trace(head, sent)
    path = ' -> '.join([str(sent[n]) for n in path])
    print(path)
```

名詞を持つチャンクの番号をすべて求め，それぞれ係り先をトレースしながらパスをチャンク番号のリストとして得ます．
最後にチャンクをパスの順番通り表示させていけばよいです．

```text:出力
吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た
```

## 49. 名詞間の係り受けパスの抽出
> 文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ．ただし，名詞句ペアの文節番号がiとj（i<j）のとき，係り受けパスは以下の仕様を満たすものとする．
>
> 　・問題48と同様に，パスは開始文節から終了文節に至るまでの各文節の表現（表層形の形態素列）を” -> “で連結して表現する
> 　・文節iとjに含まれる名詞句はそれぞれ，XとYに置換する
> また，係り受けパスの形状は，以下の2通りが考えられる．
> 
> 　・文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
> 　・上記以外で，文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス，文節kの内容を” | “で連結して表示
> 例えば，「吾輩はここで始めて人間というものを見た。」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．
> 
> 　Xは | Yで -> 始めて -> 人間という -> ものを | 見た
> 　Xは | Yという -> ものを | 見た
> 　Xは | Yを | 見た
> 　Xで -> 始めて -> Y
> 　Xで -> 始めて -> 人間という -> Y
> 　Xという -> Y

```python:コード
def extract_path(x, y, sent):
    xs = []
    ys = []
    while x != y:
        if x < y:
            xs.append(x)
            x = sent[x].dst
        else:
            ys.append(y)
            y = sent[y].dst
    return xs, ys, x

def remove_initial_nouns(chunk):
    for i, morph in enumerate(chunk):
        if morph.pos != '名詞':
            break
    return ''.join([str(morph) for morph in chunk[i:]]).strip()

def path_to_str(xs, ys, last, sent):
    xs = [sent[x] for x in xs]
    ys = [sent[y] for y in ys]
    last = sent[last]
    if xs and ys:
        xs = ['X' + remove_initial_nouns(xs[0])] + [str(x) for x in xs[1:]]
        ys = ['Y' + remove_initial_nouns(ys[0])] + [str(y) for y in ys[1:]]
        last = str(last)
        return ' -> '.join(xs) + ' | ' + ' -> '.join(ys) + ' | ' + last
    else:
        xs = xs + ys
        xs = ['X' + remove_initial_nouns(xs[0])] + [str(x) for x in xs[1:]]
        last = 'Y' + remove_initial_nouns(last)
        return ' -> '.join(xs + [last])
```

```python:コード
sent = neko[7]

heads = [n for n in range(len(sent)) if has_noun(sent[n])]
print('パスの先頭:', heads)

pairs = [
    (heads[n], second)
    for n in range(len(heads))
    for second in heads[n + 1:]
]
print('パスの先頭のペア: ', pairs)

print('係り受けのパス:')
for x, y in pairs:
    x_path, y_path, last = extract_path(x, y, sent)
    path = path_to_str(x_path, y_path, last, sent)
    print(path)
```

まず名詞を持つチャンクの番号のリストを得ます．

次に，そのチャンクのすべてのペアを得ます．

そして，各ペアにたいして，同じチャンクに到達するまでパスを求めていき，それぞれのパス`x_path`,`y_path`と最後に到達した共通のチャンク`last`に基づいて，`path_to_str`で指定された形式に変換しています．

```text:出力
パスの先頭: [0, 1, 3, 4]
パスの先頭のペア:  [(0, 1), (0, 3), (0, 4), (1, 3), (1, 4), (3, 4)]
係り受けのパス:
Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Yという
Xで -> 始めて -> 人間という -> Yを
Xという -> Yを
```


## 次は第6章

[言語処理100本ノック 2020 第6章: 機械学習](https://qiita.com/nymwa/items/774ca6c542c1eaff160d)