Pure Kotlin な形態素解析機 Momiji をリリースしました
https://github.com/tokuhirom/momiji
Motivation
Pure kotlin な形態素解析機が欲しかったから。なぜ pure kotlin がいいかというと、kotlin multiplatform な環境で形態素解析したかったから。
実践・自然言語処理シリーズ2 形態素解析の理論と実装 が網羅的で、どういうふうに mecab が作られてるかを解説してくれてるので、この通りに実装すればまぁ普通にできる。
形態素解析は、ラティス構築してビタビアルゴリズムで最小コスト経路をたどればできるということは知っていたので、というかまぁ IME 作るのとやってることはほとんど一緒なので、やればできるということは知っていたので、やってみたという感じ。
kotlin multiplatform で動くからもちろん JS でも動くので、デモサイトも作ってみました。 https://tokuhirom.github.io/momiji/
どう作ったか
mecab の辞書をパースして、ラティスを構築してビタビアルゴリズムでコスト最小な経路を求めた。
mecab の辞書のパース
mecab のバイナリ辞書のパースは sys.dic, unk.dic, char.bin, matrix.bin の4つのファイルをパースできれば、ひと通りの事ができる。
バイナリファイルはすべてリトルエンディアン。
sys.dic / unk.dic のパース
sys.dic はシステム辞書で、unk.dic は未定義語のコストが入っている特殊辞書。フォーマットは同じ。
val magic = byteReader.readUInt()
val version = byteReader.readUInt()
val type = byteReader.readUInt()
val lexsize = byteReader.readUInt()
val lsize = byteReader.readUInt()
val rsize = byteReader.readUInt()
val dsize = byteReader.readUInt()
val tsize = byteReader.readUInt()
val fsize = byteReader.readUInt()
val dummy = byteReader.readUInt()
という感じでヘッダ領域がある。magic は 0xef718f77u とファイルサイズの xor で、これにより辞書が壊れていないかを確認できる。
その後に 32 byte の charset 領域がアリ、charset が格納されているはずだが、現実には "yes" という文字列が入っている。./cofigure の結果の charset じゃない文字列とかが入っちゃってるのかなぁと思いつつ、現実的には utf-8 決め打ちするので無視して問題ない。
その後、dsize バイト分の領域に、Darts の double array が格納されている。
そして、tsize 個のトークンが格納されている。Token は以下のようなフォーマット。
data class Token(
val lcAttr: UShort,
val rcAttr: UShort,
val posid: UShort,
val wcost: Short,
val feature: UInt,
val compound: UInt,
) {
companion object {
const val SIZE = 2 * 4 + 4 * 2
}
}
あとは fsize バイトの feature が入っている。
char.bin
未定義語を判定するための文字種定義。例えばカタカナの連続だったら一つの未定義語とする、みたいな処理をするために使う。
32bit unsigned int で char category の数が格納されている。char category は 32 バイトの固定長文字列で、null terminated である。その後、0xFFFF 個の unsigned int が格納されております。
bit field になってるけど以下のような構造。
data class CharInfo(
val type: Int,
val defaultType: Int,
val length: Int,
val group: Boolean,
val invoke: Boolean,
)
matrix.bin
連接コストが入ってる。
ヘッダに unsigned short 2つで lsize と rsize が入っている。ここから、lsize * rsize 個の short が入っている。
連接コストは matrix[leftContextId + lsize * rightContextId] のようにして取得可能。
Darts の実装
なんか common prefix search したいわけだが、、 https://blog.64p.org/entry/2024/07/24/010456 先日、KDary という実装を作ってできるようにしたんだけど、mecab のバイナリ辞書には Darts のバイナリが埋まってたので、これをそのまま使ったほうが効率がいいという話に。。
Darts のバイナリを使って common prefix search するだけならこれだけで実装できた。
ラティスの構築
なんかこういう感じでやったらできた。
ビタビアルゴリズムの実装
ガーッとラティスをたどりながら最小コストを計算していって、最後に逆向きに最小コスト経路をたどっていくだけなので簡単。
まとめ
形態素解析って大変なのは辞書作るところなので、すでにある辞書を利用する分には簡単に実装できた。コード量としても大した事ない感じ。 あと、工藤さんの本がめっちゃ丁寧なのでかいてある通りに実装すれば普通に動いた。