5月10日、Andrew Quinnが「Replacing a 3 GB SQLite database with a 10 MB FST (finite state transducer) binary」と題した記事を公開した。この記事では、フィンランド語-英語辞書アプリで3GBのSQLiteデータベースを10MBのFST（有限状態変換器）バイナリに置換し、300倍のストレージ削減を実現した技術について詳しく紹介されている。

FST（Finite State Transducer：有限状態変換器）は、文字列の検索・圧縮において近年注目される技術だ。従来のトライ構造やハッシュテーブルと比べ、プレフィックスとサフィックスの両方を効率的に圧縮できる特徴を持つ。特にRustエコシステムでの実装が進み、大規模な辞書データ処理や全文検索エンジンでの活用が広がっている。オートマトン理論に基づくこの技術は、理論と実用性を両立した稀有な例として評価されている。

トライ構造からSQLiteへ、そして限界への直面

Quinnは「Taskusanakirja」（通称tsk）というフィンランド語-英語辞書アプリを開発している。このアプリはインクリメンタル検索機能を持ち、ユーザーが入力するとリアルタイムで検索候補を表示する。

当初の実装では、プレフィックス検索の標準的な解決策であるトライ（trie）構造を採用していた。Go言語で実装され、1文字、2文字、3文字の組み合わせをメモ化することで、約40万語を60MB程度のメモリで処理できていた。

しかし、フィンランド語は膠着語（agglutinative language）という特性を持つ。一つの基本語に対して100以上の語尾変化が存在し、これらの組み合わせは規則的でない。例文として挙げられた「Opiskelijassammekin on leijonan sydän」のように、初学者にとって単語の境界を判断するのは困難だ。

フィンランド語の複雑さは、印欧語族に慣れた開発者には想像しにくい。フィン・ウゴル語族に属するフィンランド語は、格変化（15の格）、所有接尾辞、語幹の変化が組み合わさり、一つの語根から数百の形態が生成される。この語形変化情報を含めると、データは4000万〜6000万項目に膨れ上がった。トライ構造では到底扱えない規模である。

苦肉の策：SQLiteデータベースの採用

時間と選択肢が限られる中、QuinnはSQLiteデータベースとFTS（Full Text Search）拡張を使った解決策を選択した。SQLiteのFTS拡張は全文検索を効率化するが、大量のインデックスデータが必要になる。この方法は動作したが、3GBのデータベースファイルが必要になった。

「ジャカルタの大学生の古いノートPCでも動作させたい」

この目標には程遠い結果だった。

FST（有限状態変換器）による革命的な最適化

9ヶ月後、QuinnはBurntSushi（Andrew Gallant）の記事「Index 1,600,000,000 Keys with Automata and Rust」を発見した。BurntSushiは高速grep実装であるripgrepの作者として有名で、同様の問題に対してFST（finite state transducer）を使った解決策を提示していた。

FST（有限状態変換器）は、オートマトン理論に基づく効率的なデータ構造である。その特徴：

• プレフィックスとサフィックスの両方を圧縮
• 順序付けられた文字列の集合やマップをコンパクトに表現
• 高速な前方一致、あいまい検索、後方一致検索が可能
• 構築後は不変だが、メモリ効率と検索速度に優れる

Rustのfstクレートは、この理論を実用的なライブラリとして実装している。同じ作者によるtantivy（全文検索エンジン）でも活用されており、実用性が証明されている。

驚異的な結果：300倍の圧縮率

RustのFSTクレートを使って実装した結果は驚異的だった。3GBのSQLiteデータベースが10MBのFSTバイナリに圧縮され、300倍の容量削減を達成した。

この大幅な圧縮が可能だった理由：

• フィンランド語では少数の人気サフィックスが頻繁に繰り返される
• FSTはプレフィックスとサフィックスの両方を圧縮する
• データは実行時に静的で、FSTの最大の弱点（更新コスト）を回避できる
• 辞書データの性質（アルファベット順ソート）がFSTの長所と合致

検索性能も向上した。メモリ使用量の劇的な削減により、OSのファイルシステムキャッシュが効率的に働き、レスポンス時間も改善された。

実用的な教訓

Quinnは重要な洞察を共有している：

「9ヶ月前、良い解決策を見つけられないか、何もしないかの選択肢に直面した時、私は『悪いが簡単な解決策』を選んだ。SQLiteデータベースは動作した！その仕組みも理解していた。」

この「不完全だが動作する解決策」があったからこそ、後により良い技術を発見した際に安価に実験できたのである。完璧を求めて開発を止めるより、段階的改善を重ねるアプローチの価値を示している。

未来への展望

tsk v2.0.0のPro版は20MB程度になる予定で、これは無料版のv1の3分の1未満のサイズである。FST技術は他の言語処理アプリケーションでも応用可能で、特に語彙が豊富な膠着語（ハンガリー語、トルコ語など）や屈折語での効果が期待される。

自然言語処理やデータ圧縮の分野では、機械学習による手法が注目されがちだが、このケースはオートマトン理論に基づく古典的な手法の威力を改めて示している。問題の性質を深く理解し、適切な理論を適用することで、劇的な改善が可能であることを証明した事例である。

詳細はReplacing a 3 GB SQLite database with a 10 MB FST (finite state transducer) binaryを参照していただきたい。