# 最長一致パターンに基づく高速・高精度な日本語形態素解析

吉永 直樹
東京大学生産技術研究所
ynaga@iis.u-tokyo.ac.jp

## 概要

膨大な量のテキストを解析したり，言語処理応用 で大量にユーザのクエリを処理する場合，処理効率 の悪いモデルは高精度でも利用し難い. 本稿では高効率な手法の精度を改善すべく, 最長一致パターン に基づく高精度な形態素解析手法を提案する. 提案手法では，既存の辞書項目を元に，学習データから 抽出したパターンを用いて形態素解析を行う．実験 では，複数の品詞タグ付きコーパスと辞書を用いて 提案手法の評価を行い，最小コスト法や点推定に基 づく形態素解析手法の既存実装と同程度の精度, $1 / 2$ から $1 / 20$ 程度の消費メモリで，1,000,000 文/秒を超 える速度の形態素解析が可能なことを確認した. 本手法の実装（C++で約 1000 行）は以下で公開する. http://www.tkl.iis.u-tokyo.ac.jp/ ynaga/jagger

## 1 はじめに

Twitter や Zoom, Slack などのコミュニケーション プラットフォームの普及に従い，電子化された言語 データの量は爆発的に増加し続けており, 深層学習 によって高精度化された機械翻訳などの実サービス は数千万を超えるユーザを獲得するようになった。 このように，実世界テキストの量や実時間処理する ユーザクエリがこれまでになく増加する状況下で は，現実的な計算資源で運用できる効率の良い言語処理技術の重要度が高まっている。

しかしながら，深層学習の導入以降，精度に偏重 して研究が行われた結果，「効率の良い」手法 [1] は 他分野のように処理速度や消費メモリの限界を更新 するものではなく, 低速で消費メモリの大きい深層学習モデルの効率を, 深層学習の枠内で相対的かつ 限定的に改善するものが大半である. 結果, 最高精度のモデルと古典的ではあるが効率の良いモデルと の間の速度差は埋め難く, 深層学習を用いた高精度 の言語処理サービスは，膨大な GPU 資源を有する 一部の企業のみが展開するに留まっている.本研究では，遅いモデルの効率を改善するのでは なく，効率の良いモデルの精度を改善する，真に 「効率の良い」言語処理を実現すべく，機械学習を 経由しない単純で高精度な日本語形態素解析手法を 提案する. 日本語における形態素解析は，一般に，単語分割, 品詞解析, 見出し語化の混合タスクとし てモデル化されるが，我々の提案手法は，古典的な 最長一致法に基づく単語分割手法を拡張したもの で, 次の分割位置と切り出した単語の品詞・見出し 語を決定するパターンに基づき形態素解析を行う.解析に用いるパターンは形態素解析辞書の項目を シードとして，学習データから頻度に基づいて抽出 する。抽出したパターンはダブル配列 $[2,3]$ に格納 し，時空間効率の良い処理を実現する。

実験では，多様なドメインの標準コーパス $[4,5]$ と形態素解析辞書を組み合わせて提案手法の評価を 行った. その結果, 提案手法が，探索 (最小コスト 法) や分類 (点推定) に基づく実装 (MeCab, Vaporetto) と同程度の精度で，MeCab の約 15 倍，Vaporetto の 約 10 倍 (M2 MacBook Air で 1,000,000 文秒以上) の 速度で形態素解析を行えることを確認した。

## 2 パターンに基づく形態素解析

本節では，単語分割，品詞タグ付け，見出し語化 を同時に行う決定的な形態素解析手法を提案する.速度に妥協のない実装を得るため, 本研究では古典的な最長一致法 [6] を拡張した最長一致パターンに 基づく形態素解析アルゴリズムを提案する.

最長一致法は辞書 (単語の集合) に基づく決定的 な単語分割手法であり, 入力文字列の先頭から辞書中の単語と一致する最長の文字列を, 繰り返し単語 として認識することで単語分割を行う. 最長一致法 は，日本語や中国語の単語分割において，修正規則 と組み合わせることで高精度化できること $[7,8]$ が 知られているが，機械学習を用いた最小コスト法や 点推定などの標準的な単語分割手法 $[9,10]$ と比べる と分割精度には一定の差 [11] が存在する.

## 2.1 基本的なアルゴリズム

本節では, 単語分割, 品詞タグ付け, 見出し語化 ${ }^{1)}$ を同時に行う決定的な形態素解析アルゴリズム を提案する. Algorithm 1 は，与えられた文字列に対 し，トライに格納されたパターン $\mathscr{P}$ 繰り返し適用 して, 後続する単語 $w=\boldsymbol{c}_{i}^{i+\text { shift }}$ を切り出すと同時に 品詞 (と見出し語) を決定するアルゴリズムである.単語分割に対する最長一致法と同様に, 本手法でも 最長一致するパターンが選択・適用されるが，分割位置がパターン長と必ずしも一致しない点に注意さ れたい， 3 節で確認するように，この単純なアルゴ リズムは有効なパターン集合が用意できれば，最小 コスト法や点推定などの探索・分類ベースの手法に 匹敵する精度で動作する。

本手法は，系列ラベリングや組合わせ特徴に基づ く分類器における事前計算 $[9,12,13,14]$ に着想を得 ている。これらの効率的な実装では，事前計算した 特徴量の重みを，表層など単純な特徴の系列をキー として取得することで推論を行う．機械学習で用い る特徴量が単純なキー (パターン) に畳み込めるので あれば，直接，分類結果 (単語分割の有無, 品詞, 見出し語) に写像可能なパターン (特徴列) が存在し うるというのが本手法の基本的なアイデアである.

## 2.2 辞書に基づく特徵列パターンの抽出

最小コスト法 [9] や点推定 [10] を実装した形態素解析器の素性テンプレートを参考に, 本稿では提案手法のためのパターンテンプレートとして，分割位置以降の表層文字列 $\boldsymbol{c}_{p}$ と直前の単語の品詞 $t_{j-1}$ の 連結，すなわち $\boldsymbol{c}_{p} ; t_{j-1}($; は文字の連結) を採用した。

Algorithm 2 は, 形態素解析の学習データから特徵列パターンをマイニングするアルゴリズムである.単語分割, 品詞タグ及び見出し語が付与された学習


データ Dと単語がとりうる品詞タグ・見出し語を 定義した形態素解析辞書 $\mathscr{V}$ を力として, 本手法 は逐次的に特徴列パターンを学習データから抽出 する。

具体的にはまず，学習データ中の全ての単語分割位置に対し，その位置から次の分割位置以降までを 含む文字列 $\boldsymbol{c}_{i}^{i+k}$ を表層パターンとして抽出し, 直前 の単語の品詞タグ $t_{j-1}$ と組み合わせてパターン候補 を得る (4-8 行目). これらのパターン候補に対して，分割位置 (shift) ・品詞タグ $($ ・見出し語, 以後省略) $t$ の頻度を数えて，最多の分割位置・品詞タグをその パターンが適用されたときの分割位置・品詞タグと して採用する (12-13 行目). 冗長なパターンを枝刈 りするために，接頭文字列が同じで分割位置・品詞 タグが同じパターンについては，最も短いパターン のみを採用する (14-16 行目)。提案手法は最長一致法と比べて，後続文脈や前文脈品詞について追加の 走査が必要となるが，大きなオーバーヘッドとなら ないことを確認している.2)

## 3 実験

本節では提案手法を多様なドメインの形態素情報付きコーパス $[4,5]$ を用いて評価し，探索や分類に 基づく効率的な形態素解析手法 $[9,10]$ と速度，消費 メモリ，精度の観点で比較する。

2）Aho-Corasickライクな手法で表層について戻り読みのない 処理を行うことも可能だが，逆に処理速度が低下した。
表 1 評価データの統計.

## 3.1 設定

データセット 実験では新聞記事に注釈を付与し た京都大学テキストコーパス33) (куОто) [4] とウェブ ページの冒頭三文に注釈を付与した京都大学ウェブ 文書リードコーパス ${ }^{4}$ (KWDLC) [5]を用いた。開発・評価データとしては， github リポジトリに含まれる 分割を用い，残りを学習データに用いた (表 1).

比較モデル 本稿では，以下の実装を比較する。学習ベースのモデルではハイパーパラメタ $c^{5)}$開発データを用いて調整し，活用を含む品詞タグ (level 1-4)の $\mathrm{F}_{1}$ が最大となるモデルを評価に用いた.

Jagger は提案手法の C++実装であり，入力テキスト の先頭から後続する表層文字列と前文脈品詞に対し て特徴列パターンを繰り返し適用し, 決定的に単語分割, 品詞タグ付け, 見出し語化を行う. これらの パターンは学習データと辞書から抽出される。

$\mathbf{M e C a b}^{6}$ (は最小コスト法の $\mathrm{C}++$ 実装7)であり, 条件付き確率場 [15] により, 学習データからパラメタを 推定する [9]. 最小コスト法では，辞書に基づき可能 な分割と品詞の組み合わせをラティスで表現して，最尤となる分割・品詞を動的計画法で求める.

Vaporetto は点推定 [10]の Rust 実装9) である. 点推定 では，各文字間を分割候補とする二値分類により単語分割を行った後, 各単語に対して多クラス分類に より品詞タグ付けを行う. 公平な比較のために，単語特徴量には他の手法と同じ形態素解析辞書を用い る. Vaporettoでは単語の品詞候補ごとに分類器を学習しており，学習データに出現しない単語10)には，辞書中で最初に現れる品詞タグが付与される [16].

3) https://github.com/ku-nlp/KyotoCorpus

4) https://github.com/ku-nlp/KWDLC
5) $c=\{0.1,0.2,0.5,1.0,2.0,5.0,10.0\}$ を試した.

6) https://taku910.github.io/mecab/

7） $\mathrm{MeCab}$ の高速な再実装である Vibrato $\left.^{8}\right)$ は，今回用いた実験設定で品詞タグ付けまで行うと， MeCabより遅くメモリ 消費も大きかったため，比較しなかった.

8) https://github.com/daac-tools/vibrato

9) https://github.com/daac-tools/Vaporetto

10）学習データにも辞書にも出現しない単語には品詞タグが 付与されないため, 文献 [9]を参考にサ変名詞を割り当てた. なお，この処理にかかる時間は処理速度には含めない.表 2 形態素解析辞書の統計

なお, Rust と C++が生成するコードの実行速度は，多くのベンチマークで同程度 ${ }^{11)}$ である.

提案手法は，大域的な最適化を行う最小コスト法 よりは，局所的な最適化を行う点推定に近い手法で あるが，二つの点で異なる. まず，提案手法は全て の文字間に対して分割の有無を判定するのでなく, パターンに基づき，次の分割位置を決定する (分類問題としては次の分割位置を予測する多クラス分類 に相当)。また，提案手法では，単語分割，品詞タグ 付け (，見出し語化)を同時かつ決定的に行う.

形態素解析辞書 各手法が用いる辞書としては,形態素解析器 JUMAN ${ }^{12)}$ の辞書を MeCab 用に変換 したものを用いる。具体的には mecab-jumandic-5.120070304 と mecab-jumandic-7.0-20130310を，辞書の 質とカバレッジの影響を分析するために比較する。 このうち, jumandic-7.0ではウェブから自動獲得し た語彙 [17] が含まれており, 収録語数が 475,716 語 (jumandic-5.1) から 702,358 語 (jumandic-7.0) に増加 している. 品詞タグは 4 階層 (2 段階の品詞分類, 活用型, 活用形) からなる形態・統語論的なカテゴリ が付与されている (表 2).

評価方法 解析精度に関する評価尺度としては,既存研究 [9] に倣い，単語分割と品詞タグに関する 精度, 再現率, $\mathrm{F}_{1}$ 値を用いる. 処理効率の評価と しては，評価データを 1000 回コピーしたデータの 解析時間 (秒), 解析速度 (文秒), 最大消費メモリ (MiB)を/usr/bin/time - l コマンドにより 3 回計測 して，中央値となる処理時間 (速度) と，そのときの 最大消費メモリを報告する. 実験は $3.5 \mathrm{Ghz} \mathrm{CPU}$ と 主記憶 $24 \mathrm{~GB}$ を備えた M2 MacBook Air 上で行った. なお，付録 $\mathrm{C}, \mathrm{D}$ に単語分割のみの評価，及び深層学習に基づく形態素解析器との比較を載せた.

## 3.2 結果

表 3, 4 に кYото, кWDLC コーパスでの単語分割・品詞タグ付けの評価結果を示す. 我々の提案手法の 参照実装である Jaggerが，最小コスト法を実装した MeCab や点推定を実装した Vaporetto と遜色のない

11) https://github.com/kostya/benchmarks/

12) https://nlp.ist.i.kyoto-u.ac.jp/?JUMAN
表 3 куото コーパスの解析結果, $\mathrm{F}_{1}$ (precision/recall).

表 4 KWDLC コーパスの解析結果, $\mathrm{F}_{1}$ (precision/recall).

精度を示すと共に，MeCab の約 15 倍，Vaporetto の 約 10 倍高速，かつ MeCab の約 1/2, Vaporetto の約 1/20 程度の消費メモリで解析が行えている. Jagger が用いる特徴列パターンは枝刈り (Algorithm 2 の 14 行目) によって最小限に抑えられており, 機械学習 を経由せず，浮動小数点数で表現されるパラメタも 含まないことから，高効率となったと考えられる (他手法の学習に相当するパターンの抽出時間は 6 秒未満であった). MeCab の解析精度は辞書の性質 に依存し，jumandic-7.0を用いた場合，KWDLC で優れ た精度を示す一方で куото では単語分割精度が低下 している. Vaporetto は，学習データの多い куотоで は MeCab や Jagger より高精度だが，学習データの 少ない KWDLC では Jagger と同程度の精度に留まる。

表 5 に，学習データとは異なるドメインの評価 データを用いて各手法を評価したときの解析精度 を示す. 辞書に基づいて単語分割候補を列挙する最小コスト法 (MeCab) に対し，辞書を間接的に用いる 点推定 (Vaporetto) の解析精度が低く, 学習ドメイン に依存する点推定のリスクを示している. 提案手法 の実装である Jagger は MeCabよりは性能が低下し ているものの, Vaporetto ほどには性能が落ちておら ず，辞書と学習データの両方をバランスよく活用し た手法となっている. 提案手法は，辞書，あるいは パターンを追加する形で学習という余分なプロセス を経ずに処理を即座に変更することもできる。

## 4 まとめ

本稿では最速の言語処理技術を高精度化すべく，最長一致パターンに基づく高精度な形態素解析器を 提案した. 我々の手法は, 辞書中の単語をシードと して学習データから単語分割位置と品詞タグ (及び 見出し語)を決定するパターンを抽出し，最長一致 パターンを順次切り出す形で効率よく高精度の解析 を行う．複数の品詞タグ付きコーパスを用いた実験 により, 提案手法が最小コスト法や点推定の効率的 な既存実装に匹敵する解析精度を達成し, 同時に, ノート PCで $1,000,000$ 文秒という基礎解析として 望ましい解析速度を実現することを確認した。

今後は，深層学習により得られる埋め込み表現を 離散化してパターンに組み込むなどして，本論文の アプローチを他の言語処理タスクに応用したい.

## 謝辞

本研究は JSPS 科研費 JP21H03494 の助成を受けた ものです. Vaporettoの未知語処理に関する実装をご 教示くださった LegalOn Technologies の赤部晃一氏，本稿の草稿にコメントをくださった Rakuten Institute of Technology Americas の新里圭司氏に感謝いたし ます.

## 参考文献

[1] Marcos Treviso, Tianchu Ji, Ji-Ung Lee, Betty van Aken, Qingqing Cao, Manuel R. Ciosici, Michael Hassid, Kenneth Heafield, Sara Hooker, Pedro H. Martins, André F. T. Martins, Peter Milder, Colin Raffel, Edwin Simpson, Noam Slonim, Niranjan Balasubramanian, Leon Derczynski, and Roy Schwartz. Efficient methods for natural language processing: A survey, 2022.

[2] 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.

[3] Naoki Yoshinaga and Masaru Kitsuregawa. A self-adaptive classifier for efficient text-stream processing. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pp. 1091-1102, Dublin, Ireland, August 2014.

[4] Sadao Kurohashi and Makoto Nagao. Building a Japanese parsed corpus. In Treebanks: Building and Using Parsed Corpora, pp. 249-260. Kluwer Academic Publishers, 2003.

[5] Masatsugu Hangyo, Daisuke Kawahara, and Sadao Kurohashi. Building a diverse document leads corpus annotated with semantic relations. In Proceedings of the 26th Pacific Asia Conference on Language, Information, and Computation, pp. 535-544, Bali, Indonesia, November 2012.

[6] Masaaki Nagata. A stochastic Japanese morphological analyzer using a forward-DP backward-A* $n$-best search algorithm. In COLING 1994 Volume 1: The 15th International Conference on Computational Linguistics, Kyoto, Japan, August 1994.

[7] David D. Palmer. A trainable rule-based algorithm for word segmentation. In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pp. 321-328, Madrid, Spain, July 1997.

[8] Julia Hockenmaier and Chris Brew. Error-driven learning of Chinese word segmentation. In Proceedings of the 12th Pacific Asia Conference on Language, Information and Computation, pp. 218-229, Singapore, February 1998.

[9] 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, Barcelona, Spain, July 2004.
[10] Graham Neubig, Yosuke Nakata, and Shinsuke Mori. Pointwise prediction for robust, adaptable Japanese morphological analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 529533, Portland, Oregon, USA, June 2011.

[11] Manabu Sassano. Deterministic word segmentation using maximum matching with fully lexicalized rules. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, volume 2: Short Papers, pp. 79-83, Gothenburg, Sweden, April 2014.

[12] Nobuhiro Kaji, Yasuhiro Fujiwara, Naoki Yoshinaga, and Masaru Kitsuregawa. Efficient staggered decoding for sequence labeling. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pp. 485-494, Uppsala, Sweden, July 2010.

[13] Naoki Yoshinaga and Masaru Kitsuregawa. Kernel slicing: Scalable online training with conjunctive features. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pp. 12451253, Beijing, China, August 2010.

[14] 赤部晃一森信介. Vaporetto: 点予測法に基づく高速 な日本語トークナイザ. 言語処理学会 第 28 回年次大会 発表論文集, pp. 256-261, 2022.

[15] Percy Liang, Hal Daumé, and Dan Klein. Structure compilation: Trading structure for features. In Proceedings of the 25th International Conference on Machine Learning, ICML '08, p. 592-599, New York, NY, USA, 2008.

[16] 森信介, 中田陽介, Neubig Graham, 河原達也. 点予測 による形態素解析. 自然言語処理, Vol. 18, No. 4, pp. 367-381, 2011.

[17] Yugo Murawaki and Sadao Kurohashi. Online acquisition of Japanese unknown morphemes using morphological constraints. In Proceedings of the $\mathbf{2 0 0 8}$ Conference on Empirical Methods in Natural Language Processing, pp. 429-437, Honolulu, Hawaii, October 2008.

[18] 工藤拓. 形態素解析の理論と実装. 近代科学社, 2018.

[19] 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, Chiang Mai, Thailand, November 2011.

[20] Arseny Tolmachev, Daisuke Kawahara, and Sadao Kurohashi. Juman++: A morphological analysis toolkit for scriptio continua. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 54-59, Brussels, Belgium, November 2018.

[21] Hajime Morita, Daisuke Kawahara, and Sadao Kurohashi. Morphological analysis for unsegmented languages using recurrent neural network language model. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 2292-2297, Lisbon, Portugal, September 2015.
表 6 JUMAN++との比較, $\mathrm{F}_{1}$ (precision/recall).

## A 未知語処理

最小コスト法と同様に, 提案手法でも辞書・学習 データに含まれない未知語の扱いは，問題となる。現在の実装では, 既存手法 [9] と同様に, 文字種に 基づいて，数字，アルファベット，カタカナを連結 する単純な未知語処理を実装している。具体的に は，連続する数字，アルファベットはそれぞれ単純 に連結し，連続するカタカナ語については，単語の 合計長が一定サイズ以下のときに連結する。いずれ の場合も，前文脈品詞，および連結する末尾の語に 対するパターンに基づき品詞を割り当てる.

## B 実装上の工夫

Jagger の C++実装には，MeCab で用いられている ゼロコピーや mmap [18], J.DepP ${ }^{13)}$ でも用いられて いるキャッシュ効率化のための頻度順 ID[19] に加え て, Vaporetto や Vibrato で用いられている文字単位 で遷移するダブル配列を利用している。文字単位の ダブル配列には，バイト単位で遷移する動的ダブル 配列 cedar ${ }^{14)}$ に軽微な修正を加えたものを用いた。

## C 単語分割のみの処理効率の比較

品詞タグ付けに対するアプローチ（未知語処理,見出し語化への対応）の違いから, MeCab / Jagger と Vaporetto を形態素解析器として厳密な意味で公平に比較することは困難である。 そこで，各実装で jumandic-7.0を用いて，単語分割のみを行い，処理速度・消費メモリを比較した。なお，MeCab, Jagger については表 3,4 と同じモデルを用いた. Vaporetto については，省メモリ化のため単語分割のみの学習 データから, 単語リストとして辞書を与えて, 単語分割のみを行うモデルを再学習した ${ }^{15)}$.


表 7 単語分割の処理効率 (辞書: jumandic-7.0).

表 7 に， 3.1 節の評価方法に倣って計測した単語分割の処理効率を示す. 表で UTF-8 split は，UTF-8 で符号化された評価データを文字ごとに分割して 出力する処理である. Vaporetto の処理効率が改善し ているが，(モデルの読み込みのオーバーヘッド (約 1.7 秒) 点を考慮しても) 提案手法による処理の方が 高速かつ省メモリである.

## D ニューラル形態素解析との比較

現時点で最高精度の日本語形態素解析器である JUMAN++-V2 [2016) との比較を行った. モデルは,表 1 と同じ学習データから公式スクリプト ${ }^{17)}$ 及び，学習コーパスに対し最適化されたハイパーパラメタ を用いて学習した。なお，JUMAN++は，Wikipedia から抽出した辞書と大規模コーパスから訓練された RNN 言語モデルを追加で用いており, 精度の観点 では Jagger に不利で，速度の観点では JUMAN++に 不利な比較となっている点に注意されたい。

表 6 に jumandic-7.0 を辞書に用いた Jagger と比較 した結果を示す. Jagger と JUMAN++の解析精度の 差は, 品詞タグ付けでは大きいが単語分割では $1 \%$ 以内に収まっている。JUMAN++-V2 は JUMAN++ [21] に対して 250 倍の高速化を達成したと報告されてい るが，Jagger はその JUMAN++-V2 よりさらに 180 倍以上高速で，1/7 以下の消費メモリであった.

16) https://github.com/ku-nlp/jumanpp

17) https://github.com/ku-nlp/jumanpp-jumandic
 吉永 直樹 東京大学生産技術研究所 ynaga@iis.u-tokyo.ac.jp  