本記事は，自然言語処理 Advent Calendar 2019 - Qiitaの１日目の記事です．
はじめに
今回の記事では，去年末ごろからPythonとCythonだけでチマチマ作った形態素解析器Taiyakiをベースに，形態素解析器の解説をしようかなと思います．この形態素解析器の完成はまだ程遠いんですが，ひとまず簡単な形態素解析はできるようになったのでここでお披露目しておきます．本記事は実質，Double-Arrayの辞書引きと最小コスト法に基づく形態素解析器の解説記事となっています．
なぜ今更に形態素解析器を作ったかと問われると困ってしまうのですが，NLPerなら１つぐらい自作しても良いのかなってことと．形態素解析がどう動いているかって意外と知らなかったのが動機です．解説内容間違えてる可能性はあるので，見つけた方はコメント欄でご指摘いただけると嬉しいです．
作っているものは下記リポジトリで管理しています．近いうちにちゃんとした形でリリースしたいです．
自作するにあたって読んだ本はこちらです．MeCabやSentencePieceの開発者として知られる工藤さんの本で，形態素解析器を開発する人にとっては（どれぐらいいるのか知らんけど）紛れもない神本です． 本記事は，この本から得られる以上の情報を提供できるとは思いませんが，自作するに当たり苦労した点やグラフィカルに解説して初学者でも楽しめるように紹介できればと思います．
- 作者: 工藤拓,言語処理学会
- 出版社/メーカー: 近代科学社
- 発売日: 2018/10/04
- メディア: 単行本
- この商品を含むブログを見る
目次
めっちゃ長くなったので先に目次書いておきます．
- 形態素解析とは
- Taiyakiの全体構成
- Double-Arrayによる辞書引き
- 共通接頭辞検索と最長一致法
- 最小コスト法
- ラティス構築
- ビタビアルゴリズムによる最小コスト経路の算出
- 未知語処理
- まだやっていないこと
- まとめ
形態素解析とは
形態素解析とは，文を入力した際に，単語分割及び品詞推定を行う処理を指します．形態素（morpheme）は言語学上の最小限の意味の単位を表し，その最小単位で区切ってあげようというのが形態素解析です．
形態素解析を実現する手法は，基本的に２種類．本記事で上げるラティスを構築して最小コスト法を解く手法と，点予測と呼ばれる手法があります．Taiyakiでは前者を採用しています．最小コスト法を採用している形態素解析器としてMeCabやJumanが上げられ，一方点予測ではKyTeaなどがあります．先に点予測を説明しておくと，点予測では文字の系列データ "吾輩は猫である" を入力した際に，各文字の間に境界があるかを予測する単純なモデルです．つまり，"吾"と"輩"は区切られているか？"輩"と"は"は区切られているか？といった形で１文字ずつ処理していきます．この例だと後者で区切れて"吾輩"というのが１つの単位として抽出できるのが良さそうですね．この例では単語分割だけですが，品詞も含めた予測（多クラス分類）を解けば品詞推定もいけます．なんだかRNNとかでできそうだな，って思う人がいるかもいれませんが，実際にJumanなどで知られる黒橋・河原研の方がニューラルネットを使った手法を，NLP2019やNAACLで手法を発表しています．Podcastでも説明しているので興味がある人はぜひ．
点予測に対して，最小コスト法は実装項目が多く作るのは面倒ではあるのですが，人による言語知識をうまく組み込めるような仕組みになっており，作っていて面白そうだなと思いこちらを採用しました．また経路選択による解候補（N-best）が出せるというのも点予測にはない魅力です．
Taiyakiの全体構成
Taiyakiの全体構成は下記のようになっています．まず最初に大規模語彙データから，辞書を構築する必要があります．文の解析時にこの構築した辞書を参照します．この辞書をどう作るのかというと，Double-Arrayという仕組みを採用します．
Double-Arrayによる辞書引き
入力文を単語分割するためには，辞書データが必要になります．幸いにも多くのデータが公開されているのですが，まずはmecabのIPA辞書というのを使うことにしました．このIPA辞書には，様々な語彙が品詞や読み情報を伴い記録されています．またCRFで計算されたコスト（後述）が既に付与されており使いやすいです．一部例を以下に示します．何だかよくわからん数字とか記号が入っていますが，とりあえず気にしないで雰囲気を感じてください．
鯛焼,1285,1285,5618,名詞,一般,*,*,*,*,鯛焼,タイヤキ,タイヤキ 太公望,1285,1285,5622,名詞,一般,*,*,*,*,太公望,タイコウボウ,タイコーボー 土盛り,1285,1285,5622,名詞,一般,*,*,*,*,土盛り,ドモリ,ドモリ 祝い事,1285,1285,5601,名詞,一般,*,*,*,*,祝い事,イワイゴト,イワイゴト
このようにIPA辞書に登場する単語単位で入力文を区切れば，単語分割ができてきそうです（コストや未知語はひとまず忘れる）．このように与えられた入力文から辞書に登録された単語を抽出する作業を辞書引きといいます． 非常にナイーブに実装すると，まず語彙をPythonの辞書型などでロードします．そして，入力文字列に対してすべての部分文字列を計算し，その部分文字列が辞書に登場するかを計算すれば，単語の区切り候補はすべて分かるわけです．ただ問題になるのは計算コストです．すべての部分文字列を考えるのにN2，さらに文字列のハッシュ値計算にNかかるので，O(N3)という非現実的な計算量になります．数十万，数百万の語彙を扱うことを考えると，さすがに厳しいです．
そこで語彙情報を効率的に保持・探索できるデータ構造のDouble-Arrayが登場します．これは1989年に登場した技術ですが，未だにメモリ使用効率が高く，最も高速なトライの実装方法として現役のアルゴリズムのようです．これからDouble-Arrayの解説を，探索と構築に分けて説明しますが，構築手段の方は探索と比べてかなり複雑であるためスキップして大丈夫です．またDouble-Arrayを実際に使うときは，Darts-cloneを使ってしまえば，一瞬ですが，今回は勉強も兼ねて自分で実装してみました．さすがにPythonだと構築時間が馬鹿にならなかったのでCythonで書いています．実業務ではおとなしくDarts-cloneを使いましょう．
Double-Array 検索編
Double-Arrayはその名の通り，２つの同じ長さの配列（int）から構成されます．それぞれの配列をbaseとcheckと呼びます．文字列を入力した際に１文字単位で文字コードを計算し，baseとcheckを使うことで，その入力文字列が辞書に含まれているかどうか？を判定させることができます．baseは，文字コードのオフセット値がセットされており，そのbaseのオフセット値と文字コード値を足し合わせた値をインデックス値に持つcheckの値が，その遷移元のbaseのインデックス値と一致する場合，遷移が成功し，そこまでの文字が登録されていると判断できる仕組みです．checkの値が遷移元のbaseのインデックス値でない場合，それは未知の遷移ということで辞書には登録されていないということが言えます． 言葉で説明すると難しいので以下にスライドを作ったのでこれで説明します．
この例では非常にシンプルに，文字はa, b, c, #の4文字が存在します．#というのは終端コードを指し，語彙の終端を判断できます．語彙はaとbcの２つだけ登録されたDouble-Arrayが存在し，既に構築済みのものを用意しました，例として，a, bc, cの3つの文を入力したときに，Double-Array上でどう検索されるか示しています．最初の2つは語彙辞書に登録されているので，見つかりますが，最後のcは語彙にはないので検索が失敗しているのが分かると思います．
どうでしょう？入力文字列に比例した処理時間で，高速に検索できるのが分かるでしょうか？生の語彙辞書ではなく，2つのint配列だけで辞書引きできるのは感動的です．
ところでこの文字コードの値は，Taiyakiの実際の実装では，書籍に書いてあるとおり，UTF-8マルチバイト値で行いました．これにより遷移距離は255以下になるため配列の構築がコンパクトに実現できます．例えば"あ"という文字コード値は，[227, 129, 130]という3つ（3バイト）に分割されます．つまり"あ"を調べるためには，3回の遷移が必要になるわけですが，入力文字列長は高々しれた長さなので，処理時間を気にする必要はないでしょう．それよりも遷移距離を短くしたことでDouble-Arrayをコンパクトに作れることの方が重要です．
In [1]: s = 'あ'.encode('utf-8') ...:print(s) ...:for code_val in s: ...: print(code_val) ...: b'\xe3\x81\x82' 227 129 130
Double-Array 構築編（スキップしてええよ）
先程の例では，すでに構築済みのDouble-Arrayが登場しましたが，あれをゼロから作ってみましょう．Double-Arrayは一度構築してしまえば単純な話ですが，それをどうコンパクトに高速に構築するのか，というのは結構難しいです．また語彙を追加していくと，コンフリクトが発生してしまうので，ノードの付替をする部分が複雑です．ここは決して難しいものではないんですが，手順が多いので，じっくりと紙に書いたりして動作原理を理解する必要が私にはありました． また，Double-Arrayの構築には時間がかかりますが，一般的に形態素解析を行う際は，動的に語彙を追加することはあまり考えていないため，オフラインで時間をかけて１度流すもの，という前提を置く場合が多いかもしれません．といってもDarts-cloneの構築は割と一瞬なんですけどね．
辞書構築もスライドを使って説明しましょう．基本的には０リセットされたDouble-Arrayの値をソート済み語彙辞書を最初から登録して値を更新していくだけです．ただし，コンフリクトが容易に発生するので，コンフリクト時にはコンフリクトが発生したインデックスとそのコンフリクトが発生したインデックスを参照しているインデックスの値を入れ替えていく必要があります．ここまでの説明で分かったらあなたの空間把握能力は天才的だと言っていいでしょう．
構築したDouble-Arrayは検索のときに使った値に最終的になります．
実装のコツ
最初ナイーブに上記をPythonで実装していたのですが，これが遅くて遅くてとてもじゃないですが，数十万単語を１日経っても構築できないような状況でした．というのもコンフリクト発生時に，遷移元を親に持つノードを入れ子で探す必要があったりするので，毎度全探索してると指数関数的に遅くなります．マルチバイト単位で遷移するため，base値から255程度しか移動できないので，そのことをうまく使って対象ノードからの探索範囲を絞る必要があります．またある程度，配列の空きがなくなってきたタイミングで，下手にセコセコ配列を使わずに，配列のメモリを増やしてスカスカの領域を作って再配置しやすくするのも手です．ただこのあたりは私もチューニングしきれていないので，別途高速化できたタイミングでまた記事を書こうと思います．
自作Double-ArrayとDarts-cloneの比較
せっかく自作したので，Darts-cloneと比較してみます．Darts-cloneはC++でできているのに対して，私の自作はCython製です．私の実装がヘボいとはいえ，どれぐらいの性能差があるのか，気になって調べてみました．mecab-ipadicに登録されていたおよそ33万語を登録したDouble-Arrayを構築した結果が以下です．
| 構築時間 | Double-Arrayサイズ | |
|---|---|---|
| Darts-Clone | 1.5秒 | 5.2 MB |
| Taiyaki | 93.3秒 | 25.7 MB |
うーん，これはひどいです．C++とCythonとか言う前に，実装力の差がありそうですね．実際に構築はオフラインで行うので構築時間はそこまで気にしなくても良いかなとは思いますが，改善の余地は大きそうです．ファイルサイズも私のは生テキストで保存しているとはいえ差が大きく開きました．ノードのアサイン・再アサイン時に時間がかかっていたのでガバガバと配列サイズを大きくする実装を入れたのが原因で，かなりスパースになってしまいました．
今回実装したDouble-Arrayの実装はこちらです．Cython知らん！という方もほぼ見た目Pythonなので何となく分かるかと．ただ実装は結構複雑というか汚くなってしまったので，最適化と合わせてまだまだ改善していきたいです．
Taiyaki/double_array.pyx at master · jojonki/Taiyaki · GitHub
共通接頭辞検索と最長一致法
Double-Arrayによる辞書引きという形態素解析における非常に重要な機能を実装することができました．実は既にこの段階で最長一致法という単純な単語分割器は作れてしまいます．最長一致法とは，その名の通り長い単位で区切れるパーツで単語分割を行う手法です．そのために必要な共通接頭辞検索（Common Prefix Search）について説明しましょう．共通接頭辞検索とは，入力文から考えられる様々な接頭辞（prefix）が辞書に登場するものかを検索します．例えば「東京都」という文にに対しては「東」「東京」「東京都」という単語が共通接頭辞になります．
この共通接頭辞検索によって，「アイスカフェオレ飲みたい」を最長一致法で分割してみましょう．この文に対して共通接頭辞検索は，「ア」「アイ」「アイス」「アイスカ」...「アイスカフェオレ飲みた」「アイスカフェオレ飲みたい」...「イ」「イス」「イスカ」...という接頭辞候補ができるので，それらが辞書に含まれるのかを調べればよいのですが，Double-Arrayがあるわたしたちは，この共通接頭辞もスマートに抽出できます．例えば「アイス」「アイスカフェオレ」「飲」「飲み」「たい」という語彙が登録されているDouble-Arrayが使えるとしましょう．そうするとDouble-Arrayによる共通接頭辞検索を使った最長一致法は下記のように実装できます．
- 「アイスカフェオレ飲みたい」を対象文にセット
- 「ア」に遷移．また「#」に遷移不可，「ア」は接頭辞でない．
- 「イ」に遷移．また「#」に遷移不可．「アイ」は接頭辞でない．
- 「ス」に遷移．また「#」に遷移可能．「アイス」を接頭辞に追加．
- （中略．「ス」に戻って，「カ」「フェ」「オ」で遷移）
- 「レ」に遷移．また「#」に遷移可能．「アイスカフェオレ」を接頭辞に追加．
- 「飲」に遷移不可．ここでDouble-Arrayの探索を打ち切る（「アイスカフェオレ飲」を接頭辞に持つ単語はもう辞書に登場しないので打ち切れる）．
- 共通接頭辞「アイス」と「アイスカフェオレ」をreturn．
- 最長一致法に基づき，「アイス」と「アイスカフェオレ」は「アイスカフェオレ」の方が長いのでこちらを採用．
- 【アイスカフェオレ】まで区切れたので，次に「飲みたい」を対象文にセットして共通接頭辞検索を行う．
- （これを文末まで繰り返す）
- 【アイスカフェオレ，飲み，たい】と最長一致法で区切れる．
このように共通接頭辞検索の結果を，貪欲に長い方を採用していくだけで，簡単に文を区切ることができます．また基本的には１文字ずつ調べていくだけで（１文字目から調べ直さなくても）複数の共通接頭辞を出せるのも効率的ですね．工藤さんの書籍によると単純な手法ですが，90%以上の精度が得られる結果も出てるようです．品詞などの単語に付属する情報がいらないアプリケーションを考える場合は，Double-Arrayだけで実装できるので非常に軽量・高速・シンプルに出来上がります．
最小コスト法
最長一致法では，貪欲に長いトークンを採用する形で分割をしていきましたが，実際に分割パターンはたくさんあるはずです．そこで使われるのが全分割パターンを表現したラティス構造を作り，そのラティスから最小コストの経路を探し，その経路を通るノードの単位（単語・形態素の単位）を採用することで，最適な形態素解析を行おうという手法を，最小コスト法と呼びます．コストとは何かというと，その語の発生のしやすさや，語と語の繋がりやすさ，になり，前者を生起コスト，後者を遷移コストと呼びます．
まずはラティス構築に関して説明していきましょう．
ラティス構築
形態素解析器におけるラティスとは，下記のように形態素解析及び単語分割の全解候補です（単純のため省略していますが，もっと多くのノードがあります）．共通接頭辞検索により，入力文を1文字ずつずらして共通接頭辞検索をすることで，共通接頭辞をすべて洗い出せるので，下記のようなデータ構造で表現できます．ラティスの実装は自由に行えると思いますが，書籍に倣うと，各文字位置（０〜８）において，BeginNodes，EndNodesという形で保持する形を選びました．BeginNodesはそこから後ろにつながるノード群を保持し，EndNodesは反対に前につながるノード群を保持します．下記の例だと，BeginNodes[3]には（ネコ，ネ），EndNodes[3]には（輩は，は）のノードが格納されます．ノードには，文の中での文字位置，生起コスト，文脈ID，品詞，などの情報をもたせます．
ラティス上に数字が書いていますが，これはmecab-ipadで計算済みのコストになります．矢印上の数字は連接コスト，ノード内の数字を生起コストと呼びます．連接コストはその経路を通るためのコスト，生起コストはそのノードの文字を通るためのコストです．つまり経路を選ぶ（次のノードを決定する）度に，連接コストと生起コストの和がコストとして発生します．縦線のグリッドで書いている０から８の数字は文字位置を表します．ラティスの特徴として，どのような経路を通っても元の文が復元できるようになっているので，あとはどう最小コストの経路を出すかという話になります．
ところでこの数字はどこから持ってきたかというと，mecabのIPA辞書に定義されたものを使っています．記事冒頭で出てきたあの謎の時系列データを見てみましょう．品詞.csvに色々定義されています．左から４つを順に説明すると，見出し語，左文脈ID，右文脈ID，生起コスト，です．左文脈IDとはその単語を左から見たときのIDで，右文脈IDはその逆です．
鯛焼,1285,1285,5618,名詞,一般,*,*,*,*,鯛焼,タイヤキ,タイヤキ 太公望,1285,1285,5622,名詞,一般,*,*,*,*,太公望,タイコウボウ,タイコーボー 土盛り,1285,1285,5622,名詞,一般,*,*,*,*,土盛り,ドモリ,ドモリ 祝い事,1285,1285,5601,名詞,一般,*,*,*,*,祝い事,イワイゴト,イワイゴト は,261,261,3865,助詞,係助詞,*,*,*,*,は,ハ,ワ
左・右文脈IDがなぜいるかというと，連接コストを見るためです．連接コストはmatrix.defに定義されています． 例えば，【鯛焼（名詞）, は（助詞）】という２つのノードの連接コストを調べるには，【鯛焼】の右文脈ID，【は】の左文脈IDを見ればよいのです．（右左混乱しますが，気をつけてください．鯛焼は左側のノードですが，連接エッジ側（右側）から見たコストになるので，右文脈IDとなります）．matrix.defの該当行は下記のように，単語A，Bが連接する際に，Aの右文脈ID，Bの左文脈ID，連接コストの順で記述されます．つまり【鯛焼（名詞）】の右文脈ID，【は（助詞）】の左文脈IDが並んでいる場所を探すと下記のようになっているので，この連接コストは-3845と負の値であることが分かります．要は負のコストなので，選ばれやそうな経路です．
1285 261 -3845
では，【鯛焼, 太公望】はどうでしょうか？いずれも文脈IDが1285なので，matrix.defの1285 1285の行を探せばよいのです．先程よりもコストが上がったので，連接コストだけの観点で言えば，【鯛焼太公望】よりも【鯛焼は】の方が自然なつながりであるというのが機械的に分かります（意外と鯛焼太公望のコストが低いですが笑）．
1285 1285 62
このようにして，生起コストと連接コストが分かったので，あとは最小コストの経路パスを競プロよろしくのテクニックで好きに解けばよいのです． ちなみにこれらのスコアはBCCWJなどの大規模コーパスでCRFなどによって学習されるのですが，今回の記事ではそのあたりまで間に合わなかったので，今度の記事で新語追加などの話と合わせてお話できればと思います．
ビタビアルゴリズムによる最小コスト経路の算出
最小コストの経路を出すには，動的計画法であるビタビアルゴリズムを使うのが楽です．ビタビアルゴリズムは順方向と逆方向の２種類の探索で，最小コストの経路が見つかります．順方向では各ノードにおいて，そのノードに到達するための最小コストを計算していき，更に最小コストを通る直前の経路を保存します．逆方向では，その各ノードで保存されている直前の最小コストの経路を選択していくだけ，最小コストの経路が辿れます．これもスライドを用意したので見てみてください．前方向計算時に，いくつかのノードでは複数の経路がありますが，最小コストの経路を選択していることに注意してみてください． speakerdeck.com
ここまでで一通り形態素解析ができるようになったので，形態素解析をしてみた例がこちらになります．
$ python examples/run_tokenizer.py Loading dictionaries... Loaded! Query (press "end" to exit)>> 吾輩は猫である Tokenized tokens (min cost): 表層系 品詞 発音 未知語 __BOS__ None None None 吾輩 名詞 ワガハイ False は 助詞 ワ False 猫 名詞 ネコ False で 助動詞 デ False ある 助動詞 アル False __EOS__ None None None Query (press "end" to exit)>> 形態素解析エンジンTaiyakiできたぞ Tokenized tokens (min cost): 表層系 品詞 発音 未知語 __BOS__ None None None 形態素 名詞 ケイタイソ False 解析 名詞 カイセキ False エンジン 名詞 エンジン False Taiyaki 名詞 * True でき 動詞 デキ False た 助動詞 タ False ぞ 助詞 ゾ False __EOS__ None None None Query (press "end" to exit)>> すもももももももものうち Tokenized tokens (min cost): 表層系 品詞 発音 未知語 __BOS__ None None None すもも 名詞 スモモ False も 助詞 モ False もも 名詞 モモ False も 助詞 モ False もも 名詞 モモ False の 助詞 ノ False うち 名詞 ウチ False __EOS__ None None None
未知語処理
ここまでで形態素解析はできるようになったのですが，それは既知語が登場する場合です．mecab-ipadicには33万語登録されていますが，実際に語彙というのはロングテールなので，マイナーな語彙は登録されていなかったり，そもそも語はどんどん追加されていくので（流行語，地名，ユニット名とか色々），これに対応しないといけません．では，実際に知らない語，未知語を含む文を入力されたらどうすべきでしょうか？極端な話，私が今思いついたような語彙とかにも対応してほしいわけです．実は先程の形態素解析の例で「Taiyaki」という未知語があるのですが，うまく単語区切りできているのは，未知語処理のおかげです．
TaiyakiではMeCab処理を模倣しているので，解析時の未知語処理もMeCabさんに倣うとしましょう．MeCabでは，解析する文字種毎にヒューリスティックなルールが設定されており，それをベースに未知語処理していきます．そのルールはmecab-ipaadicのchar.defに記述されています．char.defは冒頭，下記のような記述があります．
DEFAULT 0 1 0 # DEFAULT is a mandatory category! SPACE 0 1 0 KANJI 0 0 2 SYMBOL 1 1 0 NUMERIC 1 1 0 ALPHA 1 1 0 HIRAGANA 0 1 2 KATAKANA 1 1 2 KANJINUMERIC 1 1 0 GREEK 1 1 0 CYRILLIC 1 1 0
左から順に，文字種，動作タイミング（0/1），グルーピング（0/1），長さ（0,1,..,n)です．
- 文字種
- ユニコードポイントの範囲を指し示します（後述）
- 動作タイミング
- １であれば常に未知語処理を働かせ，０であればその位置から開始する既知語がない場合に動作させる
- グルーピング
- 同じ文字種でまとめるかどうか
- 長さ
- １以上である場合，その長さで未知語をまとめる．０である場合，まとめる長さ制約は設けない（ただしグルーピングが１のときのみ有効）
文字種とは，Unicodeのコードポイントの値から判定するものとしてchar.defで以下のように定義されています．漢字とか平仮名のコードポイントの範囲が書かれています．
# HIRAGANA 0x3041..0x309F HIRAGANA # KATAKANA 0x30A1..0x30FF KATAKANA 0x31F0..0x31FF KATAKANA # Small KU .. Small RO
この文字種を判定するコードは，Pythonで下記のように書けます．int値に変換して範囲に収まっているか見るだけです．
# 便宜上char.defより部分的に抜粋してここで定義．実際はchar.defから読み込んでパース． char_def = { 'ALPHA': [('0x0041', '0x005A'), ('0x0061', '0x007A')], 'HIRAGANA': [('0x3041', '0x309F')], 'KATAKANA': [('0x30A1', '0f30FF'), ('0x31F0', '0x31FF')], 'NUMERIC': [('0x0030', '0x0039')] } def analyzeCharCategory(char): code_pt = ord(char) # ordはUnicode コードポイントを表す整数を返す for char_category, char_range_list in char_def.items(): for char_range in char_range_list: char_range_beg, char_range_end = char_range if code_pt >= int(char_range_beg, 16) and code_pt <= int(char_range_end, 16): return char_category for char in ['a', 'あ', 'ア', '3']: print(char, ':', analyzeCharCategory(char))
結果は下記のようになり，文字種が判定できていることが分かります．
a : ALPHA あ : HIRAGANA ア : KATAKANA 3 : NUMERIC
文字種判定ができるようになったので，いくつか未知語を含む文の形態素解析をしてみましょう．
最初は未知語「GAFA」です．ALPHAのルールは，グルーピングが１かつ未知語長が０（制限なし）なので，下記のようにまとまって捉えることができます．
表層系 品詞 発音 未知語 __BOS__ None None None GAFA 名詞 * True に 助詞 ニ False 転職 名詞 テンショク False し 動詞 シ False たい 助動詞 タイ False 人生 名詞 ジンセイ False だっ 助動詞 ダッ False た 助動詞 タ False __EOS__ None None None
次にカタカナである「タピりたい」と「タピタピりたい」を形態素解析してみるとこんな感じです．カタカナのルールはグルーピングが１かつ未知語長が２であるため，長さ２で区切られています．本質的な解ではないですが，まぁなんとなくうまくいくケースがそれなりにある，という感じでしょうか．
表層系 品詞 発音 未知語 __BOS__ None None None タピ 名詞 * True り 助動詞 リ False たい 助動詞 タイ False __EOS__ None None None 表層系 品詞 発音 未知語 __BOS__ None None None タピ 名詞 * True タピ 名詞 * True り 助動詞 リ False たい 助動詞 タイ False __EOS__ None None None
最後に漢字である「卍解」を含む文を形態素解析してみるとこんな感じです．漢字はグルーピングなしで未知語長が２なのでうまくいきそうですが，漢字１文字が既知語として登場すること，動作タイミングが０であることから，うまく卍解できません．この例からも未知語処理が一筋縄ではいかないことが分かります．ゲームや漫画では特に未知語が多いですし，SNSなどでは言葉が砕けすぎていて形態素解析と実に相性が悪く，未だに研究の余地は大きく残っていると言えます．
表層系 品詞 発音 未知語 __BOS__ None None None 卍 名詞 マンジ False 解し 動詞 カイシ False たい 助動詞 タイ False __EOS__ None None None
速度計測
ここまでで一通り動くようになりました．せっかくなのでpure pythonで書かれたjanomeさんと速度対決をしてみましょう．適当におーぷん２ｃｈの文，1000文をtokenizeしたときの速度を比較してみると下記のようになりました．
| 実行時間 | |
|---|---|
| Janome | 1.2秒 |
| Taiyaki | 76.1秒 |
はい，圧倒的な遅さを誇ります．何故なんでしょう...Double-Arrayの構築が遅いのは多少理解できるのですが，推論時も遅いのは正直ようわかりませんね．Double-Arrayの検索部は，早くなるようなものではない気がするので，ラティスの構築や探索が下手なんでしょうか．これはfuture workにしておきます．
語彙追加と評価
語彙追加に関しては，今回はタイムアップだったので，次回の記事で書こうと思います．今回はmecab-ipadicで既にCRFで計算済みのコストをそのまま利用しましたが，Taiyakiではゼロから作ることを目標としているので，ここのコストも自前で計算したいです．そのために，現代日本語書き言葉均衡コーパス(BCCWJ)を買おうかなと思いましたが，流石に22万円するのでお財布には辛いです（誰か買って）．まだ方針は決めてないですが，京大ウェブ文書リードコーパスなどの無料で使えるものや，既存の形態素解析器が大規模文書に対して形態素解析した結果を擬似的なコーパスとして利用する方法（シルバーコーパス）などがあるかなぁと思っています．このあたり評価方法と含めて，現在検討中です．
まとめ
この記事では，ゼロから作った形態素解析器Taiyakiを教材に，最小コスト法に基づく形態素解析器の解説をしました．だいぶ長い記事になったので，ここまで読んでくださった方には感謝です．スライドなどを使って極力わかりやすくなるよう頑張りました．まだ語彙追加，評価，高速化など大事なところをやっていないですし，ライブラリ化するために必要なテストやパッケージングもできていないので，進捗出たらまた報告します．
明日の自然言語処理Advent Calendar２日目は，下記お二人になります．
coro65536さん
仮説検定のp値を理解する - Qiita
