從 3 GB 到 10 MB：使用有限狀態轉換器優化前綴搜尋

當建立一個「邊輸入邊搜尋」的字典時，主要的技術挑戰在於高效的前綴搜尋。對於大多數開發者來說，首選方案是 trie (前綴樹)，它透過共享共同前綴來實現快速查找。然而，隨著數據集增長——特別是在處理黏著語 (agglutinative languages) 的複雜形態時——即使是經過優化的 trie 也可能變得大到無法負荷。

在最近一個名為 Taskusanakirja (tsk) 的芬蘭語-英語字典專案中，作者面臨了這個擴展性的瓶頸。最初一個可控的 Go 實作，最終卻需要一個 3 GB 的 SQLite 資料庫來處理數百萬個變形詞形式。解決方案是什麼？遷移到 Rust 並實作有限狀態轉換器 (Finite State Transducer, FST)。

挑戰：黏著語的複雜性

芬蘭語是一種高度黏著的語言，這意味著它透過在詞根上添加多個後綴來構建單詞。一個單詞詞根可能擁有超過一百種可能的結尾。這種複雜性因「子音變化」和「元音和諧」而進一步加劇，在添加後綴時，單詞本身的詞根也會發生轉變和變化。

對於語言學習者來說，能夠搜尋特定的變形形式並找到其詞根是至關重要的。然而，這會導致數據爆炸：

Tries 在規模擴大時會失效： 雖然 trie 可以高效地在 ~50 MB 的 RAM 中儲存 400,000 個項目，但若要在不消耗數 GB 記憶體的狀況下擴展到 4,000 萬至 6,000 萬個項目，則是不可能的。
「笨拙但簡單」的方案： 為了讓專案繼續進行，作者最初實作了帶有全文搜尋 (FTS) 功能的 SQLite 資料庫。雖然功能上表現良好，但它需要使用者下載 3 GB 的檔案——這與「輕量級口袋字典」的目標相去甚遠。

解決方案：有限狀態轉換器 (FST)

為了緩解記憶體危機，作者轉向使用了 Rust 中的 fst crate，其靈感來自 Andrew Gallant (BurntSushi) 的研究成果。

雖然 trie 僅共享前綴，但有限狀態轉換器（特別是最小無環確定性有限狀態自動機）同時共享前綴與後綴。

為什麼 FST 對芬蘭語有效

在像芬蘭語這樣的語言中，數千個不同的單詞通常共享相同的幾種常見變形模式（例如，結尾如 -ssa-mme-kin）。在標準的 trie 中，每個後綴實例都會被儲存為一條獨立的路徑。在 FST 中，任何結構上完全相同的子樹都會被合併。

這種「後綴共享」極大地提升了記憶體效率。透過使用 FST 將變形和詞形變化映射回其原始定義，作者將數據佔用空間從 3 GB (SQLite) 減少到僅 10 MB——實現了 300 倍的縮減。

工程經驗教訓：從「天真」開始的價值

這次優化過程中最深刻的啟發之一是「將問題解決兩次」的哲學。作者認為，從一個「笨拙但簡單」的方案（如 SQLite DB）開始，通常比從一開始就花數週時間研究完美的架構更為優越。

"SQLite 資料庫可以運作！我理解它的運作方式... 我認為將問題解決兩次是沒問題的。"

這種方法具有幾個優點：

立即驗證： 你可以證明該功能是可行且有用的。
參考實作： 天真的版本可以作為黃金標準，用來驗證高度優化版本之正確性。
降低風險： 你可以避免「分析癱瘓」，並確保專案能夠如期交付。

更廣泛的應用

FST 在此情境下的成功並不侷限於芬蘭語。正如社群討論中所提到的，類似的技術非常適用於其他黏著語，例如土耳其語或日語，其中單詞形成遵循類似的「詞根與後綴層疊」模式。

此外，所描述的數據結構與有向無環字圖 (Directed Acyclic Word Graph, DAWG) 非常接近，這是一種在過去幾十年中被重新發現的各種形式的結構，專門用來解決這類字典壓縮問題。

轉換摘要對照表

指標	初始 Go/Trie	中間 SQLite	最終 Rust/FST
儲存/RAM	~60 MB (有限集合)	3 GB	10 MB
搜尋類型	前綴	全文搜尋	前綴/模糊/後綴
可攜性	高	中 (外部資料庫)	極高 (靜態二進位檔)