LegalOn Technologies Engineering Blog

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

速度の高みを目指す：高速な単語分割器 Vaporetto の技術解説

Research

こんにちは。LegalForce Research でエンジニアをしている赤部 (@vbkaisetsu) です。

今回は、弊チームが開発した新しい高速な単語分割器 Vaporetto（ヴァポレット）の技術解説を行います。Vaporetto はプログラミング言語 Rust で開発されています。想定する読者は、

です。

単語分割器 Vaporetto はオープンソースソフトウェアであり、ソースコードは以下のリポジトリで公開しています。

https://github.com/legalforce-research/vaporetto

Vaporetto という名前は、イタリアのヴェネツィアで運行されている水上バスから取りました。

f:id:vbkaisetsu:20210928143630j:plain
ヴェネツィアの様子。写真右端の黄色いラインの入った建物がヴァポレットの乗り場。
（2016年、筆者撮影）

はじめに

開発の経緯

Vaporetto の開発が始まったのは2021年7月中旬で、もともとは筆者の休日の趣味として始まりました。その頃、形態素解析器 Sudachi の Rust 実装である Sudachi.rs の開発が Sudachi 本家に委譲されたという話もあり、自分でも Rust で単語分割器を実装してみようと思ったのが始まりです。

ただ、既存のツールを単純に Rust で実装しても、車輪の再発明になってしまいます。そこで、Vaporetto を開発する上では単語分割速度に重点を置き、比較的高速に動作するであろう点予測ベースの分割手法を採用することにしました。その後、LegalForce Research 内で以前から利用している KyTea が同じく点予測ベースの単語分割器で互換性があることもあり、Vaporetto を Research チーム内で開発する運びとなりました。

単語分割の目的

自然言語処理をする際、文に対する前処理として単語分割（トークン化）が行われます。単語分割によって、入力文を一定の意味を持つまとまりにすることができ、後段の機械学習をはじめとした解析を効率的に精度良く行うことが可能となります。（日本語において「単語」の定義は自明ではなく、辞書などによって分割単位は異なります。ここでいう「単語分割」とは、文を形態素のようなものに分割することを指しています。）

英語など、単語境界に空白を入れる言語の場合は、人手で書かれた複数のルールを利用することで単語分割を比較的簡単に高速に行うことができます。一方、日本語や中国語など、単語境界が見た目だけでは判別できない言語の場合は、統計的な手法による単語分割が主流となっています。

f:id:vbkaisetsu:20210928143906p:plain
単語分割の例。日本語の例は超短単位による分割で、語尾を1トークンとみなしている。

既存の日本語単語分割器（形態素解析器）の比較

単語分割を行うための既存のツールには、例えば以下のものがあります。

これらのうち、JUMAN、ChaSen、MeCab、Kuromoji、Sudachi は、最小コスト法と呼ばれる手法で単語分割を行います。最小コスト法では、単語辞書に基づいて入力文から下図のような分割候補の単語ラティスを構築し、その中からコストの総和が最小となるような最短経路問題を解くことで、最適な分割候補を出力します。元となるコストは、人手による決め打ちや、統計モデルによって算出されたものが利用されます。

f:id:vbkaisetsu:20210928144021p:plain
最小コスト法の例

一方 KyTea (Neubig+ 2011)1 は、点予測（Pointwise Prediction）と呼ばれる手法で単語分割を行います。点予測では、各文字間に対して一定の幅の窓を考え、その窓に含まれる文字列から素性（特徴量）を取り出し、線形分類モデルなどの統計モデルによって単語境界であるか否かを判別します。

f:id:vbkaisetsu:20210928144046p:plain
点予測の例

最小コスト法では、コストの総和は文全体に対して計算されるため、予測器には文全体を入力する必要があります。一方、点予測の場合は、各文字境界が独立に予測されるため、例えば学習データとして文の一部だけにアノテーションしたデータを利用したり、文を適当な大きさに分割して並列に予測することができます。

Vaporetto では、KyTea と同様に線形分類による点予測を採用し、モデルの学習には LIBLINEAR (Fan+ 2008)2 を利用しました。また、素性には以下の3つを利用しました。

  • 文字 n-gram とその相対位置 (n: 1〜3)
  • 文字種 n-gram（ひらがな、漢字など）とその相対位置 (n: 1〜3)
  • 辞書単語素性

3つ目の辞書単語素性は、具体的には下図のように、単語辞書に含まれる単語の内側であるか、端であるかという情報を利用します。

f:id:vbkaisetsu:20210928144120p:plain
単語辞書素性の例（単語辞書に「と」と「権利」が含まれる場合）

これらは KyTea と同様のモデルであり、Vaporetto では KyTea の学習済みモデルを読み込むことができるようにしました。また分割精度は、実装上の些細な違いを除き KyTea と同一となっています。

追記 (2021-09-29)

  • 点予測による単語分割や形態素解析と MeCab など他の手法による解析の精度面での比較については、森ら (2011) 3の研究を参照してください。

高速な予測のための取り組み

素性 n-gram の高速な列挙

各文字間に対して最大で何種類の素性が考えられるでしょうか。窓幅を3とすると、文字 1-gram は6種類、文字 2-gram は5種類、文字 3-gram は4種類です。このため、文字 n-gram と文字種 n-gram を合わせると、合計で30種類の素性を考えることになります。また、これらの素性は文字間によって全く異なったものとなります。このため、単純に n-gram と対応する重みをハッシュマップに格納してスコアを計算しようとすると、すべての文字間に対して少なくとも30回のハッシュ計算と対応する重みの取得を行うことになります。

しかし、実際にスコア計算に必要な n-gram は30種類も無いはずです。素性によってはそもそも学習データに含まれていないものや、学習の過程で正則化によってモデルから削除されたものも含まれます。そこで、パターンマッチオートマトンによって、単語分割したい文字列の中から必要最小限の n-gram だけを列挙することで、効率化を図ります。

f:id:vbkaisetsu:20210928144155p:plain
Aho-Corasick アルゴリズムによるパターンマッチの例。下線部分がマッチした区間。

上図は、Aho-Corasick アルゴリズム (Aho&Corasick 1975)4 によるパターンマッチの例です。まず、学習済みモデルの中から重みが0でない素性の n-gram を列挙し、それをモデル辞書とします。このモデル辞書から Trie を作り、点線で示されたサフィックスリンクを張れば、辞書に含まれる文字列に一致する区間を列挙できるパターンマッチオートマトンとなります。

Rust には Aho-Corasick アルゴリズムのライブラリである、aho-corasick クレートがあります。このクレートでは、通常の Aho-Corasick アルゴリズムに基づくオートマトンを生成する NFA モードと、サフィックスリンクを初期化時に辿っておき、各状態において次の遷移先を即座に決定できるようにした DFA モードを選択することができます。DFA モードではパターンマッチ中にサフィックスリンクを辿る処理が無いため高速に動作しますが、各状態が大量の遷移先を保持することになるため、非常に多くのメモリを消費してしまいます。（これについては aho-corasick クレートのソースコードで説明されています。）

そこで Vaporetto では、オートマトンを格納するデータ構造として Double-Array (Aoe 1989)5 を利用することで、省メモリと高速な動作の両立を実現しています。Double-Array を利用した Aho-Corasick アルゴリズムのコードは、Vaporetto とは別に daachorse（ダークホース）という名前で以下のリポジトリで公開しています。

https://github.com/legalforce-research/daachorse

daachorse は、aho-corasick クレートの NFA を利用した場合と同程度のメモリ消費で、DFA と同程度の速度か、状況によってはより高速に動作します。

重み配列

文字 n-gram と文字種 n-gram の重みは、いまスコアを計算しようとしている文字境界との相対位置ごとに学習されています。例えば「われらは全世界の国民が」という文字列の各文字境界についてスコアを計算する場合、窓幅を3とすると「世界」という 2-gram は5つの文字境界のスコア計算の際に、それぞれ異なる相対位置において出現します。

f:id:vbkaisetsu:20210928144231p:plain
n-gramの重みは (窓幅×2-n+1) 個の相対位置ごとに学習される。

このため、「世界」という 2-gram に対して、相対位置に応じた5種類の重みが学習されています。それらの重みを順に並べたものを重み配列とします。

f:id:vbkaisetsu:20210928144310p:plain
重み配列の例。ここでは、「全世界」と「世界」の重み配列がスコア配列に加算され、単語境界の判定に利用される。

各重みはパターンマッチオートマトンで n-gram が見つかるたびにスコア配列に加算されていきますが、相対位置ごとの重みを配列の状態で保持しておくことで、SIMD 命令による並列計算などの最適化が効きやすくなります。

重みの事前加算

パターンマッチオートマトンを利用するだけでも十分高速に動作しますが、一部の重みを事前に足し合わせておくことで、更に高速化できます。

例えば上の例にある「全世界」と「世界」という2つの n-gram で考えてみましょう。この例では、ある入力文に「全世界」という n-gram が含まれている場合、 パターンマッチオートマトンは「全世界」に一致しますが、同時にその部分文字列である「世界」にも一致します。このように、ある n-gram に一致した際に、その部分文字列にも必ず一致するという場合があります。

ところで、通常の Aho-Corasick アルゴリズムでは、あるパターンの終端に到達した際に一致するパターンが報告されますが、そこで報告されるパターンの数は1つとは限りません。例えば上の例において、「われらは全世界の国民が」という文字列の「界」の部分に到達した際に、オートマトンは「全世界」と「世界」の2つのパターンを報告します。これは、オートマトンを構築する際に、サフィックスリンクを辿ってサフィックスの一致状態を事前に調べておくことで実現されます。

ここで、オートマトンにサフィックスのパターンを報告させるのではなく、事前に長い n-gram の重み配列に対してサフィックスの重み配列を加算しておくことにします。このようにしておけば、長い n-gram への一致が報告されて重みを加算する際に、同時にサフィックスの n-gram の重みも加算されます。

f:id:vbkaisetsu:20210928144358p:plain
重み配列の事前加算の例

これにより、単語分割の際には必要最小限の加算処理によって各文字間のスコアを計算することが可能となります。

処理速度の比較

Vaporetto と他の単語分割器の速度比較です。Vaporetto と KyTea では、KyTea が配布している圧縮 SVM モデルを利用しました。MeCab では IPAdic を利用しました。Kuromoji は Atilika 社のバージョンで IPAdic を利用しました。Sudachi では system_core.dic を利用しました。Lindera は Kuromoji の Rust 実装、Sudachi.rs は Sudachi の Rust 実装です。Vaporetto では、シングルスレッドとマルチスレッドでの速度を計測しました。単語分割は、KFTT の日本語学習データ（44万文）に対して行い、20回の平均速度を出しました。結果は以下のとおりです。

f:id:vbkaisetsu:20210928144428p:plain
単語分割速度の比較

ツール 分割速度 [×106 文字/秒] 標準偏差
KyTea 0.735 0.004
Vaporetto 3.018 0.030
Vaporetto (4 スレッド) 3.353 0.038
MeCab 2.683 0.005
Kuromoji 0.440 0.011
Lindera 1.095 0.004
Sudachi 0.255 0.006
Sudachi.rs 0.247 0.001

Vaporetto は KyTea の4倍程度の速度で単語分割できることが分かります。また、モデルが異なるため単純な比較はできませんが、Vaporetto は KyTea 以外のツールと比較しても、高速に動作することが伺えます。

単語分割器の Web ページへの実装

単語分割器を JavaScript で実装して Web ブラウザ上で動作させる試みが以前からあります。Web サービスにおいて単語分割などの一部の処理をクライアント側で動作させることは、サーバーの負荷を軽減し、顧客の機密情報を保護する上で大きなメリットがあります。JavaScript で実装された単語分割器として、例えば以下のようなものがあります。

しかし、2017年に Web 標準化された WebAssembly を利用すれば、Rust や C++ などで実装されたコードを WebAssembly にビルドし、そのまま Web ブラウザ上で比較的高速に動作させることが可能となります。

Vaporetto のリポジトリには、Web ブラウザ上で単語分割を行うサンプルコードと、10MBに満たない比較的軽量な単語分割モデルを同梱しており、数行のコマンドを入力するだけでデモサーバーを立ち上げることができます。

f:id:vbkaisetsu:20210928144500p:plain
Web ブラウザ上で Vaporetto が動作する様子。コンソールには、Vaporetto に入力された文字列、予測範囲、文字境界ごとに計算されたスコアが出力されている。

追記 (2021-09-29)

  • 同梱のモデルは未圧縮のものとなります。gzipで圧縮した場合は3〜4MBとなります。

まとめ

本記事では、新しい単語分割器 Vaporetto の技術解説をしました。弊社では大規模な契約書文書を扱っており、単語分割が必要な場面は機械学習データの前処理から検索データベースの構築まで多岐にわたります。単語分割の速度が高速になれば、前処理の待ち時間を削減でき、その時間を別のことに活用できます。

Vaporetto はオープンソースソフトウェアなので、自由な利用はもちろん、改善の依頼やコードの提供も受け付けております。

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

参考文献

  1. Graham Neubig, Yosuke Nakata, and Shinsuke Mori. 2011. Pointwise prediction for robust, adaptable Japanese morphological analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers - Volume 2 (HLT ‘11). Association for Computational Linguistics, USA, 529–533.↩

  2. Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. 2008. LIBLINEAR: A Library for Large Linear Classification. J. Mach. Learn. Res. 9 (6/1/2008), 1871–1874.↩

  3. 森 信介, 中田 陽介, Neubig Graham, 河原 達也, 点予測による形態素解析, 自然言語処理, 2011, 18 巻, 4 号, p. 367-381, 公開日 2011/12/28, Online ISSN 2185-8314, Print ISSN 1340-7619, https://doi.org/10.5715/jnlp.18.367↩

  4. Alfred V. Aho and Margaret J. Corasick. 1975. Efficient string matching: an aid to bibliographic search. Commun. ACM 18, 6 (June 1975), 333–340. DOI:https://doi.org/10.1145/360825.360855↩

  5. Jun-ichi Aoe. 1989. An Efficient Digital Search Algorithm by Using a Double-Array Structure. IEEE Trans. Softw. Eng. 15, 9 (September 1989), 1066–1077. DOI:https://doi.org/10.1109/32.31365↩