こんにちは
アルゴリズム関係の勉強が趣味のmaron8676です。
今回は、Rustでトライ木のベンチマークをとってみた結果を紹介します。
プログラムの速さを考える際に、アルゴリズムやデータ構造は重要な要素となります。
自然言語処理を勉強している中だと、トライ木と呼ばれるデータ構造が辞書検索タスクに有効であると良く言われます。
そこで実際どのくらい速さに違いが出てくるか確かめようと思い、最近勉強しているRustを使って、トライ木のベンチマークをとってみました。
1. プログラミング言語 Rust
簡単にRustについて紹介しておきます。
Rustは、2010年に登場した、比較的新しいプログラミング言語です。
比較的新しいコンパイル言語という点でGo言語と似たような立ち位置ですが、それと比べると
- Rustはより低レイヤのチューニングが行えるため、実行速度を上げやすい
- パターンマッチングなど、言語機能が充実している
といった良さがあります。
2. トライ木
トライ木は木構造と呼ばれるデータ構造です。
保存されたパターンの中で、先頭からの最長一致を検索する処理に優れています。
辞書検索タスクを行う場合の、データの保存形式を示したのが図1です。
各ノードが１つの文字列を表しており、ルートノードが空文字に相当するノードになります。
ノードの下についている数字は、単語に紐づけられた値で、実際の応用においては品詞情報などになります。
数字がついていないノードは、辞書登録されていない文字列と対応します。
また、各ノードは、より短いプレフィックスを表すノードの子になるよう構成されます。
例えば、teaのノードは、teノードの子になっています
プレフィックスを検索する際には、根のノードから入力と一致するノードをたどっていきます。
たどるノードがなくなった時点で見ているノードが、最も長いプレフィックスを表すノードとなります。
例えば、図1に対してteapotという文字列から最も長いプレフィックスを探す場合は、
「t」「te」「tea」と順にノードをたどります。次のノードがないため、最も長いプレフィックスは「tea」だと分かります。
図の引用元 トライ (データ構造) - Wikipedia
4. ベンチマークタスク
トライ木が有効なベンチマークタスクとして、辞書への最長一致を使った分かち書きを採用しました。
行う処理としては、以下になります。
- 文字列を入力とし、文字列が空になるまで処理を繰り返す。
- 辞書の中で一致する最も長い単語を検索する。見つからない場合は、入力文字列の１文字目が見つかったこととする。
- 見つかった単語で入力文字列を分割し、分割結果の後ろの文字列を入力として、1に戻る。
- 分割結果を出力する。
辞書の大きさは10万語とし、MeCab辞書から一部の名詞を抽出することで作成しました。
問題を簡潔にするために、単語表記は全てひらがなとしています。
また、実行環境は以下のようにしました。
| OS | Core i5 10400F |
| メモリ | 16GB |
| GPU | GTX Geforce 1650 |
トライ木による探索では、探索途中において最長一致する文字数が分かるようになっており、そこで処理を打ち切ることができます。
ハッシュ探索では、「１文字目」、「１～２文字目」、「１～３文字目」といった全てのパターンについて検索を実行しないと、
最長一致する文字列を特定することができません。
※事前情報として辞書登録された語の最大文字数が分かっていない場合を想定しています
5. ベンチマーク結果
結果は図2, 3のようになりました。
トライ木による探索を使った場合のタスク実行時間は、ハッシュ探索の場合の約半分となっています。
理由としては、「ベンチマークタスク」でも書いた、「最も長いプレフィックスを素早く検索できる」ことが主なものだと考えられます。
6. まとめ
トライ木を用いるのが有効と言われているタスクに対するベンチマークをRustで実行し、
ハッシュ探索を用いた場合より速くなることを実際に確認することができました。
Rustは細かいチューニングまで行えるため、ベンチマーク対象間の検索処理以外の違いを少なくできました。
アルゴリズムの選択ミスはやっかいなバグです。
データが小さい時には問題なく動作してもデータが大量になったときに致命的な問題となります。
そのため、データの特徴に合わせて適切なアルゴリズムを選択することが重要ですね。
7. 使用したライブラリの紹介
radix_trie: トライ木のRust実装
GitHub - michaelsproul/rust_radix_trie: Fast generic radix trie implemented in Rust
Criterion: Rustでベンチマーク計測を行うためのツール
GitHub - bheisler/criterion.rs: Statistics-driven benchmarking library for Rust
8. 今回の検証にあたり作成したプログラム
Acroquest Technologyでは、キャリア採用を行っています。
- ディープラーニング等を使った自然言語／画像／音声／動画解析の研究開発
- Elasticsearch等を使ったデータ収集／分析／可視化
- マイクロサービス、DevOps、最新のOSSを利用する開発プロジェクト
- 書籍・雑誌等の執筆や、社内外での技術の発信・共有によるエンジニアとしての成長
少しでも上記に興味を持たれた方は、是非以下のページをご覧ください。Kaggle Masterと働きたい尖ったエンジニアWanted！ - Acroquest Technology株式会社のデータサイエンティストの求人 - Wantedlywww.wantedly.com