3 GB から 10 MB へ：有限状態トランスデューサ (FST) による接頭辞検索の最適化

入力中に検索を行う辞書を構築する場合、主な技術的課題は効率的な接頭辞検索です。ほとんどの開発者にとって、即座に思い浮かぶ答えは Trie です。Trie は小規模から中規模のデータセットには直感的で効果的ですが、複数の形態素を繋ぎ合わせて単語を形成する「膠着語」の言語的な複雑さに直面すると、苦戦することになります。

フィンランド語-英語辞書の Taskusanakirja (tsk) の場合、開発者はスケーリングの壁に直面しました。Trie は 400,000 個の項目を約 50 MB の RAM で処理できましたが、4,000万〜6,000万の屈折形へとスケールアップすると、メモリ使用量が爆発的に増加しました。暫定的な解決策として、Full Text Search (FTS) を使用した 3 GB の SQLite データベースが採用されましたが、これは機能的には動作するものの、「ポケット辞書」を目指すツールとしては、配布における巨大なハードルとなりました。

課題：膠着性と Trie の限界

フィンランド語は高度に膠着的な言語であり、一つの基本語が 100 以上の異なる語尾を持ち得ることを意味します。この複雑さは、子音階梯や母音調和によってさらに増幅されます。つまり、接尾辞が追加されるにつれて、基本語が変化・変容するのです。

データ構造の観点から見ると、標準的な Trie は接頭辞を共有するため効率的です。「kadun」と「kaduille」という単語がある場合、それらは同じ初期ノードを共有します。しかし、Trie はすべての異なる接尾辞パスを個別に保存します。100,000 個の単語がすべて同じ 12 個の屈折パターン（例えば -ssa-mme-kin など）で終わる可能性がある言語において、Trie はそれらの接尾辞を数千回も冗長に保存してしまいます。

解決策：有限状態トランスデューサ (FST)

これを解決するために、開発者は Rust の fst crate を介して実装された有限状態トランスデューサ (FST) へと舵を切りました。Trie は接頭辞のみを圧縮しますが、FST（具体的には、最小化された非巡回決定性有限状態オートマトン）は、接頭辞と接尾辞の両方を圧縮します。

構造的に同一な2つの部分木をマージすることで、FST は共通の接尾辞の冗長性を排除します。繰り返される屈折パターンが支配的なコーパスにおいて、これは「メモリを印刷するためのライセンス」とも言えるものです。その結果、驚異的なサイズ削減が実現しました。3 GB の SQLite データベースは 10 MB の FST バイナリに置き換わり、スペースを 300 倍削減することに成功しました。

なぜ Rust なのか？

Rust への移行は単なるトレンドではなく、実用的な選択でした。著者が述べているように、Rust は、高速であること、ポータブルであること、そして「厄介なメモリ・エルゴノミクス」に対処する必要があるプロジェクトにおいて、特に効果的です。

設計思想：「不適切な」解決策の価値

この移行から得られる最も洞察に満ちた教訓の一つは、初期の、最適ではない実装の役割です。開発者は、SQLite が完璧なツールだったからではなく、単に「動作する、手軽で不適切な」手段だったから、最初に SQLite を使用しました。

このアプローチにはいくつかの利点があります：

即時の検証: SQLite データベースは、機能が実現可能であることを証明し、パフォーマンスの基準値を提供しました。
リファレンス実装: 素朴なバージョンは、最適化された FST 実装が同じ結果を生成することを確認するための、正解（ground-truth）として機能します。
迅速なイテレーション: 問題を「二度」解くことで、複雑なデータ構造にコミットする前に、問題の制約をより深く理解することができます。

あるコメント投稿者が指摘したように、「SQLite は正しい不適切な解決策だった」のです。それにより、プロジェクトを前進させつつ、開発者が高性能な代替手段を実装するために必要なエンジニアリング経験を積むことができました。

幅広い応用範囲と類似の構造

FST アプローチはフィンランド語に限ったものではありません。トルコ語や日本語のような他の膠着語にも非常に適応可能です。さらに、この構造は、競技プログラミングや言語学で使用される他の特殊なデータ構造、例えば Directed Acyclic Word Graph (DAWG) や、Scrabble ソルバーが大規模なデータセットを小さな L3 キャッシュに収めるために使用する GADDAG 辞書などと深い関係があります。

汎用的なデータベースから特化型の静的データ構造へと移行することで、Taskusanakirja は重いインストールから、軽量な 20 MB の「オール・バッテリーズ・インクルーデッド（すべて込み）」のバイナリへと進化しました。これは、適切なデータ構造の選択が、ハードウェアの増強よりも大きな効果をもたらすことが多いということを証明しています。