こんにちは。LegalOn Technologies Researchで研究員をしている神田 (@kampersanda) です。
この度、論文「Engineering faster double-array Aho-Corasick automata」がソフトウェア系の有名学術誌「Software: Practice and Experience」に採択されました。
本記事では論文の紹介をします。論文内に記述された内容については簡単な概要紹介に留め、論文には書かれていない研究の動機などをメインにお伝えします。
論文の概要
本論文は、パターンマッチングアルゴリズムAho-Corasick法（AC法）の効率的な（高速・省メモリな）実装方法を探求したものです。具体的には、高速なオートマトンの表現技法Double Arrayに着目して、Double Arrayを用いたAC法（以下、DAAC）の数ある実装技法をレビューし、徹底的な実験的解析を通じて「本当に効率的なDAACの実装方法は何か？」を追求しました。この研究結果は、我々が開発するパターンマッチングライブラリDaachorseに活用されています。
研究の動機
Daachorseの開発のキッカケは単語分割器Vaporettoです。
Vaporettoは点予測に基づく高速な単語分割器です。単語分割は、自然言語で書かれた文書データから特徴量を得る際など、自然言語処理や情報検索などの多くのアプリケーションで必要な前処理です。しかし、昨今の大規模な文書データでは、その処理時間がシステム全体のボトルネックになることも多く、処理の高速化が求められます。例えば、契約書なども一つの一つの文書がとても長いので大規模になりやすく、単語分割に数時間掛かることも珍しくありません。Vaporettoはそうした背景から、高速処理に向けた設計がされています。Vaporettoの重要な構成要素の一つがAC法によるパターンマッチングであり、そのモジュールを切り出してライブラリ化したものがDaachorseです。Vaporettoの詳細については、論文やブログ記事をご参照ください。
Double Arrayはシンプルなアイデアに基づくデータ構造である一方、より高速な検索を得るためには計算機のアーキテクチャなどを意識し、入念に実装する必要があります。しかし、数多くある実装技法から効率的なものを選び抜いて設計することは容易ではありません。Double Arrayの実装技法は出典が論文やOSSなど多岐に渡り、慣習的に使われているような文書化されていないものも含まれるためです。故に、多くの人にとって例えばdarts-cloneなどで実装されているようなコアな技術にリーチするのが難しい現状にあります。
そこで、我々がDaachorseの開発過程で得た知見を共有し、文字列処理の発展に貢献したいと考え、論文として報告することにしました。
論文の主結果
簡単に論文の主結果を紹介します。それぞれ詳しい内容は論文をご参照ください。
実装技法のレビューと比較実験
まず、数ある実装技法をいくつかのコンポーネントに分類し整理しました。そして、各コンポーネントに属する技法を比較することで、どの組合せが最も効率的なDAACの設計に繋がるかを評価しました。以下は、それらカテゴリと技法をリストアップした表です。
文字列の表現方法や配列のメモリレイアウトなど、6つのコンポーネントに分類されています。実装技法は、出典のあるものから慣習的に使用されているもの、本論文で提案したものまで様々です。表の「Selected」列にチェックが付いている技法が、実際にDaachorseに採用した技法になります。比較実験を通じて、現代のアーキテクチャにおけるキャッシュ効率などの観点から、効率的な技法を選定しました。
既存ソフトウェアとの比較
有名なAC法の実装として、Rustで書かれたaho-corasick (AC) ライブラリがあります。このライブラリでは、高速な直接アドレス表とメモリ効率の良いリスト構造をハイブリッドに使い分けることでオートマトンを表現しています。
比較した実装は以下の4種類です。
- Bytewise-Daachorse: Daachorseによるバイト単位で遷移するDAAC
- Charwise-Daachorse: Daachorseによる文字単位で遷移するDAAC
- NFA-AC: ACライブラリによる標準のACオートマトン
- DFA-AC: ACライブラリによる遷移先候補を全て展開したACオートマトン
Charwise-Daachorseは、日本語などのマルチバイト文字に特化した実装です。DFA-ACは、メモリを多く使用する代わりに高速化した実装です。
以下の図が、それら実装について検索時間を比較した結果です。
縦軸が解析に要した時間、横軸が登録パターンの数を表しています。英語と日本語からなる3種類のパターンセットで評価しています。詳細な実験設定は論文をご参照ください。パターン数が増えてもDaachorseの速度低下は控えめであり、大きなパターンセットほどDaachorseが高速なことがわかります。これは、本研究での分析によりキャッシュ効率の良い実装技法を採用したことにも起因します。
メモリ使用量についても以下に示します。
Daachorseは大半のケースでACライブラリより省メモリです。
Vaporettoでの性能評価
単語分割器VaporettoにDaachorseとACライブラリを組み込んだ場合の、解析速度の比較実験も行いました。UniDic v3.1.0に含まれる重複を除いた66万単語をパターンとし、BCCWJのサブコーパスを改行で区切り得られた590万文（平均33.8文字）について解析した結果が以下になります。
- Bytewise-Daachorse: 3.3 マイクロ秒/文
- Charwise-Daachorse: 2.9 マイクロ秒/文
- NFA-AC: 7.5 マイクロ秒/文
- DFA-AC: 7.3 マイクロ秒/文
Daachorseは最大2.6倍程度高速であり、NLP応用においてもその効果が確認されます。
採択に至るまで
この論文は、内容が整理されている点や、レビューと実験結果がAC法を実装しようとしている人にとって有益なリソースとなり得る点などが評価され、採択に至りました。
初稿の時点で査読者からはかなりの好印象でした。しかしそれでも、L1/L3レベルでのキャッシュミス回数やCPU命令数、分岐数などまで含めた議論の拡充や、Rust言語を用いた実験結果の一般性の説明など、ソフトウェア系学術誌として非常にクリティカルな指摘を多く受けました。そして、多くの追加実験と説明を加え、採択して頂けました。
査読をクリアするのは大変でしたが、論文のクオリティは確実に改善しましたし、徹底的なソフトウェア分析に必要なことを学べたので、とてもよい経験でした。
まとめ
本記事では、論文「Engineering faster double-array Aho–Corasick automata」の紹介として、その研究動機と主結果を解説しました。本論文の結果は、今後Double Arrayの実装を考える上で大いに役立つと思いますので、ご興味のある方は是非一読していただけると幸いです。
メンバー募集中！
株式会社LegalOn Technologies では、SREや、バックエンドエンジニア、検索システム、研究開発に興味のあるインターン生など様々なポジションを募集しています。
ご興味がある方は以下の求人ページから求人要項をご確認いただけますので、お気軽にご応募ください！
https://herp.careers/v1/legalforce/requisition-groups/d2e157cc-120b-4ade-8879-0326c32127bd
