Professional Documents
Culture Documents
汎用日本語形態素解析エンジン
工藤 拓
アジェンダ
形態素解析の技術
辞書引きのアルゴリズム、データ構造
曖昧性の解消
MeCab の開発裏話
歴史
設計方針
汎用テキスト変換ツールとしての MeCab
恐ろしく汎用的!
「意外な」使い方
これから
形態素解析
文を単語に区切り、品詞を同定する処理
全文検索 Spam フィルタリング 人工無能...
以下の3つの処理
単語への分かち書き(tokenization)
活用語処理(stemming, lemmatization)
品詞同定(part-of-speech tagging)
すもも 名詞,一般,*,*,*,*,すもも,スモモ,スモモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも 名詞,一般,*,*,*,*,もも,モモ,モモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも 名詞,一般,*,*,*,*,もも,モモ,モモ
の 助詞,連体化,*,*,*,*,の,ノ,ノ
うち 名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ
。 記号,句点,*,*,*,*,。,。,。
形態素解析の技術
基本的な処理: 辞書から単語を引いて、与えられ
た文と照合し、最も自然な単語列を求める
辞書引き
入力文は単語毎に区切られていない
どの文字列を辞書引きするか自明ではない
曖昧性の解消
すべての可能な単語の組合せから(何らかの
基準で)最適な単語列を発見する
基準の定義
日本語処理のための辞書の要件
単語の区切りが明確でないので、先頭から
何文字までが単語なのかわからない
奈良先端科学技術大学院大学情報科学研究科
2
単純な方法(hash)だと (文長) の辞書引きが発生!
$str = "奈良先端科学技術大学院大学情報科学研究科";
for (my $i = 0; $i < length($str); ++$i) {
for (my $j = 1; $j < length($str) - $i; ++$j) {
my $key = substr($str, $i, $j);
if (defined $dic{$key}) {
...;
...
対象文字列の先頭から文字を順番にたどるだけ
辞書引き終了のタイミングが自動的にわかる
入力文字列の長さに比例した時間 O(文長) で探索が可能
さまざまな実装
Double- Array() TRIE
{#=- 1,a=1,b=2,c=3...}
int n = 1
for (int i = 0; i < strlen(key); ++i) {
// 見つかった!
if (BASE[k] < 0)
printf (“%d\n”, - BASE[k]);
n = k;
An efficient implementation of Trie Structures, }
Aoe et al 92 より引用
規則(ヒューリスティックス)に基づく手法 (80年代)
最長一致: 長い単語を優先 (KAKASI)
分割数最小: 文全体の単語の数を最小にする候補
文節数最小: 文全体の文節数を最小にする候補
多くの場合曖昧性を解決できない
最小コスト法
5
20 5
10 [ ] 5
10
10
[ ]
BOS 20 0
EOS
10
[ ] [ ] [
] [ ] 5
5 5 5
10 10 10 10
20 [ ]
[ ] 30
2
連接コスト: 二つの単語のつながりやすさ
生起コスト: 一つの単語の出現しやすさ
連接コストと生成コストの和が最小になる解
コストはなんらかの方法で決定 (後述)
Viterbi アルゴリズム (動的計画法の一種) で
O(文長) で探索可能
最小コスト法 (Viterbi アルゴリズム)
3200 4200
1000
700
1300
3150 4500
2700
1400
2700
5700 4550
1400
7100
最小コスト法 (Viterbi アルゴリズム)
3200 4200
6900
1000 800
700
7900
1300
3150 4500 1500
7250
2700
1400 800
2700
5700 4550
1400
最小コスト法 (Viterbi アルゴリズム)
3200 4200
6900
1000 800
700
1300
3150 4500 1500
2700
1200 600 7300
1400 800
2700 8200
5700 4550
600 7650
1400
最小コスト法 (Viterbi アルゴリズム)
3200 4200
6900
1000
800
500
700 7400
1300
3150 4500 1500
2700
1200 600 7300 8260
960
1400 800
2700
5700 4550
600
1400
最小コスト法 (Viterbi アルゴリズム)
3200 4200
6900
1000
800
500
700 7400
1300
3150 4500 1500
2700
1200 600 7300
960
1400 800
2700
5700 4550
600
1400
最小コスト法 (Viterbi アルゴリズム)
3200 4200
6900
1000
800
500
700 7400
1300
3150 4500 1500
2700
1200 600 7300
960
1400 800
2700
5700 4550
600
1400
コストの決定方法
人手でガンバル (90年代はじめ)
試行錯誤の連続, かなり大変
客観的評価が難しい
統計処理
大量の生テキストから推定
超低コスト
質に問題がある (全文検索目的だったら可能かも)
正解データを人手で作ってデータから推定
現代の形態素解析器の主流
低コスト
これから...
大量の生テキスト + 少量の正解データ + 統計処理
正解データ作成ツール (VisualMorphs)
Conditional Random Fields
解析速度を犠牲にしない
事前に計算できることはすべてやっておく
辞書やコスト値はすべてバイナリデータ
ディスクの使い方は富豪的
MeCab の設計方針
機能の選別
前処理/後処理でできることはやらない
ChaSen の機能過多の反省
文字コード変換, 改行処理, 連結品詞, 注釈, ChaSenサーバ
かわりに API を充実
C/C++, Perl, Java, Python, Ruby, C# ...
解析器にしかできない機能を提供
N-best 解, 制約つき解析, ソフト分かち書き(後述)
use MeCab;
my $str = "すもももももももものうち";
my $mecab = new MeCab::Tagger(“”);
for (my $n = $mecab->parseToNode($str);
$n; $n = $n->{next}) {
printf “%s\t%s\n”, $n->{surface}, $n->{feature};
}
ソフト分かち書き =
(形態素解析 + 文字単位解析)/2
全文検索におけるインデックスの単位
形態素解析: 高精度, 検索漏れ
文字単位/n-gram: 高再現率, 検索ノイズ
ソフトわかち書き
パラメータθによって無段階に変更
ソフト分かち書き: 動作例
形態素解析 文字単位
高精度 高再現率
検索漏れ 検索ノイズ
入力 「京都大学」
汎用テキスト処理ツール
MeCab は日本語形態素解析器だけではない
汎用的に作っています!
テキスト → テキストの汎用変換ツール
仮名漢字変換 (mecab-skkserv, AJAX IME)
ローマ字→ひらがな
文字コード変換 (ちと強引)
適切に辞書/コスト値を作れば実現可能!
/
/ai
/uta
/no
/a /i
/uta
MeCab の辞書
1. dic.csv (辞書定義)
の,166,166,8487,助詞,格助詞,一般,*,*,*,の,ノ,
京都,1306,1306,1849,名詞,固有名詞,地域,一般,*,*,京都,キョウト,キョート
桜,1304,1304,7265,名詞,固有名詞,人名,名,*,*,桜,サクラ,サク
....
MeCabの技術
辞書引き
通常の hash は使えない
TRIE
曖昧性の解消
最小コスト法
統計処理による正解データからの推定
設計方針
汎用性
テキスト変換ツール
意外な使い方