素人の言語処理100本ノック:49


[言語処理100本ノック 2015](http://www.cl.ecei.tohoku.ac.jp/nlp100/)の挑戦記録です。環境はUbuntu 16.04 LTS ＋ Python 3.5.2 \:\: Anaconda 4.1.1 (64-bit)です。過去のノックの一覧は[こちら](http://qiita.com/segavvy/items/fb50ba8097d59475f760)からどうぞ。

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

###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:main.py
# coding: utf-8
import CaboCha
import re

fname = 'neko.txt'
fname_parsed = 'neko.txt.cabocha'
fname_result = 'result.txt'


def parse_neko():
	'''「吾輩は猫である」を係り受け解析
	「吾輩は猫である」(neko.txt)を係り受け解析してneko.txt.cabochaに保存する
	'''
	with open(fname) as data_file, \
			open(fname_parsed, mode='w') as out_file:

		cabocha = CaboCha.Parser()
		for line in data_file:
			out_file.write(
				cabocha.parse(line).toString(CaboCha.FORMAT_LATTICE)
			)


class Morph:
	'''
	形態素クラス
	表層形（surface）、基本形（base）、品詞（pos）、品詞細分類1（pos1）を
	メンバー変数に持つ
	'''
	def __init__(self, surface, base, pos, pos1):
		'''初期化'''
		self.surface = surface
		self.base = base
		self.pos = pos
		self.pos1 = pos1

	def __str__(self):
		'''オブジェクトの文字列表現'''
		return 'surface[{}]\tbase[{}]\tpos[{}]\tpos1[{}]'\
			.format(self.surface, self.base, self.pos, self.pos1)


class Chunk:
	'''
	文節クラス
	形態素（Morphオブジェクト）のリスト（morphs）、係り先文節インデックス番号（dst）、
	係り元文節インデックス番号のリスト（srcs）をメンバー変数に持つ
	'''

	def __init__(self):
		'''初期化'''
		self.morphs = []
		self.srcs = []
		self.dst = -1

	def __str__(self):
		'''オブジェクトの文字列表現'''
		surface = ''
		for morph in self.morphs:
			surface += morph.surface
		return '{}\tsrcs{}\tdst[{}]'.format(surface, self.srcs, self.dst)

	def normalized_surface(self):
		'''句読点などの記号を除いた表層形'''
		result = ''
		for morph in self.morphs:
			if morph.pos != '記号':
				result += morph.surface
		return result

	def chk_pos(self, pos):
		'''指定した品詞（pos）を含むかチェックする

		戻り値：
		品詞（pos）を含む場合はTrue
		'''
		for morph in self.morphs:
			if morph.pos == pos:
				return True
		return False

	def get_morphs_by_pos(self, pos, pos1=''):
		'''指定した品詞（pos）、品詞細分類1（pos1）の形態素のリストを返す
		pos1の指定がない場合はposのみで判定する

		戻り値：
		形態素（morph）のリスト、該当形態素がない場合は空のリスト
		'''
		if len(pos1) > 0:
			return [res for res in self.morphs
					if (res.pos == pos) and (res.pos1 == pos1)]
		else:
			return [res for res in self.morphs if res.pos == pos]

	def get_kaku_prt(self):
		'''助詞を1つ返す
		複数ある場合は格助詞を優先し、最後の助詞を返す。

		戻り値：
		助詞、ない場合は空文字列
		'''
		prts = self.get_morphs_by_pos('助詞')
		if len(prts) > 1:

			# 2つ以上助詞がある場合は、格助詞を優先
			kaku_prts = self.get_morphs_by_pos('助詞', '格助詞')
			if len(kaku_prts) > 0:
				prts = kaku_prts

		if len(prts) > 0:
			return prts[-1].surface		# 最後を返す
		else:
			return ''

	def get_sahen_wo(self):
		'''「サ変接続名詞＋を」を含無場合は、その部分の表層形を返す

		戻り値：
		「サ変接続名詞＋を」の文字列、なければ空文字列
		'''
		for i, morph in enumerate(self.morphs[0:-1]):

			if (morph.pos == '名詞') \
					and (morph.pos1 == 'サ変接続') \
					and (self.morphs[i + 1].pos == '助詞') \
					and (self.morphs[i + 1].surface == 'を'):
				return morph.surface + self.morphs[i + 1].surface

		return ''

	def noun_masked_surface(self, mask, dst=False):
		'''名詞を指定文字(mask)でマスクした表層形を返す
		dstがTrueの場合は最左の名詞をマスクした以降は切り捨てて返す

		戻り値：
		名詞をマスクした表層形
		'''
		result = ''
		for morph in self.morphs:
			if morph.pos != '記号':
				if morph.pos == '名詞':
					result += mask
					if dst:
						return result
					mask = ''		# 最初に見つけた名詞をマスク、以降の名詞は除去
				else:
					result += morph.surface
		return result


def neco_lines():
	'''「吾輩は猫である」の係り受け解析結果のジェネレータ
	「吾輩は猫である」の係り受け解析結果を順次読み込んで、
	1文ずつChunkクラスのリストを返す

	戻り値：
	1文のChunkクラスのリスト
	'''
	with open(fname_parsed) as file_parsed:

		chunks = dict()		# idxをkeyにChunkを格納
		idx = -1

		for line in file_parsed:

			# 1文の終了判定
			if line == 'EOS\n':

				# Chunkのリストを返す
				if len(chunks) > 0:

					# chunksをkeyでソートし、valueのみ取り出し
					sorted_tuple = sorted(chunks.items(), key=lambda x: x[0])
					yield list(zip(*sorted_tuple))[1]
					chunks.clear()

				else:
					yield []

			# 先頭が*の行は係り受け解析結果なので、Chunkを作成
			elif line[0] == '*':

				# Chunkのインデックス番号と係り先のインデックス番号取得
				cols = line.split(' ')
				idx = int(cols[1])
				dst = int(re.search(r'(.*?)D', cols[2]).group(1))

				# Chunkを生成（なければ）し、係り先のインデックス番号セット
				if idx not in chunks:
					chunks[idx] = Chunk()
				chunks[idx].dst = dst

				# 係り先のChunkを生成（なければ）し、係り元インデックス番号追加
				if dst != -1:
					if dst not in chunks:
						chunks[dst] = Chunk()
					chunks[dst].srcs.append(idx)

			# それ以外の行は形態素解析結果なので、Morphを作りChunkに追加
			else:

				# 表層形はtab区切り、それ以外は','区切りでバラす
				cols = line.split('\t')
				res_cols = cols[1].split(',')

				# Morph作成、リストに追加
				chunks[idx].morphs.append(
					Morph(
						cols[0],		# surface
						res_cols[6],	# base
						res_cols[0],	# pos
						res_cols[1]		# pos1
					)
				)

		raise StopIteration


# 係り受け解析
parse_neko()

# 結果ファイル作成
with open(fname_result, mode='w') as out_file:

	# 1文ずつリスト作成
	for chunks in neco_lines():

		# 名詞を含むchunkに限定した、chunksにおけるインデックスのリストを作成
		indexs_noun = [i for i in range(len(chunks))
				if len(chunks[i].get_morphs_by_pos('名詞')) > 0]

		# 2つ以上ある？
		if len(indexs_noun) < 2:
			continue

		# 名詞を含むchunkの組み合わせを総当りでチェック
		for i, index_x in enumerate(indexs_noun[:-1]):
			for index_y in indexs_noun[i + 1:]:

				meet_y = False			# Yにぶつかった？
				index_dup = -1			# XとYの経路がぶつかったchunkのindex
				routes_x = set()		# Xの経路チェック用

				# 名詞Xから根に向かって、Yにぶつからないか調べながら探索
				dst = chunks[index_x].dst
				while dst != -1:
					if dst == index_y:
						meet_y = True			# Yにぶつかった
						break
					routes_x.add(dst)			# 経路チェックのために保存
					dst = chunks[dst].dst

				# 名詞Yから根まで、Xの経路にぶつからないか調べながら探索
				if not meet_y:
					dst = chunks[index_y].dst
					while dst != -1:
						if dst in routes_x:
							index_dup = dst		# Xの経路とぶつかった
							break
						else:
							dst = chunks[dst].dst

				# 結果出力
				if index_dup == -1:

					# XからYにぶつかるパターン
					out_file.write(chunks[index_x].noun_masked_surface('X'))
					dst = chunks[index_x].dst
					while dst != -1:
						if dst == index_y:
							out_file.write(
									' -> ' + chunks[dst].noun_masked_surface('Y', True))
							break
						else:
							out_file.write(
									' -> ' + chunks[dst].normalized_surface())
						dst = chunks[dst].dst
					out_file.write('\n')

				else:

					# 経路上の共通のchunkでぶつかるパターン

					# Xからぶつかる手前までを出力
					out_file.write(chunks[index_x].noun_masked_surface('X'))
					dst = chunks[index_x].dst
					while dst != index_dup:
						out_file.write(' -> ' + chunks[dst].normalized_surface())
						dst = chunks[dst].dst
					out_file.write(' | ')

					# Yからぶつかる手前までを出力
					out_file.write(chunks[index_y].noun_masked_surface('Y'))
					dst = chunks[index_y].dst
					while dst != index_dup:
						out_file.write(' -> ' + chunks[dst].normalized_surface())
						dst = chunks[dst].dst
					out_file.write(' | ')

					# ぶつかったchunkを出力
					out_file.write(chunks[index_dup].normalized_surface())
					out_file.write('\n')
```

####実行結果：

以下、結果の先頭部分です。

```console:result.txt（先頭部分）
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を | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y
Xは | Yという -> 人間中で | 種族であったそうだ
Xは | YYで | 種族であったそうだ
Xは | Y -> 獰悪な | 種族であったそうだ
Xは | Yな | 種族であったそうだ
Xは -> Y
Xという -> Y
Xという -> 人間中で | Y -> 獰悪な | 種族であったそうだ
Xという -> 人間中で | Yな | 種族であったそうだ
Xという -> 人間中で -> Y
XXで | Y -> 獰悪な | 種族であったそうだ
XXで | Yな | 種族であったそうだ
XXで -> Y
X -> Y
X -> 獰悪な -> Y
Xな -> Y
```

結果全体は[GitHub](https://github.com/segavvy/nlp100_Python/tree/master/49)にアップしています。

###問題の意味

Chunkクラスに`noun_masked_surface()`を追加しました。文節の中の名詞をマスクした表層形を取得するためのものです。それ以外のクラスや関数は[前問](http://qiita.com/segavvy/items/ed5cc48dc02afd8855a1)のままです。

*i* とか *j* とか出てきてややこしいですが、文中の名詞2つの組み合わせを総当たりして、位置関係を[前問](http://qiita.com/segavvy/items/ed5cc48dc02afd8855a1)のようなパスで出力しなさい、という問題です。

たとえば問題文で例として使われている「吾輩はここで始めて人間というものを見た。」の場合、名詞を含む文節は、次の丸を付けた4つです。

![Kobito.pCyt3d.png](https://qiita-image-store.s3.amazonaws.com/0/139624/bd705163-ea8f-24e6-e477-6a0e9b13c04f.png "Kobito.pCyt3d.png")

この4つの文節をペアにする組み合わせは6通りあるため、6行のパスを出力します。

まず最初に注目するペアは最初に出てくる「吾輩」と「ここ」の2つです。文節番号の若い *i* がXになるので、XとYは次のようになります。

![Kobito.PnWWVz.png](https://qiita-image-store.s3.amazonaws.com/0/139624/cc288495-ae26-2784-5d45-923cbd07d90c.png "Kobito.PnWWVz.png")

この2つは「見た」でぶつかるので、それぞれから「見た」の手前までのパスと「見た」そのものを`|`で区切ってを出力します。その際に注目している名詞は「X」と「Y」に置換します。

```console
Xは | Yで -> 始めて -> 人間という -> ものを | 見た
```

続いてXはそのまま、Yを次のものにずらします。

![Kobito.jEEkoS.png](https://qiita-image-store.s3.amazonaws.com/0/139624/dc5be30a-6e86-c871-fb55-c355bae076da.png "Kobito.jEEkoS.png")

```console
Xは | Yという -> ものを | 見た
```

同じように次にいきます。

![Kobito.P2xScu.png](https://qiita-image-store.s3.amazonaws.com/0/139624/9ac17dc0-f0d5-6f47-511b-6abfdd082fc3.png "Kobito.P2xScu.png")

```console
Xは | Yを | 見た
```

「吾輩」を起点にしたペアはもうないので、Xを「ここ」にずらします。

![Kobito.TAFyI8.png](https://qiita-image-store.s3.amazonaws.com/0/139624/d7b3d781-3cc9-99c0-c3bf-4012e7ebbef5.png "Kobito.TAFyI8.png")

今度はパスの途中でYにぶつかります。途中でぶつかった場合はそこまでのパスを表示して終わりです。なお、問題文の例を見ると、Y側はその名詞より後の形態素は表示しないようなので、Yの文節を表示する際は名詞より後を省略します。Chunkクラスに追加した`noun_masked_surface()`関数の引数dstは、名詞より後ろを省略するためのものです。

```console
Xで -> 始めて -> Y
```

あとはこれを繰り返すだけです。

![Kobito.4ZMRqP.png](https://qiita-image-store.s3.amazonaws.com/0/139624/06035948-d2c2-7c30-1237-3f0e5a7439ac.png "Kobito.4ZMRqP.png")

```console
Xで -> 始めて -> 人間という -> Y
```

「ここ」を起点にしたペアはもうないので、Xをずらします。

![Kobito.ubNUEE.png](https://qiita-image-store.s3.amazonaws.com/0/139624/d1e65bcc-085b-afa9-3c68-ef143ba6c22b.png "Kobito.ubNUEE.png")

```console
Xという -> Y
```

最初は問題の意味がわからず苦戦しましたが、分かってしまえばなんとかなります。

###文節内に名詞が複数ある場合

文節内に名詞が複数ある場合ですが、とりあえず今回は最初に見つけた名詞のみXやYに置換し、それ以降の名詞は除去するようなコードにしました。ちょっとやっつけですが、名詞が続く部分は1つのXやYに置換されるので、なんとなくいい感じになるかと思います。

　
50本目のノックは以上です。誤りなどありましたら、ご指摘いただけますと幸いです。
<hr>

*実行結果には、[100本ノックで用いるコーパス・データ](http://www.cl.ecei.tohoku.ac.jp/nlp100/#data)で配布されているデータの一部が含まれます。この第5章で用いているデータは[青空文庫](http://www.aozora.gr.jp)で公開されている夏目漱石の長編小説『吾輩は猫である』が元になっています。*