3GBのSQLiteデータベースを10MBのFST（有限状態変換器）バイナリに置き換える
(til.andrew-quinn.me)- Taskusanakirja は、入力中の接頭辞検索を提供するフィンランド語-英語辞書
- フィンランド語の活用形展開により項目数が 4,000万〜6,000万件 まで増え、トライが限界に達した
- 暫定的な SQLite FTS 解決策は高速だったが、初回に3GBのダウンロードが必要だった
- Rustベースの FST により、SQLiteデータを約10MBのバイナリへ縮小し、300倍の削減を実現した
- FSTは接頭辞と 接尾辞 の両方を共有するため、反復する活用パターンと相性が良い
Taskusanakirjaの検索構造と初期の限界
- Taskusanakirja、略して
tskは フィンランド語-英語辞書 で、入力しながら段階的に検索できる機能を提供する - この機能は本質的には 接頭辞検索 の問題であり、自動補完向け接頭辞検索の定石的な解法は トライ の実装だった
- 最初の実装は Go で書かれ、プログラム全体を1つの
.exe、1つの.app、または1つの静的リンクバイナリとして配布することが初期設計の目標だった - 数十万語規模では、全体のうち一桁パーセントに相当する大量一致を避けるため、最初の50件または100件程度の結果だけを返し、1・2・3文字の組み合わせをメモ化していた
- この方式により、基本的な最適化を施したトライを約 60MB の容量内に収めることができ、1年間個人的に多用しても体感上の遅延はなかった
フィンランド語の活用データが生んだ規模の問題
- フィンランド語は 膠着語 であるため、1つの基本語が全組み合わせを考えると 100を超える語尾 を持ちうる
- その組み合わせは規則的ではなく、非常に規則化されたフィンランド語の正書法は、実際の話者が発する形をそのまま文字に反映するため、基本語は語尾と結びつく中で増え、移動し、変形する
- 初級学習者は
Opiskelijassammekin on leijonan sydänのような文で特定の単語に詰まりやすく、tskは単語を正しい境界で分割するのに役立つ情報も含めようとしていた - 言語学的には、このような変形は 子音交替 と 母音調和 に当たり、フィンランド語はその両方を同時に用いる
- たとえば
katuは “street” を意味するが、属格はkatunではなくkadunであり、閉音節のためtがdに弱化する - この構造に 15の格、2つの複数、6つの所有接尾辞、不定数の接語を掛け合わせると、素朴なトライでは
-ssa-mme-kinのように何千語もが共有する語末部分のコストを分担できない - 約 40万件の項目 はトライで約50MBのRAM内に保持できたが、同じ方式は4,000万〜6,000万件へは拡張できなかった
- 暫定策として活用形を別の SQLite FTS データベースに入れて必要時に検索するようにしたところ、体感上の遅延なしに動作したが、初回に 3GBのダウンロード が必要だった
RustとFSTに切り替えた結果
- 9か月後、Rustで再挑戦する中で、3GBのSQLiteデータベースからデータを取り出して FST に圧縮する最小のRustプログラムを書いた
- きっかけは BurntSushi aka Andrew Gallant の記事 Index 1,600,000,000 Keys with Automata and Rust であり、有限状態機械が文字列のソート済み集合やマップを小さく高速に表現できる点が核心だった
- 結果のバイナリは約 10MB となり、3GBのSQLiteデータベースに比べて約300倍の容量削減となった
- この用途は fst crate にも特によく適合していた。というのも、高度に膠着的な言語の活用形・屈折形を元の定義へ戻してマッピングする問題だったからだ
- トライは 接頭辞 を圧縮するが、FSTは接頭辞と 接尾辞 の両方を圧縮する
- フィンランド語辞書コーパスには、非常に高頻度で反復される人気の接尾辞が少数存在するため、接尾辞共有が大きな効果を生む
- データは実行中に変更されない 静的データ なので、
fstの最大の弱点を回避できた
FSTがトライより小さくなった理由
- FSTを自然言語データでトライよりはるかに小さくする鍵は 接尾辞共有 にある
- トライは
kadunとkaduilleが先頭3ノードを共有するように接頭辞を共有するが、異なる接尾辞の経路はそれぞれ別に保存する - 最小非循環決定性有限オートマトン は、構造的に同一な2つの部分木を統合する
- 10万語が同じ12種類前後の活用パターンで終わるようなコーパスでは、この統合が大きなメモリ節約につながる
- この事例の核心的なヒューリスティックは、その場しのぎで作った汎用データベースを、必要な仕事だけを正確に行う小さく静的な専用データ構造へ置き換えることで 300倍のメモリ削減 を得ることにある
暫定SQLite解決策が残した役割と配布サイズ
- 9か月前にSQLiteを選んだのは、「良いものができずに何もしない」より「悪くても簡単なもの」を選んだ結果であり、実際に動作した
- SQLiteのB-treeと Full Text Search extension を理解していたため、当時としては素早く試せる解決策だった
- 同じFTS拡張は
tsk v2.0.0アルファにない、あまり使われない一部機能にも使われたが、現在のメモリフットプリントを損なうなら完全に削除される可能性がある v2のPro版は、すべてを含めて約 20MB を見込んでおり、これはv1無料版より3倍小さいtskはもともとTUIのGoプログラムとして始まり、以前のfzfベースのプロトタイプfinstemから発展したもので、the highest-ROI program I’ve written so far ともつながっているtaskusanakirjaはフィンランド語で “pocket dictionary” を意味し、古いノートPCにも入らないならポケット辞書ではなく、コンパイルされる古いOxford辞典に近い、という基準が維持されている- 「問題を2回解いてもかまわない」という繰り返し現れる形があり、既存のより良い実装を探さなければという罪悪感で立ち止まるより、いくつかの車輪を自分で再発明したほうが、実際の限界により早く到達できるという見方が示されている
- この見方は Caplanian view の「練習」と結びついており、Do Ten Times as Much が不快ではあるが有効な助言として示されている
1件のコメント
Lobste.rsの意見
記事そのものも興味深く、適材適所のツールを適切な仕事に当てて一桁台の改善を得ているのが良かったが、本文より最後の脚注のほうがさらに印象的だった。
今作っているツールは、すでに30〜40年前に誰かがもっとうまく実装していたかもしれない、という罪悪感のせいで立ち止まってしまう悩みを正確に言い当てている。だがそれは罠であり、車輪をいくつかは作り直してみないと、車輪作りの限界までは行けない、という言葉が刺さった。たいていの分野では4つか5つで十分で、数学や計算機科学のような厳密な分野でも23個ほどで足りるかもしれず、そうやって自分で作り直しながら投げかける問いが、ただ勉強するよりはるかに速く本当の最前線へ連れていってくれる、という主張である。
まず何かしら動く参照実装があったからこそ、それを置き換える効率的な実装を作りやすくなった。
ただ、既存の解法を見ると自分には不要な荷物がたくさん付いている。経験上、自分のアイデアを押し通す価値があると分かっていながら、何か見落としているのではないかとずっと思っていたが、これを読んでとにかくやってみることにした。失敗しても、その過程で学べることがある。
とても素晴らしい。Compressing Icelandic name declension patterns into a 3.27 kB trieを思い出した。
Scrabbleボットを実装していて、DAWG(Directed Acyclic Word Graph) という関連データ構造を知ったが、その用途ではかなり一般的なようだ。
fstクレートとの主な違いは、各単語を一意な整数にマッピングしない点のように見える。同様にサイズが大きく減り、性能も驚くほど向上した。Scrabbleボットは基本的に..cat..のような単純な正規表現に一致する単語で辞書全体をフィルタしなければならないが、実際には現在の盤面で可能なあらゆる単純な正規表現を処理する必要がある。1分ほど待っていた処理が、体感できないほどの遅延にまで縮んだ。リンク先の記事も読む価値がある: https://burntsushi.net/transducers/
fstは、srgnのドイツ語サポートでも最終的に使うことになったツールで、Andrewが直々に勧めてくれた後のことだった。共通の接頭辞と接尾辞を圧縮するという同じ問題空間で、本当によく機能する。さらにCLIツールなので起動コストの最小化も必要だったが、
fstクレートはゼロコピー読み込みをサポートしており、ランタイムオーバーヘッドがない。FSTはコンパイル時点で生成される。本当に素晴らしいし、ドイツ語と英語にもこういうものがあればいいのにと思う。ドイツ語の複合語は今でもしばしば自分を混乱させる