日本語形態素解析エンジンKuromojiについて調べた
はじめに
とある事情(仕事)により、日本語の形態素解析エンジンKuromojiについて調べる必要があったので、ドキュメントとコードを読み込んだ。 形態素解析とは、ものすごく簡単に言うと、文章をその構造や品詞に細かく分解することです。分解された単位をトークンと呼ぶ。(イメージとしては、単語や助詞がトークンとなりえる。)
特に、自然言語処理(NLP)なんかでは馴染みがあるのでは？(私は素人なので...) 形態素解析は、主に利用する辞書の精度(網羅率)に大きく依存する形になります。例えば「ほげふが」という文章を解析するとして、辞書に「ほげ」と「ふが」が存在している場合、["ほげ", "ふが"]と2つのトークンに分解することができる。(これをトークナイズと呼ぶ。) 同じく文章をトークンに分解する方法として、N-gramがあります。Nに数字が入るわけですが、例えば2-gramで文章「ほげふが」をトークナイズする場合は、["ほげ", "げふ", "ふが"]と3つのトークンを生成することができる。
なおApatche版とAtilika版の2つが存在しますが、本記事では Atilika版 version 0.9.0を対象としている。
Kuromoji
概要
Java製の日本語形態素解析エンジン。
公式
kuromoji - japanese morphological analyzer
単語辞書
Kuromojiでは、ユーザ側は用意されている単語辞書(例. kuromoji-ipadic)に加えて、ユーザ独自で固有名詞等を指定できるユーザ辞書を利用できる。 また、内部的にはこれらの辞書に含まれない単語を、「未知の」単語辞書として保持しているようです。ちなみに未知の単語辞書については、そのカテゴリによって自動的にトークン化される。例えば「123#.!」という文章がある場合、["123", "#.!"]と数字、記号のカテゴリにトークン化される。詳しくは以下の実装を確認してほしい。
kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
Kuromojiの解析モード
トークン化する際の解析粒度に応じて、モードが3つほど存在する。
Normalモード デフォルトモードで、辞書にのっとってトークナイズする。 未知の単語については、上記の方法にのっとり、カテゴリごとにまとめてトークナイズする。
Searchモード Normalモードに加えて、複数の言葉が組み合わさった単語を分解してトークナイズする。 例えば「日本経済新聞」という名詞があった場合、["日本", "経済", "新聞"]と分解する。 何が嬉しいかというと、全文検索エンジンなどで、単語を引っ掛けたい時に有効。
Extendsモード Searchモードに加えて、未知語をuni-gram (雲丹ではなくて「1」という意味)としてトークナイズする。 例えば、「サバゲー」が未知語の場合は、["サ", "バ", "ゲ", "ー"]となる。
内部で用いられるアルゴリズム
形態素ラティス
下図のような、ノードがトークンとなったラティス。 各ノード・エッジにはコストが存在し、それぞれ単語辞書・解析モード別の計算式によって与えられる。 このコストを最小となる (≒ 尤もらしいトークナイズができている) パスを求めるためにViterbiアルゴリズムを用いる。
Viterbi
隠れマルコフモデルに基づいた動的計画法(DP)で、考えられる経路の中で尤もらしい経路を見つける。 隠れマルコフモデルに従うので、コストの部分について確率的な解釈が可能 (というかそうするのが一般) である。しかし今回のケースではコストが一意に決まるため、最小コストを確率ではなく一意に探索することが可能。
Viterbiアルゴリズム - 機械学習の「朱鷺の杜Wiki」
http://www.phontron.com/slides/nlp-programming-ja-04-ws.pdf
時間計算量がO(T*N2)かかる？ (T: 時間の終端、N:ノード数)
実装は以下。
kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
Patricia Trie
基数木と呼ばれる木構造のこと。
連想配列を使って各エッジに文字が張られるイメージ。
Pros
- 省メモリ
- 検索・挿入・削除 : O(k) (k: キーの長さ) なので、 (二分木と比べると、場合によっては)物凄く速い。
- 日本語の場合は文字列長が小さいので、ここはかなり効いてくると考えられる。
Cons
- 文字列や、文字列に変換可能なデータしか扱えない。
Finite State Transducer (FST)
有限状態トランスデューサと呼ばれる。いわゆる有限状態オートマトンに各エッジの出力を加えたもの。
Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待）
Pros
- Patricia Trieが利用可能・状態数が最小であることが保証されるため、省メモリ。
- 決定性を持つため、入力に対する出力が一意に決定。
- DAGなのでトポロジカルソート可能。 ラティスにおける最小コストの経路はトポロジカルソート+ Viterbiで高速に探索可能。トポロジカルソートはO(V+E) (V:ノード数, E:エッジ数)。
Cons
- 先頭文字(prefix)の探索に時間がかかる。(日本語だと候補となる文字数が多すぎるので危険...) なので、先頭文字はcachingなどによる高速化で工夫される。
FSTで単語辞書を管理している。 (未知の単語辞書も含む) // Note that FST only allows the presorted dictionaries as input.
kuromoji/Builder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
ユーザ辞書を使った単語分割
こっちもFSTで保持。 surfaceが(Trie構造)FSTで保持している辞書
kuromoji/UserDictionary.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
若干しゃくとり法と似てるなと思った（は？）
以下が実装部分
/** Lookup words in text
* @param text text to look up user dictionary matches for
* @return list of UserDictionaryMatch, not null */
public List<UserDictionaryMatch> findUserDictionaryMatches(String text) {
List<UserDictionaryMatch> matchInfos = new ArrayList<>();
int startIndex = 0;
while (startIndex < text.length()) {
int matchLength = 0;
int endIndex = 0;
while (currentInputContainsPotentialMatch(text, startIndex, endIndex)) { //トークン検索
String matchCandidate = text.substring(startIndex, startIndex + endIndex);
if (surfaces.containsKey(matchCandidate)) {
matchLength = endIndex;
}
endIndex++;
}
if (matchLength > 0) { //マッチするようなトークンが見つかったらば,
String match = text.substring(startIndex, startIndex + matchLength);
int[] details = surfaces.get(match);
if (details != null) {
matchInfos.addAll(
makeMatchDetails(startIndex, details)
);
}
}
startIndex++;
}
return matchInfos;
}
おわりに
まとめると、シンプルにかけます。 1. FSTによる管理で高速に辞書検索（トークンとなる候補をここで探す。） 2. 形態素ラティスを構築して尤もらしくトークナイズする（トークンとなる候補の中から、トークンを決定する。） 高速化を意識された実装になっていて、素晴らしいと思いました。
