2018年06月07日

言語処理100本ノックでPython入門 #49 - 名詞間の係り受けパスの抽出

  

今日は、言語処理100本ノック 2015の問題49です。
「第5章:係り受け解析」最後の問題になりました。

まだ、Pythonの文法で知らないことも結構あると思いますが、それなりのコードは書けるようになったかなと思います。やりたいアルゴリズムを実装する上で、困ることはほとんどなくなったように思います。あとはいろんなライブラリの使い方を覚えて行ければ...

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

■ 新たに得たPythonの知識

Python はメソッドのオーバーロードが使えない。

intの最大値
import sys
sys.maxsize

深いコピーができる
import copy

copy.deepcopy(x)

■ 簡単な説明

Chunkクラスには、hasNounメソッドを追加。

analyze関数は今回は変更。 EOSを明確に示すために、sentenseの最後には、Chunk(sys.maxsize, -1) を追加しました。これがEOSを意味します。
 sentence.append(Chunk(sys.maxsize, -1))
これに伴い、これまでは、dst:-1の時は、次のChunkはないことを示していましたが、最後のChunkのdstは、EOSを表すChunkへの番号をセットするようにしました。
    if destNo == -1:
        destNo = num + 1
各関数の動作については、コードにコメントを付けたのでそれを読んでください。
なお、主要な変数は以下の通りです。
  • 変数ciは、文節i(Chunkクラス) を表す
  • 変数cjは、文節j(Chunkクラス) を表す
  • 変数ckは、文節k(Chunkクラス) を表す
  • 変数kは、文節kのインデックスを表す (sentenceのインデックス) 

ただ、あまり効率の良いコードとは言えないです。改良の余地hじゃありますが、まあ良しとします。


■ Pythonのコード
import re
import sys
import copy
import functools

# 形態素を表すクラス
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1

    def toList(self):
        return [self.surface, self.base, self.pos, self.pos1]

# 文節を表すクラス (複数の形態素からなる)
class Chunk:
    def __init__(self, number, dst):
        self.number = number
        self.morphs = []
        self.dst = dst
        self.srcs = []

    def hasNoun(self):
        for m in self.morphs:
            if m.pos == '名詞':
                return True
        return False

    def concatMorphs(self):
        seq = filter(lambda x: x.pos != '記号', self.morphs)
        return functools.reduce(lambda x, y: x + y.surface, seq, '')

# 文章をsentenceに分割する。ひとつのsentenceは、Chunk(文節)の配列からなる
def analyze():
    article = []
    sentence = []
    chunk = None
    with open('neko.txt.cabocha', 'r', encoding='utf8') as fin:
        for line in fin:
            words = re.split(r'\t|,|\n| ', line)
            if line[0] == '*':
                num = int(words[1])
                destNo = int(words[2].rstrip('D'))
                if destNo == -1:
                    destNo = num + 1
                chunk = Chunk(num, destNo)
                sentence.append(chunk)
            elif words[0] == 'EOS':
                if sentence:
                    sentence.append(Chunk(sys.maxsize, -1))
                    for index, c in enumerate(sentence, 0):
                        sentence[c.dst].srcs.append(index)
                    article.append(sentence)
                sentence = []
            else:
                chunk.morphs.append(Morph(
                    words[0],
                    words[7],
                    words[1],
                    words[2],
                ))
    return article

# 名詞句(Chunk)のペアを列挙する
def enumPairs(sentence):
    count = len(sentence)
    for i in range(count):
        for j in range(i+1, count):
            if sentence[i].hasNoun() and sentence[j].hasNoun():
                yield sentence[i], sentence[j]

# ciからのパスの中にcjが含まれているかを調べる
def containsOther(ci, cj, sentence):
    curr = ci
    while curr.dst >= 0:
        if curr == cj:
            return True
        curr = sentence[curr.dst]
    return False

# ciからのパスとcjからのパスが出会う番号を返す
def connectedPoint(ci, cj, sentence):
    k = ci.dst
    while k >= 0:
        curr = cj
        while curr.dst >= 0:
            if curr.number == k:
                return k
            curr = sentence[curr.dst]
        k = sentence[k].dst
    return -1

# chunkの名詞の部分を to で指定した値に変更(オリジナルは変更しない)
def replaceTo(to, chunk):
    dup = copy.deepcopy(chunk)
    for m in dup.morphs:
        if m.pos == '名詞':
            m.surface = to
            break
    return dup

# 'Xで -> 始めて -> 人間という -> Y' というパス文字列を生成
def makePath1(ci, cj, sentence):
    path = []
    curr = replaceTo('X', ci)
    while curr.number < cj.number:
        path.append(curr.concatMorphs())
        curr = sentence[curr.dst]
    path.append('Y')
    return '{}'.format(' -> '.join(path))

# 'Xは | Yという -> ものを | 見た' という形式のパス文字列を生成
def makePath2(ci, cj, ck, sentence):
    ci = replaceTo('X', ci)
    cj = replaceTo('Y', cj)
    p1 = ci.concatMorphs()
    list1 = []
    curr = cj
    while curr.number < ck.number:
        list1.append(curr.concatMorphs())
        curr = sentence[curr.dst]
    p2 = '{}'.format(' -> '.join(list1))
    list2 = []
    curr = ck
    while curr.dst > 0:
        list2.append(curr.concatMorphs())
        curr = sentence[curr.dst]
    p3 = '{}'.format(' -> '.join(list2))
    return '{} | {} | {}'.format(p1, p2, p3)

# 1センテンスから、パスを列挙する
def extractPaths(sentence):
    for ci, cj in enumPairs(sentence):
        if containsOther(ci, cj, sentence):
            yield makePath1(ci, cj, sentence)
        else:
            k = connectedPoint(ci, cj, sentence)
            if k > 0:
                yield makePath2(ci, cj, sentence[k], sentence)

# ファイルを読み込み、1センテンス毎に、extractPathsを呼び出し、Path(複数)を取り出し、ファイルに出力
def main():
    article = analyze()
    with open('result49.txt', 'w', encoding='utf8') as w:
        for sentence in article:
            for path in extractPaths(sentence):
                w.write(path + '\n')

if __name__ == '__main__':
    main()

ソースはGitHubでも公開しています。

■ 結果

先頭の10センテンスの結果を掲載します。
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で | 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な -> 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