Perl Hackers Hub

第31回 Perlによる自然言語処理入門(2)

この記事を読むのに必要な時間:およそ 4.5 分

前回の(1)こちらから。

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

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

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

図1 Trie木

図1 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はDartsDouble-ARray Trie SystemというC++実装のPerlバインディングです。

LOUDS-Trie

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

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

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

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

テキスト解析の流れ

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

図2 テキスト解析の流れ

図2 テキスト解析の流れ

形態素解析

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

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

形態素解析のしくみ

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

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

図3 Lattice構造

図3 Lattice構造

実際の形態素解析器ではこれに加えて,辞書に存在しない単語(未知語)であっても,分割位置を推定できるよう工夫がされています。例としては文字種に基づくヒューリスティック注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;
    }
}
注1)
必ずしも正しいわけではないが,ある程度は正解が期待できるような手法のことです。

コメント

コメントの記入