# Python で作って学ぶ形態素解析 2015/4 に公開した、Pure Python な形態素解析器 [janome][1] の内部を詳解します。 形態素解析とは、一般に分かち書きともいわれ、自然言語処理の基礎となる技術です。辞書ベースの形態素解析は主として辞書のエンコードと解析実行の２つのフェーズからなり、それぞれアルゴリズムが確立されています。 このセッションでは、形態素解析アルゴリズムについて解説し、また janome ではそれをどのように実装したのかと、工夫した点について紹介します。 ## 形態素解析とは 形態素解析とは、自然言語を形態素に分割する技術で、ざっくりいうと文章を単語の列に分割して品詞を推定することです。検索やテキストマイニング、文書クラスタリングといった、テキストを処理するほぼすべてのアプリケーションの重要な前処理を担います。 ## 形態素解析のデータ構造とアルゴリズム 教師ありの形態素解析では、学習済みの辞書と言語モデルをもとに分かち書きを実行します。 ### 辞書データ構造 辞書は、コンパクトで高速な検索が可能なデータ構造をもつことが求められます。辞書データ構造には、MeCab でも採用されている trie 木が用いられることが多いですが、 janome では、データサイズがよりコンパクトな Minimal Acyclic Subsequential Transducer （ Finite State Transducer, FST の一種）というデータ構造を使っています。FST は Java 製 OSS 検索エンジン Apache Lucene のコアとしても採用されていて、janome の実装の一部は Lucene を参考にしています。なお、辞書と学習済み言語モデルは mecab-ipadic を利用させていただいています。 また、ライブラリに辞書を同包するにあたって工夫したこと、苦労した点についてもお話します。 ### 解析アルゴリズム 解析実行時には、日本語分かち書きの曖昧性を解消するために、一番もっともらしい分割方法を探索します。もっともらしい分割方法の与え方にはいくつかありますが、janome では品詞バイグラムの出現確率がもっとも高くなるようにパスを推定する、最小コスト法を使っています。アルゴリズムとしては MeCab で採用されているビタビアルゴリズム（動的計画法の一種）を用いています。 [1]: http://mocobeta.github.io/janome/