LuceneのMappingCharFilterでのFSTから見えたアルゴリズム選定の難しさ
🎄この記事はNAVITIME JAPAN Advent Calendar 2023の21日目の記事です。
こんにちは、co-yarnです。地点検索システムの研究開発を担当しています。
今日は FST という(ちょっとマニアックかもしれない)オートマトンについてお話していきたいと思います。
当社では、全文検索ライブラリエンジン「Lucene」をベースにした「Apache Solr」という全文検索システムを使用しています。
今回は、そのLuceneに実装されている「MappingCharFilter」で FST が利用されていることに着目し、MappingCharFilterでFSTが利用されるに至った経緯と、FSTの特性について調べてみてわかったことをまとめていきます。
今回話す内容をまとめると以下のようになります。
LuceneでFSTが最初に使われたのは2010年で、インデックス処理で使われた
LuceneのMappingCharFilterでFSTが使われるようになったのは2012年で、実装の単純化とメモリの軽量化＋高速化が期待されて導入されたが、期待されたほど速くならなかった
Rustで実装されたFSTのパフォーマンス計測の結果から、FSTは汎用的な用途には向かず、キーの数が多い（数十万以上）などの状況なら使えそう
アルゴリズムやデータ構造、計算量の概念などが記事中に出てくるため、メインの対象読者は検索システム(SolrやElasticsearch/OpenSearch)やLuceneを使っている人や計算機科学を学んでいる人、もしくはアルゴリズムが好きな人向けとなっています。
それ以外の方にもなんとなく雰囲気がつかんでいただけるよう、なるべく噛み砕いて書いていこうと思います。
きっかけ
今年2023年の9月に、当社から通称住所についてのお知らせをリリースしました。その土地に住んでいる人によって慣習的に使われている住所（通称住所）の一部を、データ整備することで検索でヒットできるようにした、という内容です。
上記のお知らせにもありますが、例えば「東京都稲城市大字大丸四号123-1」という住所検索をしたとき、法律で定められている「東京都稲城市大字大丸123-1」という住所がヒットするようになりました。
お知らせをリリースしてから、各方面から反響いただき、対応してよかったなと思っております。今回のお話はこの対応の裏であったことから話が始まります。
通称住所についての対応は「通称住所が既存のデータのどの住所にあてはまるのか」というデータを自社で独自に作成し、検索データの作成時に住所を置換するという処理を入れることで実現しています。
もう少し検索システム的に言うと、住所検索をする際に、MappingCharFilter を使って検索する文字列を置き換えすることで実現しています。
検索システムを触ったことがある方ならご存知かと思いますが、MappingCharFilter自体はインデクシングや検索の際に、設定された置換ルールで文字列を置き換えるという、いたってシンプルな処理を行うものです。例えば、漢数字を英数字に置き換える用途など、ごく一般的に使われるものです。
今回の通称住所の対応では、通称住所と正式な住所の組み合わせのデータを約19000件作成し、 MappingCharFilter の置換ルールとして登録しています。この対応を進めているとき、ある1つ疑問が生まれましたーー「こんなに置換ルールを追加して大丈夫なの……？」
実際のところは、めちゃくちゃ数が多いというわけでもないので、このぐらいの件数なら、おそらくまだ問題はないだろうという予想をしていましたし、もちろんリリースする前にはパフォーマンス評価を行って、実際に問題ないことを確認していました。
しかし、気になってしまったからには調べないと気がすまない、ということで Lunene の実装を追ってみることにしました。その結果、 FST に行き着き、ここから 「FSTとはどういうものだろうか」を追う旅が始まりました。
FSTとは
Finite State Transducer (FST: 有限状態変換機) と呼ばれる、有限オートマトンです。この記事では、（少し乱暴な言い方ですが、）FSTを「ある文字列に対応する文字列を返却する辞書のようなもの」と思ってください。
どのように対応する文字を探すか、ざっくりと言うと、「前から1文字ずつ当てはまる文字があるか見ながら、出力する文字列を作っていき、最後まで見たときにその文字列があることがわかれば、対応する文字列を出力する」という流れになります（文章で書きましたが、この流れはオートマトンの動きそのものです: オートマトンについての解説はこちら）。
FSTについての詳しい日本語記事が他にあるので、以下の記事もご参照ください。
FST自体は汎用的なもので、あいまい検索や正規表現など、自然言語処理や音声認識の分野で利用されているようです。
今回のお話では、 Lucene の MappingCharFilter で利用されている用途についてのみ対象とするので、概ね連想配列と同じようなものとして考えていただいて問題ありません。
Lucene での FST が導入されるまでの経緯
LuceneでのFSTは、前節で紹介した 『Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待）』 でも書かれている通り、単なるFSTではなく、正確には「Minimal Acyclic Subsequential Transducer」 と呼ばれる最小で決定的であるという性質を持ったFSTが実装されています。本来はFSTというと、最小でないものや決定的でないものも含まれています。当時既に OpenFST というFSTの実装が存在しており、このようなFSTについて扱えるようになっていました。
しかし、Luceneでは最小で決定的であるFSTを使うことでできれば十分ということで、入力がソート済であることを要請する代わりに構築が簡単な「Minimal Acyclic Subsequential Transducer」が採用されたようです（このnoteでは、以後 Luceneの実装についても単にFSTと呼称します）。また、FSTには「FST同士で合成できる」という性質も持っていますが、ソースコードを調べた限りLuceneではFSTの合成も実装されていませんでした。
最初にLucene に FST が導入されたのは2010年でした（対応チケット「Add a simple FST impl to Lucene」参照）。
最初にFSTが利用されたのはインデクシング処理で、導入した結果省メモリと高速化に寄与したそうです（ブログ「Using Finite State Transducers in Lucene」参照）。
一方で、MappingCharFilterにもFSTが使われるようになったのは、2012年のことでした（対応チケット「MappingCharFilter could be improved by switching to an FST.」）。
もともとの MappingCharFilter は "複雑な木構造(complex tree like structure)" （変更前の実装を見る限り、HashMapを使ったTrie木のようなもの）を使って実装されていました。そこで、FST に置き換えることで、実装がシンプルになり、加えてメモリの軽量化＋高速化が期待されていたようです。
MappingCharFilter stores an overly complex tree-like structure for matching input patterns. The input is a union of fixed strings mapped to a set of fixed strings; an fst matcher would be ideal here and provide both memory and speed improvement I bet.
しかし、その後のコメントを見ると、用意したテストケースでパフォーマンスを計測したところ期待されたほど速くはならなかった様子が伺えます。むしろ単純に実装しただけでは遅くなってしまい、ローリングバッファと事前に遷移先へのキャッシュを持つことでなんとか許容できるパフォーマンスになったようです。
New patch: I made a simple perf test (attached:
PerfTestMappingCharFilter.java), and found the FST was slower... I
fixed RollingCharBuffer to bulk read, and also pre-cache the FST arcs
in a HashMap (FST pre-caches only latin bytes), and now perf is a bit
faster. I also switched to builder API (like SynFilter) so
the NormalizeCharMap instance is immutable.
I think it's ready!
(後略)
インデクシング処理ではどの程度高速化・省メモリ化されたかは発表されていますが、 MappingCharFilterでは最終的にどの程度高速化・省メモリ化したかは、（もしかしたら別の媒体に記録されているかもしれませんが、）少なくとも対応時のチケットには情報は見つかりませんでした。
もう少し詳しくみていくために、 FSTはどのように実装されているのか、またMappingCharFilterでFSTがどのように使われているのか追っていくことにしました。
MappingCharFilter で FST がどう作られどのように使われているのか？
Luceneはオープンソースであるため、GitHubにコードが公開されています。そのため、実際にGitHub上に公開されているコードを読むことで、どのように実装を読み解いていくことができます。今回はMappingCharFilterとFSTについて追っていきたいため、以下ファイルについてソースコードを確認していきました。
MappingCharFilterでFSTが作られるところから文字列の置換が行われるまでの流れを、以下に簡単にまとめます。上2つがFSTの構築、下2つがFSTの利用での処理となっています。
MappingCharFilter用の置換ルールが記載された設定ファイルが読み込まれ、1行ずつパースしながら同時にソートする
パースされた置換ルールについて昇順に、置換前の文字列をUTF-16でエンコードして2byteごとに分割したものを入力とし、置換後の文字列をchat配列として扱ってFSTを構築（このFSTはバイト列に圧縮される）
構築したFSTをMappingCharFilter（より正確にはNormalizeCharMap）で利用し始める前に、あらかじめ一番最初の頂点からの遷移先の辺の情報をバイト列から読み出して、HashMapにキャッシュする
置換対象の文字列を受け取り、その文字列の置換開始位置をずらしながらFST上で1文字ずつ検索を行い、一致する文字列のなかで最長のものを検索し置換後の文字列に置き換えを繰り返す。もし一致するものがない場合、1文字だけ置換開始位置を進めてから、再度検索を行う
「Minimal Acyclic Subsequential Transducer」の構築時の特徴ですが、FSTの構築時になされている工夫として、更新されることがないと確定した状態や遷移については、情報を圧縮してバイト列に格納することでFST構築中のメモリ使用量を減らしていているようでした。余談ですが、FSTを構築するクラスの名前が「FSTBuilder」ではなく「FSTCompiler」となっていることに最初違和感を覚えていたのですが、「情報を圧縮してバイト列に格納する」処理が理由なのかなと（個人的に）解釈しています。
Luceneでの処理について追ってみたところで、ここから文字列を置き換える処理での計算量について考えてみます。
置換したい文字列の長さをKとします。まず、FSTに検索している文字列があるかを検索することになりますが、これは文字列の先頭から1文字ずつ状態を遷移させて探していくため、最悪O(K)の計算量となります。
なお、厳密にはLuceneの実装では、（最初の遷移以外は）遷移数に応じて線形探索 or 二分探索を使い分けて目当ての遷移が存在するか探していくため、もう少し計算量は異なります。ですが、話が複雑になるため、今回は線形探索で遷移数（＝文字の種類数）は一定という仮定の元で話を続けます。
入力と置換対象の文字列の両方とも同じ文字列パターンが繰り返されるが、置換対象の部分文字列に入力と一致するようなものがないようなケースを考えると、1文字ずつ削れる文字列に対して、毎回文字列の長さ分検索を行うことになるので、最終的な文字列置換の計算量は最悪O(K^2)であることがわかります。
余談ですが、このような文字列検索に対して、Aho-Corasickのアルゴリズムを用いるとどのようなケースでもO(K)になることが知られていますが、Luceneのソースコードの中でもこのアルゴリズムで高速化できるのではとコメントで言及されていました。
比較として、元の "複雑な木構造" (HashMapを使ったTrie木)で検索する場合の計算量を考えてみるのですが、実はこちらも検索時に1文字ずつ当てはまる文字がないか探していくため、文字列置換の計算量はFSTと同じく最悪O(K^2)となります。
したがって、最悪計算量は両方とも（仮定の元では）差がないことになります。これ以上については、（前述した通り）チケットなどに詳細の情報がないため、結局FSTをそのまま実装した場合でパフォーマンスが悪かった理由は残念ながらはっきりしませんでした（なお、実際にパフォーマンスを取り直してみるとはっきりするかもしれませんが、時間の都合上今回は行っておりません）。
ここからは推測ですが、最初の遷移部分だけHashMapでもつことで高速化したことから、FSTから遷移についての情報をデコードする処理が想定よりも重かったのではないかと考えています。
個人的には調べていてたくさん発見があったので、収穫としては十分だったのですが、最後にLuceneとは直接関係しないですが、FSTのパフォーマンスについて述べられた面白い記事を見つけましたので、そちらを簡単に紹介しようと思います。
FSTの特性について
BurntSushiさんという方が Rust で FST を実装してライブラリとして公開していました。FSTの構築方法については、LuceneのFSTと同じく「Minimal Acyclic Subsequential Transducer」として実装されています。この方は、なんとFSTを実装しただけではなく、自作のFST について詳細なパフォーマンス計測を行っていました。この計測結果を読み解いていくと、FSTのパフォーマンスについて興味深いことが書かれていました。
いくつかテストがなされているのですが、自作のFSTの性能評価をするためのテストの1つに、文字列を含まれているか判定する処理でBTreeSetとの性能差の比較がされていました。このテストの結果では、置換対象を単語のような文字列で計測した場合、5倍程度BTreeSetの方が高速であったこと、一方で置換対象になる文字列をURLのように長くなるようなデータセットで比較すると、速度差は2.7倍程度にまで縮まったことがわかったそうです。
データセットの数を N、データ（文字列）の長さを K とすると、BTreeSetの計算量はO(K logN)と、FSTの計算量の O(K) よりも大きくなっています。なので、比較回数自体はFSTのほうが少なくなっています。
作者の考察によると、FSTでの状態と遷移をデコードするための処理よりも、BTreeSet のキーへのアクセスのほうがかなり速いことが原因だとされています。またデータの長さが長いケースだと、FSTとBTreeSetの速度差が縮まるような結果が得られたことから、作者の予想では、「データの数が多く、データ（文字列）の長さが長いほどFSTが有利になってくるのでは」と考えられています。
ちなみに、HashSetとも比較がなされていました。結果は文字列の長さによらず、FSTと比べて約10～11倍程度HashSetのほうが高速という結果になっていました。筆者は、HashSetに対しては同じく計算量が O(K) であることから、HashSetよりも高速にはならないだろうと考えているようです。
最後に作者は、BTreeMapやHashMapと比べて、FSTは汎用的な用途には向かないと結論づけています。FSTを利用するかのチェックポイントを4つほど挙げていますが、そのうちの1つに、キーの数が数十万個以上になるかどうかがありました。具体的な数については実装や言語にもよると思われますが、たくさんのキーがある状況というのがFSTの優位性が発揮しやすい状況であると思います。
最後に
Rustで実装されたFSTの話を受けた上で、Luceneでの「（単純な実装だと、）MappingCharFilterでFSTを使った場合、想定していたよりも速くならなかった」という話を考えてみると、色々と理由が考えられそうな気がしてきます。
ですが、Rustで実装されたFSTの話を、そのままJavaで実装されているLuceneの話に適用することはできません。そのため、厳密に話をするにはLuceneの方でもRustでの実装と同様のテストをおこなうことが必要になってくると思います。今回はそこまで手が回らないため、ここまでとなりますが、もし読者の方で興味がある方がいたらやってみてください。
ということで、ここまで長いnoteを最後まで読んでくださり、ありがとうございました。「調べたことをまとめていくだけ」と考えていましたが、思った以上に深い話になってしまいました。
なお、余談ですが、実は初稿ではRustの話をJavaの話に適用したまま話を進めてしまっていて、同僚にツッコミをいただき、軌道修正いたしました（ありがとうございます）。改めてアルゴリズムやデータ構造のパフォーマンスについての奥深さと難しさを感じることができてよかったです。
皆さんもぜひ、ライブラリの裏側で走っているアルゴリズムに思いを馳せてみるのもいかがでしょうか。