2016-09-19

『言語処理 100 本ノック』に PHP で挑戦しています。今回は問題 48 と問題 49 を解いて第 5 章を終えます。
www.cl.ecei.tohoku.ac.jp

48. 名詞から根へのパスの抽出

文中のすべての名詞を含む文節に対し，その文節から構文木の根に至るパスを抽出せよ．ただし，構文木上のパスは以下の仕様を満たすものとする．

各文節は（表層形の）形態素列で表現する

パスの開始文節から終了文節に至るまで，各文節の表現を"->"で連結する

「吾輩はここで始めて人間というものを見た」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．
吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た

問題 46, 問題 47 で Term クラスを導入したのと同様に、ここでは Path クラスを導入してパスを表現しました。chunks フィールドは、コンストラクタに渡された Chunk インスタンスから dst フィールドを辿って得られるパスを配列として保持します。パスの長さを取得する length メソッドと、パスに含まれる各文節を "->" で連結した文字列を取得するメソッドを作成しました。

<?php
require_once __DIR__ . '/Chunk.php';

class Path
{
    public $chunks;

    public function __construct($chunk)
    {
        $this->chunks = self::initChunks($chunk);
    }

    private static function initChunks($chunk)
    {
        $chunks = [];
        for ($c = $chunk; $c != null; $c = $c->dst) {
            $chunks[] = $c;
        }
        return $chunks;
    }

    public function length()
    {
        return count($this->chunks);
    }

    public function surface()
    {
        return implode(' -> ', array_map(function ($chunk) {
            return $chunk->surface();
        }, $this->chunks));
    }
}

Path クラスを利用して、問題を解くプログラムを次のように実装しました。文節が名詞を含むとき、そこからのパスを作成して出力します。問題文には明記されていませんが、パスの長さが 1 の場合は係り受けにならないので出力から除外しました。

<?php
require_once __DIR__ . '/Path.php';
require_once __DIR__ . '/read_cabocha_data.php';

main();

function main()
{
    $sentences = read_cabocha_data('neko.txt.cabocha');

    foreach ($sentences as $sentence) {
        process_sentence($sentence);
    }
}

function process_sentence($sentence)
{
    foreach ($sentence->chunks as $chunk) {
        process_chunk($chunk);
    }
}

function process_chunk($chunk)
{
    if (!$chunk->has('名詞')) {
        return;
    }

    $path = new Path($chunk);
    if ($path->length() > 1) {
        echo $path->surface(), "\n";
    }
}

実行結果の最初の 15 行は次のとおりです。9 行目から 12 行目までが、問題文に例示されている出力と一致しています。

吾輩は -> 猫である
名前は -> 無い
どこで -> 生れたか -> つかぬ
見当が -> つかぬ
何でも -> 薄暗い -> 所で -> 泣いて -> 記憶している
所で -> 泣いて -> 記憶している
ニャーニャー -> 泣いて -> 記憶している
いた事だけは -> 記憶している
吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た
あとで -> 聞くと -> 種族であったそうだ
それは -> 種族であったそうだ
書生という -> 人間中で -> 種族であったそうだ

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

問題文では名詞句の定義が明確ではないのですが、ここでは、文節の先頭から一つ以上連続する名詞と考えます。まず Chunk クラスに、文節から名詞句を取得するメソッドを追加します。名詞句でない場合には false を戻すようにします。

<?php
...

    public function nounPhrase()
    {
        $phrase = '';
        foreach ($this->morphs as $morph) {
            if (!$morph->is('名詞')) {
                break;
            }
            $phrase .= $morph->surface;
        }
        return $phrase ?: false;
    }

また、Path クラスにもメソッドを追加します。intersect は二つのパスが交わる文節を取得するメソッド、search は与えられた文節のインデックスを取得するもの、slice はオフセットと長さを指定してパスの一部を取得するものです。

<?php
...

    public static function intersect($path1, $path2)
    {
        $chunk = false;
        $i1 = $path1->length();
        $i2 = $path2->length();
        while ($i1 > 0 && $i2 > 0) {
            if (($c = $path1->chunks[--$i1]) !== $path2->chunks[--$i2]) {
                break;
            }
            $chunk = $c;
        }
        return $chunk;
    }

    public function search($chunk)
    {
        return array_search($chunk, $this->chunks, true);
    }

    public function slice($offset, $length = null)
    {
        $chunks = array_slice($this->chunks, $offset, $length);
        return self::fromChunks($chunks);
    }

    private static function fromChunks($chunks)
    {
        $path = new Path(null);
        $path->chunks = $chunks;
        return $path;
    }

問題を解くプログラムは次のように実装しました。process_sentence では、まず collect_paths で、名詞句から始まるすべてのパスを集めます。次に process_paths で、集められたパスの全ての組み合わせについて、最短係り受けパスを順に出力します。process_path_pair 関数では、まず二つのパスが交わる文節を求めて、それぞれをその文節の直前までに切り詰めます。この処理によって $latter の長さが 0 になれば問題文の前者の形状、$latter の長さが 1 以上であれば問題文の後者の形状ということになります。それぞれの形状に合わせて結果を出力します。

<?php
require_once __DIR__ . '/Path.php';
require_once __DIR__ . '/read_cabocha_data.php';

main();

function main()
{
    $sentences = read_cabocha_data('neko.txt.cabocha');

    foreach ($sentences as $sentence) {
        process_sentence($sentence);
    }
}

function process_sentence($sentence)
{
    $paths = collect_paths($sentence);
    process_paths($paths);
}

function collect_paths($sentence)
{
    $paths = [];
    foreach ($sentence->chunks as $chunk) {
        if (($path = process_chunk($chunk)) !== false) {
            $paths[] = $path;
        }
    }
    return $paths;
}

function process_chunk($chunk)
{
    return $chunk->nounPhrase() !== false ? new Path($chunk) : false;
}

function process_paths($paths)
{
    $n = count($paths);
    for ($i = 0; $i < $n; ++$i) {
        for ($j = $i + 1; $j < $n; ++$j) {
            process_path_pair($paths[$i], $paths[$j]);
        }
    }
}

function process_path_pair($former, $latter)
{
    $intersect = Path::intersect($former, $latter);
    $former = $former->slice(0, $former->search($intersect));
    $latter = $latter->slice(0, $latter->search($intersect));

    if ($latter->length() == 0) {
        echo replace_surface($former, 'X'), " -> Y\n";
    } else {
        echo implode(' | ', [
            replace_surface($former, 'X'),
            replace_surface($latter, 'Y'),
            $intersect->surface()
        ]), "\n";
    }
}

function replace_surface($path, $replace)
{
    if ($path->length() == 0) {
        return '';
    }

    $phrase = $path->chunks[0]->nounPhrase();
    return $replace . substr($path->surface(), strlen($phrase));
}

実行結果の一部を抜粋します*1。2 行目から 7 行目が問題文に例示されている出力と一致しています。

Xだけは -> Y
Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y
Xで -> 聞くと | Yは | 種族であったそうだ
Xで -> 聞くと | Yという -> 人間中で | 種族であったそうだ
Xで -> 聞くと | Yで | 種族であったそうだ

*1:正確には、11 行目から 20 行目を出力しています。

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

『言語処理 100 本ノック』に PHP で挑む (問題 48 ~ 49)

48. 名詞から根へのパスの抽出

49. 名詞間の係り受けパスの抽出