■ 1. プロジェクト概要: Taskusanakirja (tsk)
- フィンランド語-英語辞書アプリ「Taskusanakirja（tsk）」の開発プロジェクト
- インクリメンタルな検索機能（入力に応じたリアルタイム検索）を備える
- 設計当初より、単一バイナリ（.exe、.app、静的リンクバイナリ）での配布を目標とする
- 「ポケット辞書（taskusanakirja）」のコンセプトに基づき、古いノートPCでも動作することを要件とする
- Go言語によるTUIプログラムとして開発を開始し、fzfプロトタイプ（finstem）から発展した経緯を持つ
- 本記事における数値はすべて最初の有効数字に丸めて表記している（Rob Eastawayの「zequals」手法に基づく）
■ 2. 初期実装: トライ木によるプレフィックス検索
- 実装内容:
- Go言語でトライ木（trie）を用いたプレフィックス検索を実装
- 上位50〜100件への絞り込みと、1〜3文字の組み合わせのメモ化により遅延を解消
- 基本的な最適化により約60MBのメモリ使用量を実現
- フィンランド語の特性による限界:
- フィンランド語は高度に膠着語的な言語であり、語幹1つから100以上の語形が生成される
- 子音交替（例: katu → kadun）と母音調和が同時に作用し、語形変化が複雑となる
- 15の格、2つの数、6つの所有接尾辞、不定数の付加詞の組み合わせにより、語形数が爆発的に増加する
- トライ木は接頭辞（プレフィックス）のみを共有するため、-ssa-mme-kinのような共通接尾辞を持つ数千の単語のコストを共有できない
- 40〜60万件の語形を格納しようとすると、トライ木では対応不可能となる
■ 3. 暫定解決策: SQLiteデータベース
- SQLite + FTS（全文検索）拡張機能を採用した暫定的な解決策を実施
- 検索遅延は体感上なく機能したが、初回ダウンロードに3GBを要するという問題を抱える
- この状態で約9ヶ月間停滞
■ 4. FST（有限状態トランスデューサ）による解決
- 発見の経緯:
- BurntSushi（Andrew Gallant）による記事「Index 1,600,000,000 Keys with Automata and Rust」からfstクレートを発見
- 有限状態機械を用いて文字列の順序集合・マップを圧縮表現し、前方一致・曖昧・後方一致検索が可能
- 実装と結果:
- Rust言語でSQLiteデータベースからデータを抽出し、FSTバイナリに変換するプログラムを実装
- 3GBのSQLiteデータベースを10MBのFSTバイナリに置き換え
- 約300倍のメモリ削減を達成
- FSTがフィンランド語辞書に特に適した技術的理由:
- FST（最小非巡回決定性有限オートマトン）はプレフィックスとサフィックスの両方を共有する
- トライ木は接頭辞のみを共有するのに対し、FST構造的に同一なサブツリーをすべて統合する
- フィンランド語では数十万の単語が同一の数十種類の活用パターン（接尾辞）を共有するため、FST構造との親和性が極めて高い
- データがランタイム時に静的であるため、fstクレートの主要な制約（動的更新不可）を回避できる
- Rustへの書き換えについて:
- 「Rewrite It In Rust（Rustで書き直せ）」はミームとして知られる
- 「高速性・移植性が求められ、既存ツールのメモリ効率に問題がある」場合には有効な選択肢となる
■ 5. v2.0.0の展望
- Pro版v2は全機能込みで約20MBとなる見込み
- v1の無料版（約60MB）の3分の1以下のサイズとなる
- v1で使用していたFTSを利用する一部機能はv2での削除が検討されている
■ 6. 反復的問題解決に関する考察
- 暫定的なSQLite解決策の採用が、後のFST最適解への到達の前提となった
- 問題を二度解くことの意義:
- SQLiteによる最初の解決策は機能し、B木やFTS拡張機能の仕組みへの理解を深めた
- 9ヶ月の実務経験を経て、より優れた解決策（FST）への到達が実現した
- 車輪の再発明に関する見解:
- 多くの分野では4〜5回、数学・計算機科学では20〜30回程度の再発明が、知識の最前線への到達を促進する
- 受動的な学習の同量の時間と比較しても、再発明と問いかけの実践の方が最前線への到達が速い
- カプランの観点「学校が職業スキルをほとんど教えない中で人はいかにして職業的熟達を得るのか—カーネギーホールへの道と同じく、練習によってである」を支持する
- 「Do Ten Times as Much（10倍やれ）」を、不快だが効果的なアドバイスとして挙げる