Building a Tokenizer from Scratch

「食べさせられなかった」は文法的にどう分割されるか。

日本語のトークナイザーを書いていて直面した、数多の問題のひとつだ。答えは「食べ / させ / られ / なかっ / た」。原形は「食べる」。使役＋受身＋否定＋過去の四重連鎖。

トークナイザーと形態素解析

トークナイザーはテキストをトークン（検索やNLPで扱う単位）に分割する処理。形態素解析は言語学的な最小単位（形態素）に分割し品詞を判定する処理。suzumeはトークナイザーであり、厳密な形態素解析器ではない。ただし日本語では「スペースがないのでまず分割が必要」という点で、両者の守備範囲は大きく重なる。

MeCabなら辞書を引けば済む。「食べさせられなかった」がそのまま載っているわけではないが、活用パターンのデータが辞書に入っている。辞書サイズは20〜50MB。

わたしが書こうとしていたのはブラウザで動くトークナイザーだ。辞書50MBはありえない。では辞書なしで——文法規則だけで——活用形から原形を復元できるか。suzumeはその問いから始まった。

辞書で引く vs 文法で逆算する

日本語のトークナイズには大きく二つのアプローチがある。

ひとつは辞書ベース。MeCabやKuromojiがこの方式だ。何十万語の見出し語と活用形のパターンを辞書に格納し、テキストと照合する。辞書にあれば一発で解ける。辞書にない単語に出会うと弱い。

もうひとつは文法ベース。suzumeが採ったアプローチだ。辞書は最小限（助詞・助動詞・例外名詞で約400KB）にして、動詞や形容詞は文法規則で逆算する。

「食べさせられなかった」を例にとる。

MeCabは辞書を引く。suzumeは末尾から活用語尾を剥がしていく。

末尾の「た」を切る。「なかっ」は否定の助動詞「ない」が「た」に繋がるために変化した形（連用形）。「られ」は「られる」の連用形。「させ」は「させる」の連用形。残った「食べ」は一段動詞「食べる」の連用形。辞書を引かずに原形にたどり着く。

これがsuzumeの核心技術——逆活用解析だ。

活用のルールは有限だ

日本語の動詞活用は複雑に見えるが、ルールは有限だ。

動詞は大きく分けて3種類。五段活用（「書く」「読む」「飲む」）、一段活用（「食べる」「見る」）、不規則動詞（「する」「来る」）。それぞれの活用パターンは決まっている。

活用形	五段「書く」	一段「食べる」
未然形	書か	食べ
連用形	書き	食べ
終止形	書く	食べる
仮定形	書け	食べれ
意志形	書こ	食べよ

五段活用の「書く」は語尾が「か・き・く・け・こ」と五十音の行を移動する（だから「五段」）。一段活用の「食べる」は語幹「食べ」に語尾が直接くっつく。

助動詞の接続規則も決まっている。「れる・られる」は未然形に接続する。「た」は連用形に接続する。「ない」も未然形に接続する。このルールを知っていれば、末尾から順に剥がしていくことで、理論上はどんな活用チェインでも逆算できる。

理論上は。

実際にやってみたら

理論と実装の間には深い溝がある。

五段動詞の音便

五段動詞の連用形は「て」「た」に接続するとき、音が変わる。「書く」→「書いた」（イ音便）、「読む」→「読んだ」（撥音便）、「飛ぶ」→「飛んだ」（撥音便）。「書きた」ではなく「書いた」になる。

規則どおり	実際の日本語	音便の種類
書き + た → 書きた ✗	書いた ✓	イ音便
読み + た → 読みた ✗	読んだ ✓	撥音便
飛び + た → 飛びた ✗	飛んだ ✓	撥音便
持ち + た → 持ちた ✗	持った ✓	促音便

音便（おんびん）とは

発音しやすいように音が変化する現象。五段動詞が「て」「た」に接続するとき起きる。カ行（書く→書いた）とガ行（泳ぐ→泳いだ）はイ音便、マ行・バ行・ナ行（読む→読んだ、飛ぶ→飛んだ）は撥音便、タ行・ラ行・ワ行（持つ→持った、切る→切った）は促音便。

これを逆算するには、「いた」を見たら「イ音便＋た」の可能性をチェックし、「んだ」を見たら「撥音便＋た」の可能性をチェックする必要がある。単純な末尾マッチングでは処理できない。音便のパターンを活用表に組み込んで、逆引きテーブルを作った。

同じ末尾、違う活用

「切る」は五段活用（切ら・切り・切る・切れ・切ろ）。「見る」は一段活用（見・見・見る・見れ・見よ）。末尾が「る」の動詞は五段と一段の両方がありうる。

漢字で書かれていれば「切る」と「着る」は見た目で区別できる。問題はひらがなの「きる」だ。suzumeは両方の候補を生成し、スコアリングに委ねる。ただし漢字がない場合、文脈だけで解決するのは難しい。実際にsuzumeにひらがなの「きる」を食わせると、正しく分割できないケースがある。漢字という情報がどれだけ強力な手がかりか、実装して初めて実感した。

助動詞のチェイン爆発

「食べさせられなかった」は4段のチェインだが、日本語はもっと長くなる。「食べさせられたくなかったらしい」まで伸びると、使役＋受身＋希望＋否定＋過去＋推定の六重連鎖になる。

各段階で複数の解釈が生まれるので、候補の組み合わせは指数的に増える。全組み合わせを試すと爆発する。

ここでラティス＋ビタビが効く。すべての候補をラティスに載せて、ビタビアルゴリズムで最小コスト経路を一発で求める。組み合わせ爆発を、テキスト長と品詞数に比例する計算量に抑える。

ラティスとビタビ

テキストの各位置で「ここから始まる形態素の候補」をすべて列挙し、有向グラフ（ラティス）を構築する。各辺にコスト（単語の出現しやすさ＋前後の品詞の繋がりやすさ）を割り当て、ビタビアルゴリズムで文頭から文末への最小コスト経路を見つける。動的計画法なので、すべての組み合わせを試さずに最適解が得られる。

スコアリング——「自然な日本語」をコストで定義する

候補を生成しただけでは足りない。「切る」と「着る」のどちらが正しいか、決めるのはスコアリングだ。

suzumeのスコアリングは3つの信号を合算する。

単語コスト。品詞ごとの事前確率。名詞は最も出現しやすいので0.0、動詞は0.2、形容詞は0.3。辞書に載っている単語には-1.0のボーナス。1文字だけの漢字には+2.0のペナルティ（長い単語を優先するため）。

接続コスト。品詞間の遷移確率をバイグラムテーブルで管理する。「動詞連用形→助動詞」は-0.8（自然な接続）。「名詞→名詞」は+0.5（複合名詞、やや抑制）。suzumeは基本品詞14種ではなく、約55種のExtendedPOS（動詞の終止形、連用形、助動詞の種類ごと…）で接続コストを定義している。粒度を上げたぶん、不自然な繋がりを弾きやすい。

活用の信頼度。逆活用解析で推定した原形の確からしさ。音便パターンが一致していれば信頼度は高い。曖昧なケース（五段と一段の両方ありうる）は信頼度が下がり、コストが上がる。

最初はif/elseで接続規則を書いていた。ある時点でバイグラムテーブルに一本化した。手書きルールの山が、55×55の数値テーブルに変わった。コードはシンプルになり、チューニングは数値の調整だけで済むようになった。

「吾輩は猫である」という試練

精度テストに使うテキストを探していた。著作権が切れていて、標準的な日本語で、まとまった分量がある。夏目漱石がぴったりだと思った。

「吾輩は猫である」の冒頭を食わせた。分割ミスが大量に出た。明治の文語だった。

「ございます」の「ござ」は「ござる」という古語動詞の連用形だが、現代の活用テーブルには載っていない。「がお」が形容詞語幹として誤認識される。「をつかんで」の「を」と「つかんで」の境界がずれる。

各バグの修正は特殊ケースのハードコードではなく、汎用ルールとして実装した。たとえば「ござる」の活用を直すために導入した古語動詞パターンは、他の古風な表現（「参る」「申す」の古形）にも効いた。

テストケースは最終的に2201件になった。現代文、古文、口語、SNSテキスト、漱石、宮沢賢治。テストを増やすたびに、逆活用解析のルールが鍛えられていく。

400KBの文法で何ができて、何ができないか

最終的なWASMバイナリは約360KB（gzip後）。辞書込みで400KB。

文法ベースのアプローチが効くのは、活用規則に従う語彙——動詞、形容詞、助動詞——だ。これらは辞書に全パターンを載せなくても、規則から逆算できる。日本語の動詞活用は複雑だが有限であり、ルール化できる。

効かないのは、規則を持たない語彙——固有名詞、専門用語、新語——だ。「東京スカイツリー」は文法規則からは出てこない。これはコア辞書かユーザー辞書に頼る。

文法で読むか、辞書で読むか。人間も同じ二択を迫られている。知らない単語に出会ったとき、辞書を引く人と、文脈と語構成から推測する人がいる。suzumeは後者だ。推測が外れることもあるが、辞書を持ち歩かなくて済む。