前回の（1）はこちらから。

Trie木――自然言語処理で使用する代表的なデータ構造

自然言語処理、特に統計学習ベースの自然言語処理においては、機械学習したデータを格納し、利用するためのデータ構造が必要となります。本節では自然言語処理でよく利用されるTrie木というデータ構造について紹介します。

Trie木は接頭辞木とも呼ばれる順序付き木構造の一種で、木構造上のノードの位置とキーが対応します（図1⁠）⁠。図1では、丸が木構造のノードであり、1番上の丸が木のルートです。灰色の丸はキーの終端が存在するノードを表しています。ノード間の線がエッジであり、それぞれのエッジに文字が対応付けられています。Trie木にキーとして「tea」が登録されているか検索する場合は、ルートから探索を開始し「t」に対応するエッジがあればそのエッジの先のノードに遷移します。同様にして「e」「⁠a」に対応するエッジをたどった先のノードが終端（灰色の丸）であればキーが登録されているということがわかります。探索中に文字に対応するエッジが存在しなかったり、末尾の文字に対応するエッジをたどった先のノードが終端でなかった場合は、Trie木にキーが登録されていないということになります。

Trie木の特徴として、

• 格納されているキーの検索が高速
• 共通する接頭辞がまとめられることによる圧縮効果
• 共通する接頭辞を持つキーの列挙が可能

などがあり、単語情報などを格納する辞書用のデータ構造として利用されます。

Trie木を表現する実装には、ダブル配列とLOUDS -Trieがあります。順に解説します。

ダブル配列

ダブル配列はBaseとCheckの2つの配列によってノード間の遷移を表現します。ダブル配列は検索が高速で、データサイズもコンパクトです。BaseとCheck配列は各ノードから次のノードにどの文字で遷移できるかを表現した状態遷移表を、「⁠遷移先のノード番号がどこかという情報」（⁠Base配列）と「遷移先が存在するかどうかという情報」（⁠Check配列）に圧縮したものです。ダブル配列を検索する場合は、次のように計算を行うことでノードの遷移が可能かを確認します。

s：現在の状態番号
t：次の状態番号
c：検索する文字に対応する整数

t = Base[s] + c

このとき、sとCheck[t]が等しければ遷移可能ということになります。検索するキーの先頭から終端まで遷移可能であればキーが存在するということになります。

Perlでダブル配列を利用する場合は、Text::Dartsというモジュールを利用します。Text::DartsはDarts（Double-ARray Trie System）というC++実装のPerlバインディングです。

LOUDS-Trie

Trie 木の別の実装としてLOUDS -Trieがあります。LOUDS（Level-Order Unary Degree Sequence）とは省メモリで木構造を表現するデータ構造で、このLOUDS形式で作成したTrie 木がLOUDS -Trie となります。LOUDS -Trieの検索速度はダブル配列に劣りますが、データサイズはダブル配列よりもコンパクトになります。このため、辞書データをアプリケーションに同梱し、オンメモリで利用するような場合に採用されています。

PerlでLOUDS -Trieを利用する場合は、Text::Tx（txtrie⁠）⁠、Text::Ux（ux-trie）といったモジュールを利用します。

自然言語テキスト解析の基本

本節では、自然言語で書かれたテキストを解析する方法について説明します。

テキスト解析の流れ

日本語テキスト解析を行う流れは、図2のとおりです。解析の目的に応じて各段階の出力を利用します。

形態素解析

形態素解析とは、自然言語文を形態素単位に分割し、品詞などを付与する処理のことです。形態素はその言語における最小単位で、基本的には単語だと思ってよいです。現在利用されている実装の多くは、品詞だけでなく、活用の種類、原形、読みなどの付与を行うようになっています。

形態素解析は後続の処理である係り受け解析のためではなく、単体で利用することもあります。たとえば形態素解析によって入力テキストの読みを取得してテキスト読み上げプログラムに渡したり、表記と品詞の情報に基づいてテキストを書き換えたり、応答を変化させるbotに利用するなどです。

形態素解析のしくみ

ここでは、形態素解析で利用されている手法の1つであるコスト最小法について説明します。コスト最小法では、次のような処理を行います。

• ① 単語の生起コスト（単語の出現確率⁠）⁠、品詞などの情報が格納されている単語辞書を用意する
• ② 単語辞書を利用して、入力文に含まれる単語候補を列挙する
• ③ 列挙した単語を文頭から文末まで並べて、組み合わせた構造（Lattice構造）を作成する（図3）
• ④ Lattice構造の頂点（図3の各ボックス）を通るコストとして、単語の生起コスト（単語の出現確率が高いほど低コスト）を設定する
• ⑤ Lattice構造の辺（図3の各矢印）を通るコストとして、連接コスト（品詞の隣接確率が高いほど低コスト）を設定する
• ⑥ 文頭から文末までの経路で最もコストの低い経路を探索する
• ⑦ 探索した最もコストの低い単語列（図3の太字の列）を出力する

実際の形態素解析器ではこれに加えて、辞書に存在しない単語（未知語）であっても、分割位置を推定できるよう工夫がされています。例としては文字種に基づくヒューリスティック[1]な処理で、アルファベットが連続している場合は連続した範囲を単語とするといった工夫が行われています。

Text::Mecabで形態素解析

次にPerlで形態素解析を行う方法について説明します。ここでは広く利用されている形態素解析器であるMeCabのPerlバインディングであるText::MeCabの使用方法を説明します。なお、Text::MeCabを利用する際はMeCab本体を事前にインストールしておく必要があります。

以下は、Text::Mecabで単語分割と品詞、読み情報をダンプする例です。

use strict;
use warnings;
use utf8;
use Encode;
use Text::MeCab;
use Data::Dumper::AutoEncode;

my $parser = Text::MeCab->new(rcfile=> './mecabrc');
my $encoding = Encode::find_encoding('utf8');

my $input = " 彼女は大学生だ";

my @result;
for (
    my $node = $parser->parse($text);
    $node;
    $node = $node->next
) {
    next if $node->stat =~ /[23]/; （1）

    my $surface = $encoding->decode($node->surface); （2）
    my $feature = $encoding->decode($node->feature);
    my @feature = split ',', $feature;
    push @result, { surface => $surface,
                    pos => $feature[0],
                    pron => $feature[7] };
}
print eDumper(\@result);

（1）は文頭および文末のノードをスキップしています。（2）はText::MeCabの出力はバイト列なのでデコードしてPerlのUTF-8文字列にしています。

次は、Text::Mecabを利用した簡易ルビ振りプログラムです。この例ではText::Mecabで取得した形態素解析結果の読みの情報（カタカナ）をひらがなに変換してrubyタグを付けています。漢字にのみルビを付けるようにするなど改造してみてください。

#!perl -w
use strict;
use warnings;
use utf8;
use constant MECABRC => './mecabrc';
use Encode;
use Text::MeCab;
use Lingua::JA::Regular::Unicode qw/katakana2hiragana/;

if(@ARGV != 1){
    print <<USAGE;
USAGE: ./add_rubytag.pl INPUT_TEXT
USAGE
    exit -1;
}

run(@ARGV);

exit 0;

sub run {
    my $input = shift;
    my $parser = Text::MeCab->new(
        rcfile=> MECABRC,
    );

    my $encoding = Encode::find_encoding('utf8');

    my $result = q{};
    for my $text (split /(\s+)/, $input) {
        foreach (
            my $node = $parser->parse($text);
            $node;
            $node = $node->next
        ) {
            next if $node->stat =~ /[23]/;

            my $surface
                = $encoding->decode($node->surface);
            my $feature
                = $encoding->decode($node->feature);
            my $read = (split /,/, $feature)[7];

            if($read ne q{} && $surface ne $read) {
                $result
                    .= add_ruby_tag($surface, $read);
            }else {
                $result .= $surface;
            }
        }
    }
    print $encoding->encode($result), "\n";
}

sub add_ruby_tag {
    my ($surface, $read) = @_;
    my $read_hiragana = katakana2hiragana($read);
    if($surface ne $read_hiragana){
        return "<ruby>" . $surface. "<rt>"
            . $read_hiragana . "</ruby>";
    } else {
        return $surface;
    }
}

係り受け解析

係り受け解析は形態素解析の結果を受けて、文を構成する各単語、文節間の「修飾する（係る⁠）⁠」⁠「⁠修飾される（受ける⁠）⁠」の関係を調べ構文木を構築する処理です。

係り受け解析のしくみ

係り受け解析の手法としては、

• Shift-Reduce
• 全域木
• チャンキングの段階適用

などがありますが、ここではチャンキングの段階適用について説明します（図4⁠）⁠。チャンキングの段階適用では、次のような処理を行います。

• ① 機械学習によって作成されたチャンクモデルに基づいて文をチャンクという単位に分割する
• ② 文末以外のすべてのチャンクで、直後のチャンクに係るかどうかを推定する。係る場合は直後のチャンクを親（係り元）とする
• ③ すでに係り先となったチャンクを削除し、チャンクが1つになった場合は終了し、それ以外は残ったチャンクを対象として②の処理に戻る

CaboChaで構文解析

Perlで係り受け解析をする場合は、係り受け解析器CaboChaに付属するPerlバインディングを利用できます。CaboChaは素のテキストからの解析、MeCabの出力を受けての解析ともに可能です。

以下は、Text::MeCabで処理した結果をCaboChaの入力として係り受け解析を行う例です。

use strict;
use utf8;
use Encode;
use Text::MeCab;
use CaboCha;

my $parser = Text::MeCab->new(rcfile=> './mecabrc');
my $encoding = Encode::find_encoding('utf8');

my $input = " 彼女は東京にある大学に通っています";

my @result;
for my $text (split /(\s+)/, $input) {
    for (
        my $node = $parser->parse($text);
        $node;
        $node = $node->next
    ) {
        next if $node->stat =~ /[23]/;

        my $surface = $encoding->decode($node->surface);
        my $feature = $encoding->decode($node->feature);
        push @result, "${surface}\t${feature}";
    }
}

my $cabocha = CaboCha::Parser->new("-I1");
my $tree = $cabocha->parse(join("\n", @result));

my $chunk_number = 0;
for (my $i = 0; $i < $tree->chunk_size; ++$i) {
    my $chunk = $tree->chunk($i);

    print sprintf("chunk %d is following chunk %d",
               chunk_number++, $chunk->{link}), "\n";

    for(my $j = 0; $j < $chunk->{token_size}; ++$j){
        my $token = $tree->token($chunk->{token_pos} + $j);
        print "\t" . $token->{surface}
                . " : " . $token->{feature}, "\n";
    }
}

意味解析

意味解析とは、意味を利用して文の構造のあいまい性を解消する処理のことです。意味解析についてはさまざまな手法が研究されていますが、まだ実用段階とは言えないようです。

意味解析の手法として研究されているのが格文法を用いた手法です。

格文法

格文法とは、文の意味構造を格構造（動詞、深層格、名詞という関係の集合）によって表現する手法です。格には構文木によって決まる表層格と表層だけでは決まらない深層格があります。表層格は日本語ではガ格、ヲ格、ニ格の3種類が定義されています。深層格については表4に示します。

格解析

文の格構造を決定する処理を、格解析または述語項構造解析と言います。格解析の方法としては次の2種類があります。

• 選択制限に基づく手法
• 用例に基づく手法

選択制限に基づく手法は、「⁠名詞に対する意味的な制約である動詞の動作主格は、人間や動物のみ」といった制約によって格構造を決定します。格構造を決定するためには、格フレームと呼ばれる動詞が取り得る格構造のパターン（どの格を持つか、主格と深層格の対応、選択制限）が記載された格フレーム辞書を用いて、マッチする格フレームを探索します。

用例に基づく手法は、格構造付きの用例を集めて類似度の高い用例を探索します。最も類似度の高い用例の各構造を採用します。

日本語用の格解析ツールとしては、Perlで書かれたSynChaがあります。

＜続きの（3）はこちら。＞