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


[言語処理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)からどうぞ。

## 第6章: 英語テキストの処理
>英語のテキスト（nlp.txt）に対して，以下の処理を実行せよ．

###59. S式の解析
>Stanford Core NLPの句構造解析の結果（S式）を読み込み，文中のすべての名詞句（NP）を表示せよ．入れ子になっている名詞句もすべて表示すること．

####出来上がったコード：

```python:main.py
# coding: utf-8
import os
import subprocess
import xml.etree.ElementTree as ET
import re

fname = 'nlp.txt'
fname_parsed = 'nlp.txt.xml'


# タグと内容を抽出するための正規表現
pattern = re.compile(r'''
	^
	\(			# S式の開始カッコ
		(.*?)	# = タグ
		\s		# 空白
		(.*)	# = 内容
	\)			# s式の終わりのカッコ
	$
	''', re.VERBOSE + re.DOTALL)


def parse_nlp():
	'''nlp.txtをStanford Core NLPで解析しxmlファイルへ出力
	すでに結果ファイルが存在する場合は実行しない
	'''
	if not os.path.exists(fname_parsed):

		# StanfordCoreNLP実行、標準エラーはparse.outへ出力
		subprocess.run(
			'java -cp "/usr/local/lib/stanford-corenlp-full-2016-10-31/*"'
			' -Xmx2g'
			' edu.stanford.nlp.pipeline.StanfordCoreNLP'
			' -annotators tokenize,ssplit,pos,lemma,ner,parse,dcoref'
			' -file ' + fname + ' 2>parse.out',
			shell=True,		# shellで実行
			check=True		# エラーチェックあり
		)


def ParseAndExtractNP(str, list_np):
	'''S式をタグと内容に分解し内容のみを返す
	またタグがNPの場合は、内容をlist_npにも追加する
	内容が入れ子になっている場合は、
	その中身も解析して、内容を空白区切りで返す。

	戻り値：
	タグを除いた内容
	'''

	# タグと内容を抽出
	match = pattern.match(str)
	tag = match.group(1)
	value = match.group(2)

	# 内容の解析
	# カッコで入れ子になっている場合は、一番外側を切り出して再帰
	depth = 0		# カッコの深さ
	chunk = ''		# 切り出し中の文字列
	words = []
	for c in value:

		if c == '(':
			chunk += c
			depth += 1		# 深くなった

		elif c == ')':
			chunk += c
			depth -= 1		# 浅くなった
			if depth == 0:
				# 深さが戻ったので、カッコでくくられた部分の切り出し完了
				# 切り出した部分はParseAndExtractNP()に任せる（再帰呼び出し）
				words.append(ParseAndExtractNP(chunk, list_np))
				chunk = ''
		else:
			# カッコでくくられていない部分の空白は無視
			if not (depth == 0 and c == ' '):
				chunk += c

	# 最後の単語を追加
	if chunk != '':
		words.append(chunk)

	# 空白区切りに整形
	result = ' '.join(words)

	# NPならlist_npに追加
	if tag == 'NP':
		list_np.append(result)

	return result


# nlp.txtを解析
parse_nlp()

# 解析結果のxmlをパース
root = ET.parse(fname_parsed)

# sentence列挙、1文ずつ処理
for parse in root.iterfind('./document/sentences/sentence/parse'):
	result = []
	ParseAndExtractNP(parse.text.strip(), result)
	print(*result, sep='\n')
```

####実行結果：

結果の先頭部分です。

```console:先頭部分
Natural language processing
Wikipedia
the free encyclopedia Natural language processing
NLP
the free encyclopedia Natural language processing -LRB- NLP -RRB-
a field
computer science
a field of computer science
artificial intelligence
linguistics
the interactions
computers
human -LRB- natural -RRB- languages
computers and human -LRB- natural -RRB- languages
the interactions between computers and human -LRB- natural -RRB- languages
linguistics concerned with the interactions between computers and human -LRB- natural -RRB- languages
a field of computer science , artificial intelligence , and linguistics concerned with the interactions between computers and human -LRB- natural -RRB- languages
such
NLP
the area
humani-computer interaction
the area of humani-computer interaction
（以下略）
```

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

###句構造解析とは
文章を構成素に分解し、隣接する語句同士の機能的な関係を表そうとする方法論を句構造規則と呼ぶそうです。

例えば「This is a pen.」という英文があった場合、この文（S）は、「This」という名詞句（NP）と、それに続く「is a pen」という動詞句（VP）から構成されます。そしてその名詞句は指定限定子（DT）である「This」で構成され、その動詞句は...といった感じで分析されるようです。

私も解説できるほどは理解できていないので、詳細はウィキペディアの[句構造規則](https://ja.wikipedia.org/wiki/句構造規則)などを参照してください。また、Stanford Core NLPの句構造解析については[ParserAnnotator](http://stanfordnlp.github.io/CoreNLP/parse.html)のところに解説があります。

なお、Stanford Core NLPの句構造解析の結果は、`<parse>`タグにS式で出力されます。

###S式とは
S式とは、2分木またはリスト構造を表現するための記述方式だそうですが、ウィキペディアの[S式](https://ja.wikipedia.org/wiki/S式)の解説を読んでもさっぱり意味が分かりません^^;

実際に試してみたところ、「This is a pen.」の場合、次のような解析結果になりました。なお、Stanford Core NLPの出力結果には改行が入りませんが、見やすいように適当に改行を入れています。

```console:S式のサンプル
(ROOT
	(S
		(NP (DT This))
		(VP (VBZ is) (NP (DT a) (NN pen)))
		(. .)
	)
)
```

前述の句構造解析のところにも書きましたが、文（S）が名詞句（NP）と動詞句（VP）で構成され、その名詞句は指定限定子（DT）である「This」で構成され、その動詞句（VP）は...という感じで解析された結果がこれです。これを見ると、S式の基本は「(タグ 内容1 内容2...)」という形で、内容の部分には、さらに「(タグ 内容1 内容2...)」というのが入れ子にできる記述方式のようです。

今回の問題で求められているのは名詞句（NP）の表示ですので、この例では「This」と「a pen」が出力できれば良さそうです。今回はそのようなコードにしてみました。

`ParseAndExtractNP()`でS式の解析と名詞句の抽出をしています。この関数では、まず正規表現でタグと内容を分離し、内容の部分を解析します。内容の中でカッコが出てきた場合は入れ子になっているため、カッコでくくられた部分を切り出して、さらに`ParseAndExtractNP()`を呼び出すことで解析しています。
カッコでくくられた部分の切り出しは、単純に1文字ずつ見ていって、「(」が出てきたら入れ子の深さを+1し、「)」が出てきたら-1して、深さが0になったら切り出し完了、という流れです。

###再帰呼び出し時の注意
今回の問題ではスタックオーバーフローになるほど再帰が深くならないので余談になりますが、再帰呼び出しの注意についてちょっと書いてみます。

今回のコードは、`ParseAndExtractNP()`の中で、自身の関数`ParseAndExtractNP()`を呼び出す、いわゆる再帰呼び出しになっています。S式の入れ子が深くなるとこの再帰呼び出しも深くなりますが、深くなるとどんどんスタックを消費するので、実行スレッドの生成時に割り当てられているスタックサイズに注意する必要が出てきます。スタックが不足すると、スタックオーバーフローでプログラムが異常終了してしまいます。

Pythonだとこの辺がどうなるのか調べてみたところ、再帰呼び出し数の上限を指定できる[sys.setrecursionlimit()](http://docs.python.jp/3/library/sys.html?highlight=setrecursionlimit#sys.setrecursionlimit)という関数がありました。これは便利ですね。ただ、最適な値は自分で考える必要があるので、[threading.stack_size()](http://docs.python.jp/3/library/threading.html#threading.stack_size)などで指定するスタックサイズと合わせて値を検討する必要があります。

どれくらい再帰するか分からないような場合は、再帰呼び出しをやめるように書き直す（ヒープ上に仮想スタックを作る）のも対策になるでしょう。

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

*実行結果には、[100本ノックで用いるコーパス・データ](http://www.cl.ecei.tohoku.ac.jp/nlp100/#data)で配布されているデータの一部が含まれます。この第6章で用いているデータのライセンスは[クリエイティブ・コモンズ 表示-継承 3.0 非移植](https://creativecommons.org/licenses/by-sa/3.0/legalcode)（[日本語訳](https://creativecommons.org/licenses/by-sa/3.0/deed.ja)）です。*