今回は重めかと思ったけど、やってみたらできないことはなかった。自分比で以前より関数が使えるようになってきた気がする。
言語処理100本ノック #049
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
ノート
…ん？ Xは | Yを | 見た では、
名詞句iが「ものを」で、
名詞句jが無いのでは？と思った。よく分からないぞ？？？ということでちょっと他の人の解答例を見てみたら、「名詞句i：吾輩は」「名詞句j：ものを」となる。
だんだん分かってきた。やることが明確になってきた。まず名詞句のペアを探す。
- j が i -> … -> 構文木の根 の経路上に存在するか確認
- 1で無ければ、共通の文節 k で交わるか確認
- しかるべき形式で表示する
完成
# knock049.py import function_filetochunklist cabochafile = 'neko.txt.cabocha' # 指定した品詞があるかチェック def chkPos(chunk, poslist): for m in chunk.morphs: if m.pos in poslist: return True return False # 文節内の指定した品詞を「X」や「Y」で置き換える # 文節全てではなく、指定した品詞までで止める時は `removetail = 1`とする def getReplaced(chunk, poslist, repstr, removetail): for im, m in enumerate(chunk.morphs): if m.pos in poslist: replaced = '' for jm, mm in enumerate(chunk.morphs): if mm.pos in ['記号', '補助記号', '空白']: pass elif jm == im: replaced += repstr if removetail == 1: return replaced else: replaced += mm.surface return replaced return None # 1. j が i -> … -> 構文木の根 の経路上に存在するか確認、表示を返す def onPath(sentence, I, J): pdst = sentence[I].dst plist = [getReplaced(sentence[I], ['名詞'], 'X', 0)] while pdst > 0: if pdst == J: plist.append(getReplaced(sentence[J], ['名詞'], 'Y', 1)) return ' -> '.join([str(c) for c in plist]) else: plist.append(sentence[pdst].returnmorphs) pdst = sentence[pdst].dst return False # 2の場合の表示を返す def expressIntersect(sentence, I, J, K): idst = sentence[I].dst ilist = [getReplaced(sentence[I], ['名詞'], 'X', 0)] while idst < K: ilist.append(sentence[idst].returnmorphs) idst = sentence[idst].dst jdst = sentence[J].dst jlist = [getReplaced(sentence[J], ['名詞'], 'Y', 0)] while jdst < K: jlist.append(sentence[jdst].returnmorphs) jdst = sentence[jdst].dst kdst = sentence[K].dst klist = [sentence[K]] while kdst > 0: klist.append(sentence[kdst].returnmorphs) kdst = sentence[kdst].dst return ' -> '.join([str(c) for c in ilist]) + \ ' | ' + ' -> '.join([str(c) for c in jlist]) + \ ' | ' + ' -> '.join([str(c) for c in klist]) # 2. 共通の文節 k で交わるか確認、表示を返す def intersect(sentence, I, J): idst = sentence[I].dst ipath_list = [I] while idst > 0: ipath_list.append(idst) idst = sentence[idst].dst jdst = sentence[J].dst while jdst > 0: if jdst in ipath_list: K = jdst return expressIntersect(sentence, I, J, K) jdst = sentence[jdst].dst return False # 名詞句のペアを探し、1か2の形状に該当するか確認、表示を返す def getNN(sentence): if len(sentence) < 0: return False for i, chunki in enumerate(sentence): if chkPos(chunki, ['名詞']) is False: continue for j, chunkj in enumerate(sentence[i+1:]): if chkPos(chunkj, ['名詞']) is False: continue if onPath(sentence, i, i+1+j) is not False: NounNoun = onPath(sentence, i, i+1+j) else: NounNoun = intersect(sentence, i, i+1+j) yield NounNoun # 実行 if __name__ == '__main__': sentences = list(function_filetochunklist.fileToChunkList(cabochafile)) for s in sentences: nnstr_list = list(getNN(s)) if len(nnstr_list) < 1: continue for nnstr in nnstr_list: print(nnstr)
結果
$ python knock049.py >> knock049.txt (18行目、8文目まで) 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
これで、「第5章: 係り受け解析」が終わり。
