# 最小コスト法に基づく形態素解析における CPU キャッシュの効率化

神田峻介 1 赤部晃一 1 後藤啓介 1 小田悠介 ${ }^{2}$
${ }^{1}$ LegalOn Technologies Research ${ }^{2}$ 東北大学 データ駆動科学・AI 教育研究センター
\{shunsuke.kanda, koichi.akabe, keisuke.goto\}@legalontech.jp
yusuke.oda.c1@tohoku.ac.jp

## 概要

最小コスト法に基づく形態素解析において、木の 探索やコスト行列の参照により発生するランダムア クセスは、CPU キャッシュ効率低下の原因となる。本稿では、参照の局所性を改善するデータ構造を提案し、解析速度の改善を図る。実験の結果、提案法 を適用しなかった場合と比べ、提案法は $40 \%$ 程度の 時間短縮を達成した。また、提案法を組み込んだ形態素解析器 Vibrato $^{1)}$ を新たに開発し、既存のソフト ウェアよりも高速に動作することを実証した。

## 1 はじめに

形態素解析は、自然言語を大力とし、形態素の列 を返す処理である。日本語の情報検索やテキストマ イニングなどの自然言語処理において、形態素解析 は重要な前処理である。形態素解析を実現する代表的な手法の 1 つに最小コスト法 [1] があり、MeCab [2] や Sudachi [3] などの形態素解析器で利用されて いる。

最小コスト法の時間的ボトルネックの一つに、辞書の肥大化に伴う CPU キャッシュ効率の低下が挙 げられる。単語列挙のための木構造の探索や、コス 卜計算のための行列参照では、メモリ上のランダム アクセスが頻繁に発生する。巨大な辞書では、この ランダムアクセスがキャッシュミスを引き起こし、速度低下の原因となる。

本稿では、参照の局所性の良いデータ構造を設計し、キャッシュ効率を改善することで最小コス トの高速化を達成する。IPADIC [4] や Neologd [5]、 UniDic [6, 7] を使った実験により、その有効性を実証する。実験の結果、提案法を適用しなかった場合 と比べて、提案法は $40 \%$ 程度の高速化を達成した。


図 1 入力文「元気になった」についての形態素ラティ ス。太線はコストの和が最小となる経路を表す。

また、提案法を実装した形態素解析器 Vibrato を 新たに開発した。実験により、Vibrato は MeCab の 2 倍以上の速度性能であることを実証する。

## 2 最小コスト法

## 2.1 アルゴリズム

最小コスト法は、以下の手順により入力文から形態素列2)を得るアルゴリズムである。

1. 入力文に現れる形態素をノードとしたグラフ構造（形態素ラティス）を構築

2. コストが最小となる経路を探索し、対応する形態素列を出力

図 1 に入力文「元気になった」から構築された形態素ラティスを示す。BOS と EOS は、文の先頭と 末尾を表すダミーのノードである。形態素に対応す るノードと形態素の並びの対応するエッジにはコス トが割り当てられる。ノードのコストは、その形態素自体の出現しやすさを表す。エッジのコストは、 その形態素の並びの出現しやすさを表す。以降で は、形態素辞書やコスト値は所与として各手順を説明する。

形態素ラティスの構築 入力文が与えられたと き、形態素ラティスは以下のように構築される。

2）本稿では、辞書のエントリを形態素と呼ぶ。

1. 入力文に現れる形態素を列挙（辞書引き）

2. 形態素をノードとして、文の位置について隣り 合うノード同士をエッジで連結

辞書引きはトライ [8] という木構造を使って効率的に計算できる。詳しくは 3 節で解説する。

経路の探索形態素ラティスの BOS から EOS ま でを繋ぐ、コストの和が最小となる経路を探索す る。そして、その経路に対応する形態素列を解とし て出力する。例えば、図 1 では太線の経路が該当す る。そのような経路は、ビタビアルゴリズム [9]を 用いてエッジ数に線形の時間で計算できる。

## 2.2 高速化の方針

本研究では、最小コスト法のボトルネックは以下 の 2 点であると指摘し、これらを解消することで解析速度の改善を試みる。

$\cdot$辞書引きでのトライの探索
- 経路探索中のコストの参照

これらに共通する点は、メモリ上の頻繁なランダ ムアクセスである。巨大な辞書では、このランダム アクセスがキャッシュミスを引き起こし、速度低下 の原因となる。そこで、それぞれに参照の局所性が 良いデータ構造を設計する。詳しくは、 3 節と 4 節 で解説する。

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

## 3.1 事前知識

多くの形態素解析器では、トライ [8]を使った共通接頭辞検索により辞書引きを実現する。トライと は文字列の接頭辞を併合して構築される木構造で あり、図 2 に見られるようにエッジにラベルを付随 したオートマトンの一種である。共通接頭辞検索と は、あるクエリ文字列の接頭辞として現れる登録文字列を列挙する操作であり、文字を使って根から ノードを遷移することで実現される。形態素をトラ イに登録し、入力文の全ての開始位置から共通接頭辞検索を実行することで辞書引きは実現される。

トライを表現するデータ構造としてはダブル配列 [10] が広く用いられている。ダブル配列とは、ノー ドからノードへの探索を定数時間で実現する高速な データ構造である。入力文の長さを $N$ 、登録形態素 の最大長 $K$ としたとき、ダブル配列を使った場合の 辞書引きの実行時間は $O(N K)$ である。

図 2 形態素「元気」「活気」を登録したトライ。文字列 のエンコードが Unicode である場合の、上図は Bytewise で表現した例、下図は Charwise で表現した例を示す。

## 3.2 背景と問題点

ダブル配列の代表的な実装として、Darts ${ }^{3}$ や Darts-clone ${ }^{4}$ があり、MeCab や Sudachi などで用いら れている。これらの共通点として、文字列をその データ表現のバイト列として扱う点が挙げられる。 この方法を Bytewise と表記する。図 2 の上部に例 を示す。

Bytewise の利点は、文字列のエンコードに関わら ずバイト列として処理できることと、エッジラベル の種類数の上限が 256 に定まることである。これら は実装の汎用性や容易さに関係する。

Bytewise の欠点は、日本語などのマルチバイト文字を扱う場合にバイト列が長くなることである。図 2 の例では、Unicode で符号化された長さ 2 の形態素「元気」が、長さ 6 の UTF-8 バイト列として表現されている。これは「元気」を検索するときに 6 回のランダムアクセスが必要となることを意味し、 キャッシュミス増加の原因となる。

## 3.3 改善案

文字列を Unicode のコードポイント値の系列とし て処理する。この改善案を Charwise と表記する。図 2 の下部に例を示す。

日本語の多くの文字は UTF-8 で 3 バイトを使って 表現される。そのような文字について、Charwise で は Bytewise に比べランダムアクセスの回数を 3 分の 1 に削減できる。ダブル配列では定数時間でノード の探索ができるので、計算量にも影響は無い。

Charwise の実装上の注意点は、エッジラベルの種類数が大きくなる点である。コードポイント值は U+0000 から U+10FFFF までの 110 万種類を扱う。そ のようなダブル配列は、素朴に実装すると構築速度 やメモリ効率が低化する [11]。そこで、コード值を

3) http://chasen.org/ taku/software/darts/

4) https://github.com/s-yata/darts-clone
頻度順に割り当て直すことで、多くのコード値が小 さい値になるように修正する。自然言語において文字の出現頻度には偏りがあるため、この修正で問題 が解消されることが経験的に知られている [11]。

## 4 コスト参照のキャッシュ効率化

## 4.1 事前知識

形態素ラティスのエッジに付随したコストを連接 コストとよぶ。連接コストは左側と右側ノードの素性情報のぺアによって決定される。具体的には、形態素には左文脈 ID と右文脈 ID が割り当てられ、そ れら IDのペアによって連接コストは決定される。

本稿では、左文脈 ID の集合を $X=\{0,1, \ldots,|X|-$ 1\}、右文脈 ID の集合を $Y=\{0,1, \ldots,|Y|-1\}$ と定義 する。連接コストは $|X| \times|Y|$ の連接表 $M$ に保存さ れ、文脈 $\operatorname{ID~ペア~}(x, y) \in X \times Y$ の連接コスト値は表 $M$ の $(x, y)$ 成分 $M[x, y]$ に格納される。 $M$ は単純な 二次元配列で実装され、 $M[x, y]$ には値 $x, y$ を使っ て定数時間でアクセスできる。

## 4.2 背景と問題点

現代書き言葉 UniDic [7] では素性を詳細に設計し ており、結果として連接表が肥大化している。例え ば、IPADIC v2.7.0 では $|X|=|Y|=1,316$ で連接表の サイズは高々 $3.3 \mathrm{MiB}$ である。5)それに対し、UniDic v3.1.0 では $|X|=15,388,|Y|=15,626$ で連接表のサ イズは $459 \mathrm{MiB}$ にもなる。事前実験（付録 A）では、解析時間は連接表のサイズに比例して増加する傾向 が見られており、参照の局所性の悪化が解析速度の 低下の原因になると考察される。

## 4.3 改善案

訓練コーパスを用いて文脈 ID の使用頻度を収集 し、よく使用される順に若い文脈 IDを割り当て直 す。この方法により、頻繁に使用される連接コスト 値がメモリ上で近接する。使用頻度に大きな偏りが ある場合、参照の局所性が改善する。図 3 に例を 示す。本稿では、標準の文脈 ID を使用する場合を Default、頻度順にマッピングする場合を Mapped と 表記する。


頻繁に使われる連接コスト

図 3 文脈 IDを頻度順に割り当て直した例。ある左文脈 ID $x_{i}$ に対応する行と、 $x_{i}$ について右文脈 ID $y_{1}, y_{2}, y_{3}$ の順 でコスト値を参照した様子を図示している。 $x_{i}^{\prime}, y_{j}^{\prime}$ は頻度順に割り当て直された文脈 IDを表す。 $y_{1}, y_{2}, y_{3}$ が頻繁に 使用される文脈 IDであった場合、 $y_{1}^{\prime}, y_{2}^{\prime}, y_{3}^{\prime}$ は小さい値と なる。つまり、その連接コスト值は行の先頭付近に密集 し、参照の局所性は改善する。

表 1 辞書の統計

## 5 実験

## 5.1 実験設定

形態素解析用の辞書は以下の 4 種類を評価した。
- ipadic-mecab (v2.7.0) [4]
- ipadic-neologd (2020-09-10) [5]
- unidic-mecab (v2.1.2) [6]
- unidic-cwj (v3.1.0) [7]

文章コーパスには BCCWJ v1.1 $[12,13]$ を使用し た。マッピングの訓練にはコアデータ $60 \mathrm{k}$ 文を使用 した。形態素解析の速度評価には、サブコーパスか らランダムに抽出した $100 \mathrm{k}$ 文を使用した。

手法の実装にはプログラミング言語 Rust を用 いた。コンパイルに使用した rustc はv1.63.0であ り、最適化フラグは opt-level=3 である。計算機環境は、Intel Core i9-12900K @ 3.2-5.2GHz CPU (Cacheline: 64B, L1d: 640KiB, L2: 14MiB, L3: 30MiB), 64GiB RAM であり、OS は Ubuntu 22.04 である。実験は全 てシングルスレッドで実施した。ダブル配列につ いて、Bytewise の実装には Yada v0.5.06)を用いた。

6) https://github.com/takuyaa/yada
表 2 各手法を適用した場合の解析時間 [ms]。括弧内の 数値は Bytewise+Default からの変化率を表す。

 &  &  \\

mecab-neologd & 538 & $479(-11.1 \%)$ & $467(-13.3 \%)$ \\
unidic-mecab & 616 & $567(-8.0 \%)$ & $499(-19.0 \%)$ \\
unidic-cwj & 1,012 & $949(-6.3 \%)$ & $587(-42.1 \%)$ \\

表 3 L1 キャッシュへのデータ読み込みにおけるキャッ シュミス回数 $\left[10^{6}\right]$ 。括弧内の数値は Bytewise+Default か らの変化率を表す。

 &  &  \\

ipadic-neologd & 86.0 & $79.9(-7.1 \%)$ & $56.3(-34.6 \%)$ \\
unidic-mecab & 136.1 & $130.3(-4.3 \%)$ & $71.4(-47.5 \%)$ \\
unidic-cwj & 231.8 & $226.3(-2.4 \%)$ & $104.6(-54.9 \%)$ \\

Charwise の実装には Crawdad v0.3.07)を用いた。

## 5.2 提案法の分析

提案法の Charwise と Mapped を用いた場合の解析速度を評価する。評価データ $100 \mathrm{k}$ 文の解析に要し た時間を表 2 に示す。結果は 10 回試行した平均で あり、結果中に示す「変化率」は、变化先-変化元 で算出した值である。

文脈 ID が Default の場合での Bytewise と Charwise の解析時間を比較する。全ての辞書で Charwise が 高速であり、IPADIC では $10 \%$ 以上の改善が確認さ れた。一方で、巨大な連接表を持つ unidic-cwjでは、相対的にコスト参照のボトルネックの方が大きく、 6.3\%の改善に留まった。

続いて、文脈 ID の割り当てを Mapped に変更した 場合と比較する。全ての辞書で Mapped が高速であ り、特に連接表が最も大きい unidic-cwj では $42.1 \%$ の大きな改善が確認された。

表 3 に、評価データ $100 \mathrm{k}$ 文の解析時に発生した、 L1 データキャッシュへの読み込み時のキャッシュ ミス回数を示す。計測には perf コマンドを使用し、結果は 100 回試行した平均である。

全ての場合において、提案法によりキャッシュ ミスの回数が削減している。Charwise 適用時には ipadic-neologd で、Mapped 適用時には unidic-cwj で 改善率が最も大きく、提案法が巨大な辞書について 効果的であることが確認できる。

これらの結果から、最小コスト法に基づく形態素解析器において、辞書引きとコスト参照のキャッ


表 4 形態素解析器の比較実験の結果。

シュ効率は解析速度に大きな影響を与えることが 確認された。特に連接表が巨大な場合、コスト参照 にかかる時間の割合が大きく、コスト参照のキャッ シュ効率改善が解析の高速化に有効であった。

## 5.3 形態素解析器の比較

提案法の実装である Vibrato の速度性能を、既存 の形態素解析器と比較し評価する。比較したソフト ウェアは以下の 4 種類である。
- Vibrato v0.1.2
- MeCab v0.996 ${ }^{8}$
- Lindera v0.16.19)
- sudachi.rs v0.6.4-a $1^{10)}$

Vibrato と MeCab は ipadic-mecab と unidic-cwjを用 いて評価した。Lindera はライブラリでサポートさ れている ipadic-mecab と unidic-mecabを用いて評価 した。 sudachi.rs は形態素解析器 Sudachi [3] の Rust 移植であり、辞書には SudachiDict-core ${ }^{11)}$ を用いて評価した。計測には tokenizer-speed-bench ${ }^{12)}$ を用いた。

表 4 に結果を示す。IPADIC とUniDic の両方の ケースについて、Vibrato が最速であることが確認 できた。二番目に高速な $\mathrm{MeCab}$ と Vibrato を比較し て、IPADIC で 2.1 倍、UniDic で 2.3 倍高速である。

## 6 おわりに

本稿では、形態素解析の高速化を目的とし、最小 コスト法のキャッシュ効率化技法を提案した。実験 により提案法の有効性を実証した。また、提案法を 実装した形態素解析器 Vibrato を開発し、その速度性能を実証した。今後は機能面と性能面について、 Vibrato のさらなる改良を予定している。


## 参考文献

[1] 久光徹, 新田義彦. 接続コスト最小法による日本語形態素解析. 全国大会講演論文集, 人工知能及び認知科学, pp. 1-2, 1991.

[2] Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto. Applying conditional random fields to japanese morphological analysis. In Proceedings of the $\mathbf{2 0 0 4}$ conference on empirical methods in natural language processing, pp. 230-237, 2004.

[3] Kazuma Takaoka, Sorami Hisamoto, Noriko Kawahara, Miho Sakamoto, Yoshitaka Uchida, and Yuji Matsumoto. Sudachi: a japanese tokenizer for business. In Proceedings of the 11th International Conference on Language Resources and Evaluation, 2018.

[4] Masayuki Asahara and Yuji Matsumoto. ipadic version 2.7.0 User's Manual. https://ja.osdn. net/projects/ ipadic/docs/ipadic-2.7.0-manual-en. pdf, 2003.

[5] 佐藤敏紀, 橋本泰一, 奥村学. 単語分かち書き辞書 mecab-ipadic-neologd の実装と情報検索における効果的な使用方法の検討. 言語処理学会第 23 回年次大会 (NLP2017), pp. NLP2017-B6-1. 言語処理学会, 2017.

[6] 伝康晴, 小木曽智信, 小椋秀樹, 山田篤, 峯松信明, 内元清貴, 小磯花絵. コーパス日本語学のための言語資源 : 形態素解析用電子化辞書の開発とその応用. 日本語科学, Vol. 22, pp. 101-123, 2007.

[7] 岡照晃. CRF 素性テンプレートの見直しによるモ デルサイズを軽量化した解析用 UniDic — unidiccwj-2.2.0 と unidic-csj-2.2.0 一. 言語資源活用ワーク ショップ 2017 発表予稿集, 143-152.

[8] 青江順一. キー検索技法-IV: トライとその応用. 情報処理, Vol. 34, No. 2, 1993.

[9] Andrew Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, Vol. 13, No. 2, pp. 260-269, 1967.

[10] Jun'ichi Aoe. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, Vol. 15, No. 9, pp. 1066-1077, 1989.

[11] Huidan Liu, Minghua Nuo, Longlong Ma, Jian Wu, and Yeping He. Compression methods by code mapping and code dividing for chinese dictionary stored in a doublearray trie. In Proceedings of 5th International Joint Conference on Natural Language Processing, pp. 1189-1197, 2011.

[12] 前川喜久雄. 代表性を有する大規模日本語書き言葉 コーパスの構築 (<特集>日本語コーパス). 人工知能, Vol. 24, No. 5, pp. 616-622, 2009.

[13] 国立国語研究所コーパス開発センター. 『現代日本語書き言葉均衡コーパス』利用の手引第 1.1 版. https://clrd.ninjal.ac.jp/bccwj/doc.html, 2015.

図 4 右文脈 ID の使用頻度上位 100 件の割合。値は累積 を表し、上位 $k$ 番目の値は 1 番目から $k$ 番目までの割合 の合計である。ipadic-neologd の結果は ipadic-mecab と僅差だったため省略している。

表 5 ダブル配列の実装を変化させた場合の解析時間 $[\mathrm{ms}]$ 。括弧内の数値は Default からの変化率を表す。

## A コスト参照についての事前実験

文脈 ID の使用頻度の調査. 文脈 ID の使用頻度の偏り について調査する。各辞書について、訓練用テキストを 解析したときの文脈 ID の使用頻度を算出した。右文脈 ID の使用頻度上位 100 件について、その割合を図 4 に示 す。 ${ }^{13)}$ 文脈 ID の使用頻度に大きな偏りが確認された。例 えば、右文脈 ID が $15 \mathrm{k}$ 種類も定義されている unidic-cwj

ボトルネックの調査. 巨大な連接表がボトルネックなの かを検証するために、連接表へのアクセスを完全に排除 し、連接コスト値を全て0 として解析した場合（Ideal）の 結果とも比較する。表 5 に実験結果を示す。unidic-cwjで 解析時間が $57 \%$ 短縮した。定数時間の配列参照を取り除 いただけの簡単な修正であることから、巨大な連接表へ の参照がいかにボトルネックであるかが推察できる。

## B 訓練データに関する調査

文脈 ID の使用頻度について、均衡コーパスを用いて算出した場合と、ドメインに特化したコーパスを用いて算出した場合を比較し、訓練コーパスにより Mapped の性能 が変化するのかを調査する。

実験設定. BCCWJ サブコーパスは、新聞 (PN) や Yahoo!知恵袋（OC）などの 13 カテゴリから構成される [13]。各 カテゴリから $10 \mathrm{k}$ 文ずつをサンプルし、13 種類の評価用 データを構築する。そして、各カテゴリについて、以下の 2 つの方法でマッピングを訓練し、解析時間を比較する。

・均衡データ：BCCWJ コアデータからサンプルし得ら れた 10k 文で訓練

・カテゴリ別 : 各カテゴリの評価用テキスト $10 \mathrm{k}$ 文に ついて 5 分割交差検証

辞書には unidic-cwj を使用する。計算機環境など、その 他の実験設定は 5 節と同じである。

13）左文脈 ID の結果も大差は確認されなかった。

図 5 カテゴリ別の評価データについての解析時間。

表 6 各コーパスについて、頻繁に使用された右文脈 ID の上位 10 件。PN は新聞、LB は書籍、OC は Yahoo!知恵袋。ID unidic-cwj で定義されている標準のものを表示。

解析時間に関する結果. 13 カテゴリについて、評価デー タ $10 \mathrm{~K}$ 文の解析に要した時間を図 5 に示す。訓練データ をドメインに特化しても、解析時間は大きく変化しない ことが確認された。

高頻度な文脈 ID に関する分析. コアデータといくつか のカテゴリで頻繁に使用された右文脈 ID の上位 10 件を 表 6 に示す。上位 7 件まではどのコーパスでも同一で、カ テゴリによって使用される文脈 ID に大差は無い。

これらの右文脈 ID に対応した素性列を図 7 に示す。頻出 ID は品詞などの一部の情報によって識別可能な形態素 に割り当てられている。そして、そのような形態素はド メインを問わずコーパスの大部分を占めている。

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

表 7 unidic-cwj で頻繁に使用された素性列の例。


 神田峻介 1 赤部晃一 1 後藤啓介 1 小田悠介 ${ }^{2}$ ${ }^{1}$ LegalOn Technologies Research ${ }^{2}$ 東北大学 データ駆動科学・AI 教育研究センター \{shunsuke.kanda, koichi.akabe, keisuke.goto\}@legalontech.jp yusuke.oda.c1@tohoku.ac.jp  