こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。

LegalForce Researchでは、MeCab互換の形態素解析器Vibrato（ヴィブラ〰ト）を開発しています。プログラミング言語Rustで実装しており、高速に動作することが主な利点です。Vibratoはオープンソースソフトウェアとして以下のレポジトリで公開しています。

本記事では、Vibratoの技術仕様を解説します。以下のような方を読者として想定します。

自然言語処理の要素技術に興味のある方
データ構造・アルゴリズムに興味のある方
Rustでの自然言語処理に興味がある方

Vibratoについて
最小コスト法による形態素解析
- 単語ラティスの構築
- 最小コスト経路の計算
高速化の取り組み
- 辞書引きのキャッシュ効率化
  - 実装での注意点
- 連接コスト参照のキャッシュ効率化
実験的評価
開発の経緯・展望
まとめ

Vibratoについて

まずはじめにVibratoの簡単な紹介をします。

Vibratoは高速な形態素解析を提供するRust製ライブラリです。日本語における形態素解析とは、文を単語の単位に分割し、品詞や活用形を求める一連の処理です。例えば、Vibratoで「本とカレーの街神保町へようこそ。」という文を解析すると、以下のような単語列を予測します。

本  名詞,一般,*,*,*,*,本,ホン,ホン
と 助詞,並立助詞,*,*,*,*,と,ト,ト
カレー   名詞,固有名詞,地域,一般,*,*,カレー,カレー,カレー
の 助詞,連体化,*,*,*,*,の,ノ,ノ
街 名詞,一般,*,*,*,*,街,マチ,マチ
神保  名詞,固有名詞,地域,一般,*,*,神保,ジンボウ,ジンボー
町 名詞,接尾,地域,*,*,*,町,マチ,マチ
へ 助詞,格助詞,一般,*,*,*,へ,ヘ,エ
ようこそ    感動詞,*,*,*,*,*,ようこそ,ヨウコソ,ヨーコソ
。 記号,句点,*,*,*,*,。,。,。

このような操作を提供するソフトウェアを一般に形態素解析器といいます。形態素解析器は、MeCabやKuromoji、Sudachiなど、オープンソースソフトウェアに限っても色々な実装が存在します。その中で、Vibratoは以下のような特徴を持ちます。

MeCab互換: VibratoはRustによるMeCabの再実装です。MeCabと同じ解析結果¹を返すので置き換え可能です。²
高速解析: 実装の簡略化や最適化により、MeCabよりも高速に動作します。その技術詳細をこの記事で解説します。
Pure Rust: Vibratoはプログラミング言語Rustのみを使って実装されているので、Rustプロダクトに自然に導入できます。例えば、Rust製検索エンジン Tantivyで使用可能なtantivy-vibratoが公開されています。

最小コスト法による形態素解析

Vibratoの形態素解析は最小コスト法³というアルゴリズムに基づきます。ここでは、技術解説の事前準備として最小コスト法を紹介します。

最小コスト法は、以下の2ステップにより解を得るアルゴリズムです。

入力文に現れる単語をノードとしたグラフ構造（単語ラティス）を構築
単語本体や単語の並びの出現しやすさを表したコストの和が最小となる経路を探索

例えば、以下の図は「元気になった」という入力文から構築された単語ラティスです。⁴

BOSとEOSは、文の先頭と末尾を表すダミーのノードです。単語に対応するノードと、単語の並びの対応するエッジにはそれぞれコストが割り当てられています。ノードのコストは生起コストとよばれ、その単語の出現しやすさを表します。エッジのコストは連接コストとよばれ、その単語の並びの出現しやすさを表します。

単語ラティスの構築

単語と品詞の情報やコスト値を格納した辞書を持っているとして、単語ラティスは以下のような手順で構築されます。

入力文に現れる単語を列挙する（辞書引き）。
単語をノードとして、文の位置について隣り合うノード同士をエッジで繋ぐ。

特に辞書引きが最も時間の掛かる処理です。辞書引きは複数パターン検索ともよばれ、トライ木を使って効率的に解くことができます。トライ木を用いた複数パターン検索については過去の記事で詳しく解説していますので、そちらをご参照ください。

最小コスト経路の計算

単語ラティスのBOSからEOSまでを繋ぐ、生起コストと連接コストの和が最小となる経路を探索します。そして、その経路に対応する単語系列を解として報告します。

最小コスト経路は、ビタビアルゴリズム⁵を用いてエッジの数に線形の時間で計算できます。以下の例では、太線で示された経路が最もコストが最小となるので、この解は「元気/に/なっ/た」と判断されます。

ビタビアルゴリズムやコストの学習については、「形態素解析の理論と実装」（工藤拓, 2018）をご参照ください。

高速化の取り組み

最小コスト法は、辞書引きでのトライ木の探索、単語ラティスの探索など、何かとランダムアクセスが多くなりがちなアルゴリズムです。Vibratoでは、そのランダムアクセスによるキャッシュミスを緩和することを目的とし、参照の局所性を改善するような工夫を導入しています。⁶

辞書引きのキャッシュ効率化

1つ目は辞書引きのキャッシュ効率化についてです。

MeCabをはじめとする多くの形態素解析器では、辞書引きにダブル配列トライ⁷を採用しています。ダブル配列トライの代表的な実装としては、MeCabで使用されているDarts、その改良であるDarts-clone、そのRust移植でありsudachi.rsやLinderaで使用されているYadaなどがあります。

一方Vibratoでは、Crawdadというダブル配列トライ辞書ライブラリを採用しています。

github.com

Crawdadは日本語などのマルチバイト文字列の処理に特化した実装で、その他との違いは文字列の表現方法です。

Dartsなど多くのトライ実装では、文字列をそのデータ表現のバイト列として扱います。この方法は、文字列のエンコードに関わらずバイト列として処理することができるので、実装が容易で汎用的に利用できるという利点があります。

一方Crawdadでは、文字列をバイト単位ではなくUnicodeのコードポイント単位（文字単位）に分解し、コードポイント値の系列として扱います。この方法は、日本語などのマルチバイト文字を扱うときに、バイト列と比べ文字列長が短くなるという利点があります。トライの探索では文字列長に比例した回数のランダムアクセスが必要となるので、文字列長が短くなるのはキャッシュ効率に関して利点です。

単語「元気」と「活気」をトライで表現した例を以下に示します。上図がUTF-8符号をバイト列として表現した例、下図がコードポイント値の系列として表現した例です。

日本語の多くの文字はUTF-8で3バイトを使って表現されるので、上図では文字当たり3つの遷移が定義されています。一方で下図は文字当たり1つの遷移で済みます。このように、文字単位で遷移を定義すればランダムアクセスの回数を3分の1に削減できます。

実装での注意点

コードポイント値を使う場合、文字の種類数（アルファベットサイズ）が大きくなる点に注意する必要があります。バイト単位では 0x00 から 0xFF までの高々256種類のラベルしか使いませんが、コードポイント値は U+0000 から U+10FFFF までのおよそ110万種類のラベルを扱います。

アルファベットサイズが大きいダブル配列トライは、素朴に実装すると構築が低速化したりメモリ使用量が大きくなることが知られています。そこでCrawdadでは、文字の出現頻度の偏りを利用し、コード値を頻度順に割り当て直します。多くのコード値が小さい値になることで、これらの問題が緩和されることが経験的に知られています。⁸

連接コスト参照のキャッシュ効率化

2つ目は連接コスト参照のキャッシュ効率化についてです。

事前知識

改めて、連接コストとは単語ラティスのエッジに付随したコストです。左側ノードの素性情報と右側ノードの素性情報のペアによって決定されます。⁹ 例えば、以下の連接コスト 2551 は「動詞」と「助動詞」のペアによって決定します。

より具体的には、素性には左文脈IDと右文脈IDが割り当てられ、それらIDのペアによって連接コストは決まります。ここで、左文脈IDはその単語の左側のエッジについてのID、右文脈IDはその単語の右側のエッジについてのIDです。

本記事では、左文脈IDの集合を $X=\{0,1, \dots ,|X|-1\}$ 、右文脈IDの集合を $Y=\{ 0,1,\dots,|Y|-1 \}$ と定義し、文脈IDペア $(x,y) \in X \times Y$ の連接コストを $C(x,y)$ と表記します。例えば、上の例を文脈IDを使って改めて書き直すと、以下のようになります。

連接コストは $|X| \times |Y|$ の連接表に保存され、文脈IDを使って参照されます。

単語ラティスの探索では、左文脈ID $x$ を固定し、右文脈ID $y$ についてループを回します。そのため、連接コスト値

$\displaystyle C(x,0),C(x,1),\dots,C(x,|Y|-1)$

がメモリ上で連続するように連接表を実装することで、参照の局所性が改善します。

例えば、以下のように右文脈ID $y$ についてループを回す場合、青枠で囲まれた行がメモリ上で連続するように、行指向で連接表を実装すると参照の局所性が改善します。

連接表のボトルネック

行指向で連接表を実装しても、依然として文脈IDによる頻繁な連接表へのランダムアクセスはボトルネックです。これは連接表が大きい場合に顕著です。

例えば、MeCab IPADIC v2.7.0では、 $|X|=|Y|=1316$ で連接表のサイズは3.3 MiBです。この程度のサイズであれば、現代の計算機環境なら十分キャッシュに載りますので、ランダムアクセスはそこまで大きなボトルネックとはならないでしょう。

一方、現代書き言葉UniDic v3.1.0では、 $|X|=15388, |Y|=15626$ と非常に細かく素性が定義されていて、連接表のサイズは459 MiBにもなります。記事の後半で実験結果を示しますが、実際にこの巨大な連接表は重大な速度低下を引き起こします。

改善のアイディア

Vibratoの改善のアイディアはシンプルで、よく使われる文脈ID順に若いIDを割り当て直し、よく参照される連接コストがメモリ上で近接するように文脈IDを修正します。以降では、この再割り当てを頻度順IDマッピングとよびます。文脈IDの使用頻度に大きな偏りがある場合、頻度順IDマッピングは参照の局所性を改善します。

例えば、ある左文脈ID $x_i$ について、いくつかの右文脈ID $y_j$ で連接コスト値を参照する様子を以下に示します。

標準の文脈IDを使用した場合、遠く離れたメモリを参照しキャッシュミスが発生します（上図）。しかし、これらの右文脈ID $y_j$ がよく使用されるものだった場合、頻度順IDマッピングにより連接コスト値が近接して配置されるので、参照の局所性が改善します（下図）。

Vibratoでは、訓練コーパスを用いて左文脈ID $x_i$ と右文脈 $y_j$ のそれぞれの使用頻度を算出します。そして、その頻度の多い順に若いIDを割り当てます。

実験的評価

上記した高速化技法について、実験による結果を示します。

実験設定

実験に使用したマシン環境は以下の通りで、実験はすべてシングルスレッドで行いました。

CPU: Intel Core i9-12900K (L3: 30MB, Cache-line: 64B, 16 Core, 3.2GHz-5.2GHz)
RAM: 64GB (2×32GB, DDR5)
OS: Ubuntu 22.04

形態素解析用の辞書は、以下の4種類を評価しました。

mecab-ipadic (v2.7.0)
- 単語数: 392,126
- 連接表: 1316×1316, 3.3 MiB
mecab-ipadic-neologd (2020-09-10)
- 単語数: 4,668,394
- 連接表: 1316×1316, 3.3 MiB
unidic-mecab (v2.1.2)
- 単語数: 756,463
- 連接表: 5981×5981, 68 MiB
unidic-cwj (v3.1.0)
- 単語数: 879,222
- 連接表: 15388×15626, 459 MiB

テキストコーパスにはBCCWJ (v1.1)を使用しました。Vibratoの訓練にはコアデータ60,004文を用いました。形態素解析の実行速度の評価には、サブコーパス13カテゴリから各1万文ずつをランダムに抽出した計13万文を使用しました。¹⁰

Vibratoの解析時間を計測したコードはここにあります。

辞書引きのキャッシュ効率化についての評価

バイト単位・文字単位のそれぞれのスキームでダブル配列トライを構築した場合の解析速度を比較します。以下のライブラリをそれぞれVibratoで使用し、評価データの解析に要した時間を計測しました。

バイト単位: Yada v0.5.0
文字単位: Crawdad v0.3.0

頻度順IDマッピングは適用していません。評価データ13万文の解析に要した時間を下の表に報告します。結果は10回試行した平均です。右端の列は「バイト単位」から「文字単位」への変化率を表します。¹¹

辞書	バイト単位 [ms]	文字単位 [ms]	(変化率)
mecab-ipadic	558	489	−12.3%
mecab-ipadic-neologd	739	649	−12.1%
unidic-mecab	839	749	−10.6%
unidic-cwj	1284	1210	−5.8%

すべてのケースで文字単位が高速です。unidic-cwjを除いて、10%以上の改善が見られます。一方で、unidic-cwjでは5.8%の改善に留まりました。巨大な連接表を持つunidic-cwjでは、辞書引きよりも連接コスト参照の方がボトルネックになることが原因です。

連接コスト参照のキャッシュ効率化についての評価

いくつかの段階に分けて、頻度順IDマッピングの性能を評価します。ダブル配列トライは共通して文字単位を採用しています。

文脈ID使用頻度の偏り

まず、文脈IDの使用頻度に偏りがあるのかを調査します。各辞書について、訓練用テキストを解析したときの文脈IDの使用頻度を算出しました。

右文脈IDの使用頻度上位256件について、その割合を以下に示します。32件ずつの合計をプロットしています。（左文脈IDの結果も大きく変わらないので省略します。）

文脈IDの使用頻度には大きな偏りがあることがわかります。

例えば、文脈IDが1.5万種類も定義されているunidic-cwjにおいても、上位32件が使用される割合は47%です。連接コスト値を2バイトで表現すると、64バイトのキャッシュラインには32個の値が載ります。これはつまり、頻度順IDマッピングによって、おおよそ2回中1回は同じキャッシュラインを参照することを意味します。キャッシュ効率化による改善が期待できそうです。

ボトルネックの調査

続いて、実際に連接表へのアクセスがボトルネックなのかを調査します。各辞書について、以下の2つの場合を比較します。

従来通り連接表にアクセスし、連接コストを用いて解析した場合
連接表へのアクセスを完全に除外し、連接コストはすべて0として解析した場合

連接コストが異なるので解析結果は変わりますが、定数時間の配列参照を取り除いただけなので計算量は同じです。

評価データ13万文の解析に要した時間を以下に示します。結果は10回試行した平均です。右端の列は、「連接表有り」から「連接表無し」への変化率を示します。

辞書	連接表有り [ms]	連接表無し [ms]	(変化率)
mecab-ipadic	489	410	−16.1%
mecab-ipadic-neologd	649	548	−15.5%
unidic-mecab	749	509	−32.0%
unidic-cwj	1210	522	−56.9%

配列への参照を取り除いただけの簡単な修正でしたが、解析時間に大きな差が見られました。特にunidic-cwjでは57%も解析時間が短縮されています。辞書引きなど他の処理もある中で、巨大な連接表への参照がいかにボトルネックであるかが伺えます。

これらの結果は、頻度順IDマッピングを適用した場合の変化率の下限になります。

頻度順IDマッピングの評価

頻度順IDマッピングを適用することにより、連接表のボトルネックが実際にどの程度解消されるかを調査します。以下がその結果です。前と同じく、結果は10回試行した平均です。右端の列は、「マッピング無し」から「マッピング有り」への変化率を示します。

辞書	マッピング無し [ms]	マッピング有り [ms]	(変化率)
mecab-ipadic	489	472	−3.4%
mecab-ipadic-neologd	649	623	−4.0%
unidic-mecab	749	658	−12.2%
unidic-cwj	1210	779	−35.6%

頻度順IDマッピングにより、unidic-cwjでの解析速度が36%も改善しました。この結果は、前述した分析結果に裏付けされています。一方で、連接表の小さなipadicでは大きな改善は確認されませんでした。

訓練データに関する調査

上記した実験結果は、BCCWJのコアデータ6万文、つまり均衡コーパスを頻度順IDマッピングの訓練に使用した場合のものです。ここでは、解析テキストのドメインに特化した訓練データを用いることで、頻度順IDマッピングの性能が変わるのかを調査します。

評価用テキストのBCCWJサブコーパスは、新聞（PN）や法律（OL）などの13カテゴリから成ります。実験では、各カテゴリから1万文をランダムサンプリングし使用しています。各カテゴリについて、以下の2つの方法でマッピングを訓練し、解析時間を比較しました。

均衡データ: コアデータからサンプルした1万文で訓練
カテゴリ別: 各カテゴリの評価用テキスト1万文について5分割交差検証

13カテゴリについて、評価データ1万文の解析に要した時間を以下に示します。使用した辞書はunidic-cwjです。数値は10回試行した平均です。

訓練データをドメインに特化しても、解析時間は大きく変化しないことがわかります。合計では、676ミリ秒から672ミリ秒へと改善していますが、その差は僅かです。

コアデータといくつかのサブコーパスで頻繁に使用された右文脈ID上位10件は以下の通りです。右文脈IDはunidic-cwjで定義されている標準のものです。

ランク	コアデータ	新聞 (PN)	書籍 (LB)	Yahoo!知恵袋 (OC)
1	850	850	850	850
2	6742	6742	6742	6742
3	9663	9663	9663	9663
4	11540	11540	11540	11540
5	14497	14497	14497	14497
6	2250	2250	2250	2250
7	11383	11383	11383	11383
8	6980	6980	14775	14775
9	12392	12392	12392	2410
10	14775	3917	2410	12392

上位7件まではどのコーパスでも同一で、カテゴリによって使われるIDに大きな差は無いことがわかります。頻繁に使用されている右文脈IDに対応した素性列は以下のとおりです。

850 名詞,普通名詞,サ変可能,*,*,*,*,*,*,*,*,*
6742 名詞,固有名詞,人名,一般,*,*,*,*,*,*,*,*
9663 名詞,固有名詞,地名,一般,*,*,*,*,*,*,*,*
11540 名詞,固有名詞,一般,*,*,*,*,*,*,*,*,*
14497 名詞,普通名詞,一般,*,*,*,*,*,*,*,*,*
2250 感動詞,一般,*,*,*,*,*,*,*,*,*,*
11383 名詞,普通名詞,一般,*,*,*,*,*,和,*,*,*,1,C3,*
6980 名詞,普通名詞,一般,*,*,*,*,*,漢,*,*,*,1,C3,*
12392 接尾辞,名詞的,一般,*,*,*,*,*,漢,*,*,*,*,C3,*
14775 副詞,*,*,*,*,*,*,*,和,*,*,*,1,*,*
3917 名詞,固有名詞,人名,名,*,*,*,*,固,*,*,*,1,*,*
2410 感動詞,一般,*,*,*,*,*,*,和,*,*,*,1,*,*

この結果から、頻繁に使用されているIDは品詞などのごく一部の情報によって識別可能な単語に割り当てられており、しかも、そのような単語はドメインを問わずコーパスの大部分を占めているということが分かります。

これらの結果は、「幅広いドメインのテキストを解析するために、均衡データから訓練したマッピングを一つ持っておけば十分である」ということを示唆しています。マッピング適用済みの辞書を配布すればよいので、運用上ポジティブな結果と言えます。

主結果：キャッシュ効率化による変化率

改めて、本記事で提案した辞書引きと連接コスト参照のキャッシュ効率化による最終的な変化率を以下に示します。評価データ13万文の解析に要した時間です。

辞書	改善前 [ms]	改善後 [ms]	(変化率)
mecab-ipadic	558	472	−15.3%
mecab-ipadic-neologd	739	623	−15.6%
unidic-mecab	839	658	−21.6%
unidic-cwj	1284	779	−39.3%

他の形態素解析器との比較

Vibrato (v0.1.2) と他の形態素解析との解析時間を比較します。

比較手法

Vibratoと同じ最小コスト法を使用したライブラリとして、以下の3種類を比較しました。

MeCab (2020-09-14)
Lindera (v0.16.1)
sudachi.rs (v0.6.4-a1)

VibratoとMeCabは、辞書にmecab-ipadic (v2.7.0)とunidic-cwj (v3.1.0)を使用しました。Linderaは、ライブラリでサポートされているlindera-ipadicとlindera-unidicの2種類を評価しました。sudachi.rsは、辞書にSudachiDict-Coreを使用しました。Vibratoの訓練データには、引き続きBCCWJのコアデータ6万文を用いました。

点予測法を用いた単語分割器とも比較しました。使用したライブラリは以下の通りです。

Vaporetto (v0.5.1)
KyTea (2020-04-03)
rust-tinysegmenter (v0.1.1)

VaporettoとKyTeaは、KyTea Modelsで配布されている圧縮SVMモデル (jp-0.4.7-5) を使用しました。

最小コスト法と点予測法はアルゴリズムが異なり、提供する機能も違うので、あくまで参考記録だという点にご留意ください。点予測法の詳細については、過去の記事をご参照ください。

実験結果

BCCWJサブコーパス13万文の解析に要した時間を以下に報告します。数値は100回試行した平均です。

最小コスト法ではVibratoが最速です。MeCabと比較しても、2倍以上の速度性能が確認できます。

開発の経緯・展望

Vibratoを開発する以前は、既存のライブラリを修正することで高速化に貢献するつもりでした。形態素解析器は社内外問わず至る所で使われているので、「高速化されたら少なからず誰かには喜ばれるだろう」と、筆者が思い立って個人的に着手したのが始まりです。しかし、作り込まれたライブラリに手を加えるのは中々に大変で、個々のアイディアを解析するのにも苦労しました。そこで、フルスクラッチで最小構成の最小コスト法を実装し、それを通してアイディアと実験結果を提供する方針に切り替えました。結果として開発に至ったのがVibratoで、Vaporettoなどと同様にdaac-tools以下で管理することにしました。

そういった経緯から、Vibratoはできる限り簡潔に実装することを心がけており、必要以上に機能を追加するつもりもありません。結果として、高い速度性能を維持できているので、大規模なテキストでの前処理などに活用して頂けます。一方で、形態素解析器はそれぞれに特色があり、意図する応用も異なるので、Vibratoだけが高速になってもあまり建設的だとは思いません。Vibratoで試されるアイディアを通して、他の形態素解析器の高速化にも貢献できるのが最善だと思っています。そのために、また何かアイディアがあればVibratoで試し、積極的に結果を発信していければと思っています。

まとめ

本記事では、Rust製形態素解析器Vibratoと、その技術詳細について解説しました。Vibratoはオープンソースソフトウェアなので、自由な利用はもちろん、改善の依頼やコードの提供も受け付けております。

また LegalForce Research では、コーディングが好きなソフトウェアエンジニアや研究が好きなリサーチエンジニアを募集しています。主に自然言語処理の分野でソフトウェアを開発したい方や、大量の文書を利用した研究をしたい方の応募をお待ちしております。

最小コスト値が同着となる場合を除き、BCCWJ全文について解析結果が同じとなることを確認しています。↩
v0.1.2では1-best解しか対応しておらず、n-best解やソフト分かち書きなどは未対応です。↩
久光徹, 新田義彦. 接続コスト最小法による形態素解析の提案と計算量の評価について. 電子情報通信学会技術研究報告, 1990↩
「形態素解析の理論と実装」（工藤拓, 2018）の図例を参考にしました。↩
Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 1967↩
キャッシュミスや参照の局所性については、例えばこの資料などをご参照ください。↩
Aoe. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, 1989.↩
Liu et al., Compression methods by code mapping and code dividing for chinese dictionary stored in a double-array trie. IJCNLP, 2011↩
簡単のために、本記事の例では素性として品詞を扱います。↩
BCCWJのコアデータ、サブコーパスの仕様については、公式ドキュメントをご参照ください。↩
変化率は (変化先−変化元)/変化元 で算出します。↩

LegalOn Technologies Engineering Blog

LegalOn Technologies 開発チームによるブログです。

MeCab互換な形態素解析器Vibratoの高速化技法