LoginSignup
1
4

More than 3 years have passed since last update.

@FukuharaYohei(Fukuhara)

言語処理100本ノック-49:名詞間の係り受けパスの抽出

Posted at

言語処理100本ノック 2015「第5章: 係り受け解析」の49本目「名詞間の係り受けパスの抽出」記録です。
ついに100本ノックの折り返し地点です。ここで鬼門となる凶悪なノックです。問題がわかりにくく、理解したとしても解くのが面倒くさい。100本終えて感じますが、自分で組むアルゴリズムとしては最も面倒なノックです(他にもより複雑なものはあるが、基本的にパッケージに任せているのでそんなに苦労しなません)。

参考リンク

リンク 備考
049.名詞間の係り受けパスの抽出.ipynb 回答プログラムのGitHubリンク
素人の言語処理100本ノック:49 多くのソース部分のコピペ元
CaboCha公式 最初に見ておくCaboChaのページ

環境

CRF++とCaboChaはインストールしたのが昔すぎてインストール方法忘れました。全然更新されていないパッケージなので、環境再構築もしていません。CaboChaをWindowsで使おうと思い、挫折した記憶だけはあります。確か64bitのWindowsで使えなかった気がします(記憶が曖昧だし私の技術力の問題も多分にあるかも)。

種類 バージョン 内容
OS Ubuntu18.04.01 LTS 仮想で動かしています
pyenv 1.2.16 複数Python環境を使うことがあるのでpyenv使っています
Python 3.8.1 pyenv上でpython3.8.1を使っています
パッケージはvenvを使って管理しています
Mecab 0.996-5 apt-getでインストール
CRF++ 0.58 昔すぎてインストール方法忘れました(多分make install)
CaboCha 0.69 昔すぎてインストール方法忘れました(多分make install)

第5章: 係り受け解析

学習内容

『吾輩は猫である』に係り受け解析器CaboChaを適用し，係り受け木の操作と統語的な分析を体験します．

クラス, 係り受け解析, CaboCha, 文節, 係り受け, 格, 機能動詞構文, 係り受けパス, Graphviz

ノック内容

夏目漱石の小説『吾輩は猫である』の文章（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

課題補足

ノック内容が長くて理解し難い。記事「素人の言語処理100本ノック:49」を見てようやく理解しました。私の解説は省略します・・・

回答

回答プログラム 049.名詞間の係り受けパスの抽出.ipynb

150行ありますね・・・ 時間かければもう少しシンプルにできそうですが、心折れています。

import re

# 区切り文字
separator = re.compile('\t|,')

# 係り受け
dependancy = re.compile(r'''(?:\*\s\d+\s) # キャプチャ対象外
                            (-?\d+)       # 数字(係り先)
                          ''', re.VERBOSE)
NOUN_REPLACE = '@@noun@@'
SEP1 = ' -> '
SEP2 = ' | '

class Morph:
    def __init__(self, line):

        #タブとカンマで分割
        cols = separator.split(line)

        self.surface = cols[0] # 表層形(surface)
        self.base = cols[7]    # 基本形(base)
        self.pos = cols[1]     # 品詞(pos)
        self.pos1 = cols[2]    # 品詞細分類1(pos1)

class Chunk:
    def __init__(self, morphs, dst):
        self.morphs = morphs
        self.dst  = dst  # 係り先文節インデックス番号
        self.dsts = []

        self.phrase = ''
        self.phrase_noun = ''
        self.noun = False

        for morph in morphs:
            if morph.pos != '記号':
                self.phrase += morph.surface # 記号以外の場合文節作成
                if morph.pos == '名詞':

                    # 初めての名詞の場合、名詞句として扱う
                    if self.noun == False:
                        self.noun = True
                        self.phrase_noun += NOUN_REPLACE
                        continue

                    # ひとつ前が名詞で対象だった場合は表層系を置き換えない
                    elif self.noun and self.phrase_noun.endswith(NOUN_REPLACE):
                        continue

                # 置換やスキップ以外の場合は、そのまま表層系を追加
                self.phrase_noun += morph.surface

morphs = []
chunks = []
sentences = []

with open('./neko.txt.cabocha') as f:

    for line in f:
        dependancies = dependancy.match(line)

        # EOSまたは係り受け解析結果でない場合
        if not (line == 'EOS\n' or dependancies):
            morphs.append(Morph(line))

        # EOSまたは係り受け解析結果で、形態素解析結果がある場合
        elif len(morphs) > 0:
            chunks.append(Chunk(morphs, dst))
            morphs = []

        # 係り受け結果の場合
        if dependancies:
            dst = int(dependancies.group(1))

        # EOSで係り受け結果がある場合
        if line == 'EOS\n' and len(chunks) > 0:

            # 係り先を追加していく(効率化のため最終行か追加していく)
            for chunk in chunks[::-1]:
                if chunk.dst!= -1:
                    chunk.dsts.extend([chunk.dst])
                    if chunks[chunk.dst].dst != -1:
                        chunk.dsts.extend(chunks[chunk.dst].dsts)
            sentences.append(chunks)
            chunks = []

def output_result(i, chunk, sentence):
    print('\tX:', i, chunk.phrase, chunk.dsts)

    # 名詞句(X)の次からYを探索するループ
    for i_y, y_chunk in enumerate(sentence[i+1:], i+1):

        # 名詞句の場合Yとする
        if y_chunk.noun:

            # Yの情報出力
            print('\t\tY:', i_y, y_chunk.phrase)

            result = ''

            # Yが経路(係り先)に含まれる場合
            if i_y in chunk.dsts:

                result = '\t\t\tP1:' + '\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X') + SEP1

                # XからYまでを出力
                for i_path in chunk.dsts:

                    # Yに到達したら終了
                    if i_path == i_y:
                        result += 'Y'
                        break
                    else:
                        result += sentence[i_path].phrase + SEP1

            # Yが経路(係り先)に含まれない場合
            else:
                result = '\t\t\tP2:' + '\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X')

                # 積集合での最小値で共通の文節を求める
                i_goal = min(set(chunk.dsts).intersection(set(sentence[i_y].dsts)))

                # Xから共通文節の前、Yまで
                for i_path in chunk.dsts:                    
                    if i_path == i_goal:
                        result += SEP2 + sentence[i_y].phrase_noun.replace(NOUN_REPLACE, 'Y')
                        break
                    else:
                        result += SEP1 + sentence[i_path].phrase                 

                # Yの係り先から共通文節まで
                for i_path in sentence[i_y].dsts:
                    if i_path == i_goal:
                        result += SEP2 + sentence[i_goal].phrase
                    else:
                        result += SEP1 + sentence[i_path].phrase
            print(result)

for i_sentence, sentence in enumerate(sentences):

    # 文出力
    print(i_sentence, '\t', ''.join([chunk.phrase for chunk in sentence]))
    for i_chunk, chunk in enumerate(sentence):

        # 文節が名詞句の場合
        if chunk.noun and chunk.dst != -1:
            output_result(i_chunk, chunk, sentence)

    # 多いので制限
    if i_sentence > 5:
        break

回答解説

Chunkクラス

まずはChunkクラスを大幅に拡大しています。
名詞だった場合にフラグnounをTrueに設定します。
そして「Xは」や「Yは」となるようにphrase_nounを作ります。ここの時点ではXともYともなり得るので、固定値NOUN_REPLACEをXやYの部分に入れています。また、名詞が連続した場合(例：鳩+時計)を考慮してendswithで末尾がNOUN_REPLACEになっていないかを見ています(NOUN_REPLACEが連続しないようにする)。

class Chunk:
    def __init__(self, morphs, dst):
        self.morphs = morphs
        self.dst  = dst  # 係り先文節インデックス番号
        self.dsts = []

        self.phrase = ''
        self.phrase_noun = ''
        self.noun = False

        for morph in morphs:
            if morph.pos != '記号':
                self.phrase += morph.surface # 記号以外の場合文節作成
                if morph.pos == '名詞':

                    # 初めての名詞の場合、名詞句として扱う
                    if self.noun == False:
                        self.noun = True
                        self.phrase_noun += NOUN_REPLACE
                        continue

                    # ひとつ前が名詞で対象だった場合は表層系を置き換えない
                    elif self.noun and self.phrase_noun.endswith(NOUN_REPLACE):
                        continue

                # 置換やスキップ以外の場合は、そのまま表層系を追加
                self.phrase_noun += morph.surface

ファイル読込ループ部分

前回から変化があるのは最後のif条件分岐「EOSで係り受け結果がある場合」の部分です。
文節の集合chunksをループして全係り先のリストを作成します。最終行から逆にループしているのは、全係り先を1回で作成したく、1度作成した係り先リストを再利用するためです。

for line in f:
    dependancies = dependancy.match(line)

    # EOSまたは係り受け解析結果でない場合
    if not (line == 'EOS\n' or dependancies):
        morphs.append(Morph(line))

    # EOSまたは係り受け解析結果で、形態素解析結果がある場合
    elif len(morphs) > 0:
        chunks.append(Chunk(morphs, dst))
        morphs = []

    # 係り受け結果の場合
    if dependancies:
        dst = int(dependancies.group(1))

    # EOSで係り受け結果がある場合
    if line == 'EOS\n' and len(chunks) > 0:

        # 係り先を追加していく(効率化のため最終行から追加していく)
        for chunk in chunks[::-1]:
            if chunk.dst!= -1:
                chunk.dsts.extend([chunk.dst])
                if chunks[chunk.dst].dst != -1:
                    chunk.dsts.extend(chunks[chunk.dst].dsts)
        sentences.append(chunks)
        chunks = []

出力部

後でチェックがしやすいように、課題の指示に含まれてはいませんが文全体、X、Yの情報をインデントして出力しています。
今回の出力は、以下の2パターンに大別できます。

  • パターン1：XとYが同じ経路：Yは文節全体を置き換え ->出力時にP1とする
  • パターン2: XとYが別経路：|で区切る、Yは名詞部分のみの置き換え ->出力時にP2とする

パターン1の場合は、XとYが同じ経路なのでXからYまでを順に出力します。
パターン2の場合は、XとYが別経路なので複雑です。XとYの共有的な終端を求めるためにintersection関数を使っています。「第1章の6本目でやった内容」ですね。

def output_result(i, chunk, sentence):
    print('\tX:', i, chunk.phrase, chunk.dsts)

    # 名詞句(X)の次からYを探索するループ
    for i_y, y_chunk in enumerate(sentence[i+1:], i+1):

        # 名詞句の場合Yとする
        if y_chunk.noun:

            # Yの情報出力
            print('\t\tY:', i_y, y_chunk.phrase)

            result = ''

            # Yが経路(係り先)に含まれる場合
            if i_y in chunk.dsts:

                result = '\t\t\tP1:' + '\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X') + SEP1

                # XからYまでを出力
                for i_path in chunk.dsts:

                    # Yに到達したら終了
                    if i_path == i_y:
                        result += 'Y'
                        break
                    else:
                        result += sentence[i_path].phrase + SEP1

            # Yが経路(係り先)に含まれない場合
            else:
                result = '\t\t\tP2:' + '\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X')

                # 積集合での最小値で共通の文節を求める
                i_goal = min(set(chunk.dsts).intersection(set(sentence[i_y].dsts)))

                # Xから共通文節の前、Yまで
                for i_path in chunk.dsts:                    
                    if i_path == i_goal:
                        result += SEP2 + sentence[i_y].phrase_noun.replace(NOUN_REPLACE, 'Y')
                        break
                    else:
                        result += SEP1 + sentence[i_path].phrase                 

                # Yの係り先から共通文節まで
                for i_path in sentence[i_y].dsts:
                    if i_path == i_goal:
                        result += SEP2 + sentence[i_goal].phrase
                    else:
                        result += SEP1 + sentence[i_path].phrase
            print(result)

出力結果(実行結果)

プログラム実行すると以下の結果が出力されます。多分あっているはず。あまりチェックしていません。

出力結果
0    一
1    吾輩は猫である
2    名前はまだ無い
    X: 0 名前は [2]
3    どこで生れたかとんと見当がつかぬ
    X: 0 どこで [1, 2, 4]
        Y: 2 かとんと
            P1: Xで -> 生れた -> Y
        Y: 3 見当が
            P2: Xで -> 生れた -> かとんと | Yが | つかぬ
    X: 2 かとんと [4]
        Y: 3 見当が
            P2: Xと | Yが | つかぬ
    X: 3 見当が [4]
4    何でも薄暗いじめじめした所でニャーニャー泣いていた事だけは記憶している
    X: 0 何でも [1, 5, 7]
        Y: 3 した所で
            P2: Xでも -> 薄暗い | Yで | 泣いて -> 記憶している
        Y: 6 いた事だけは
            P2: Xでも -> 薄暗い -> 泣いて | Yだけは | 記憶している
        Y: 7 記憶している
            P1: Xでも -> 薄暗い -> 泣いて -> Y
    X: 3 した所で [5, 7]
        Y: 6 いた事だけは
            P2: Xで -> 泣いて | Yだけは | 記憶している
        Y: 7 記憶している
            P1: Xで -> 泣いて -> Y
    X: 6 いた事だけは [7]
        Y: 7 記憶している
            P1: Xだけは -> Y
5    吾輩はここで始めて人間というものを見た
    X: 0 吾輩は [5]
        Y: 1 ここで
            P2: Xは | Yで -> 始めて -> 人間という -> ものを | 見た
        Y: 3 人間という
            P2: Xは | Yという -> ものを | 見た
        Y: 4 ものを
            P2: Xは | Yを | 見た
    X: 1 ここで [2, 3, 4, 5]
        Y: 3 人間という
            P1: Xで -> 始めて -> Y
        Y: 4 ものを
            P1: Xで -> 始めて -> 人間という -> Y
    X: 3 人間という [4, 5]
        Y: 4 ものを
            P1: Xという -> Y
    X: 4 ものを [5]
6    しかもあとで聞くとそれは書生という人間中で一番獰悪な種族であったそうだ
    X: 1 あとで [2, 9]
        Y: 3 それは
            P2: Xで -> 聞くと | Yは | そうだ
        Y: 4 書生という
            P2: Xで -> 聞くと | Yという -> 人間中で -> 種族であった | そうだ
        Y: 5 人間中で
            P2: Xで -> 聞くと | Yで -> 種族であった | そうだ
        Y: 6 一番
            P2: Xで -> 聞くと | Y -> 獰悪な -> 種族であった | そうだ
        Y: 7 獰悪な
            P2: Xで -> 聞くと | Yな -> 種族であった | そうだ
        Y: 8 種族であった
            P2: Xで -> 聞くと | Yであった | そうだ
        Y: 9 そうだ
            P1: Xで -> 聞くと -> Y
    X: 3 それは [9]
        Y: 4 書生という
            P2: Xは | Yという -> 人間中で -> 種族であった | そうだ
        Y: 5 人間中で
            P2: Xは | Yで -> 種族であった | そうだ
        Y: 6 一番
            P2: Xは | Y -> 獰悪な -> 種族であった | そうだ
        Y: 7 獰悪な
            P2: Xは | Yな -> 種族であった | そうだ
        Y: 8 種族であった
            P2: Xは | Yであった | そうだ
        Y: 9 そうだ
            P1: Xは -> Y
    X: 4 書生という [5, 8, 9]
        Y: 5 人間中で
            P1: Xという -> Y
        Y: 6 一番
            P2: Xという -> 人間中で | Y -> 獰悪な | 種族であった -> そうだ
        Y: 7 獰悪な
            P2: Xという -> 人間中で | Yな | 種族であった -> そうだ
        Y: 8 種族であった
            P1: Xという -> 人間中で -> Y
        Y: 9 そうだ
            P1: Xという -> 人間中で -> 種族であった -> Y
    X: 5 人間中で [8, 9]
        Y: 6 一番
            P2: Xで | Y -> 獰悪な | 種族であった -> そうだ
        Y: 7 獰悪な
            P2: Xで | Yな | 種族であった -> そうだ
        Y: 8 種族であった
            P1: Xで -> Y
        Y: 9 そうだ
            P1: Xで -> 種族であった -> Y
    X: 6 一番 [7, 8, 9]
        Y: 7 獰悪な
            P1: X -> Y
        Y: 8 種族であった
            P1: X -> 獰悪な -> Y
        Y: 9 そうだ
            P1: X -> 獰悪な -> 種族であった -> Y
    X: 7 獰悪な [8, 9]
        Y: 8 種族であった
            P1: Xな -> Y
        Y: 9 そうだ
            P1: Xな -> 種族であった -> Y
    X: 8 種族であった [9]
        Y: 9 そうだ
            P1: Xであった -> Y
1
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
4