給 Numberphiles 的備註：所有數字都已四捨五入到其第一個有效數字，因為我是 Rob Eastaway 的「zequals」方法的粉絲，該方法在估計時能直奔重點。更有價值的是能得到一個啟發：「某人透過將他自己拼湊的資料庫替換成一個微小、靜態、專用的資料結構，該結構能精確地完成他所需的功能且不多餘，從而實現了 300 倍的記憶體縮減。」
這個週末，我獲得了一個越來越難得的機會，可以著手處理 Taskusanakirja（也常被稱為 tsk），這是一個芬蘭語-英語字典，具備漸進式的即時搜尋功能。¹ 這個問題本質上歸結為前綴搜尋，而前綴搜尋與自動完成的標準解決方案是實作一個 Trie（字典樹）。
這在 tsk 的第一個實作版本中效果非常好，該版本是用 Go 寫的（我曾在其他地方寫過關於它的文章）。加上一些基本的優化。為了防止匹配到我們嵌入二進位檔案中的數十萬個單字中的一小部分百分比（從一開始的設計目標就是將整個程式作為一個 .exe、一個 .app 或一個靜態連結的二進位檔案發佈），我們設定了一個限制，例如只顯示前 50 或 100 個匹配項，然後我們將所有 1、2 和 3 個字元的組合進行了快取，之後一年多的重度個人使用中，我再也沒有注意到程式有任何延遲。透過一些基本的優化，我們大約能將一個 Trie 塞進大約 60MB 的空間。
但芬蘭語是一種高度黏著的語言。一個單一的詞根在考慮所有可能的結尾後，可能會有超過一百種變化。而且這些組合並不規則！² 芬蘭語極度規則化的拼寫也意味著在口語實際書寫時沒有虛構，這意味著詞根在添加結尾時會以聽起來悅耳的方式延伸、轉變和變異，這在你已經沉浸在這門語言中幾年後是完全可以理解的。當你還是初學者時，看到像「Opiskelijassammekin on leijonan sydän」這樣的句子，有一個詞你會特別容易卡住。這個工具試圖做的一部分就是透過嵌入所有這些資訊，幫助學生弄清楚如何在正確的邊緣切開單字。
Trie 在這一點上就失效了。我可以將大約 400,000 個項目保留在 Trie 中，佔用大約 50MB 的 RAM。但同樣的技巧無法擴展到 4000 萬到 6000 萬個項目。如果你希望所有這些都能在雅加達一位大學生的舊筆記型電腦上運行，那就更不可能了。沮喪且時間緊迫，我放棄了，說：「我們將把這些變格詞放在一個獨立的 SQLite 資料庫中，並使用 FTS（全文搜尋），如果他們實在很絕望，就讓他們在那上面搜尋。」這確實奏效了——仍然沒有明顯的延遲——但需要一次性下載 3GB 的資料。這並不理想！
這就是大約 9 個月前故事停滯的地方。這個週末，在累積了 9 個月的密集全職軟體工程經驗後，我大膽地問：我是否考慮過用 Rust 重寫它？³
原來有一位非常非常聰明的人，名叫 BurntSushi，又名 Andrew Gallant，他以 ripgrep 聞名，這是一個非常非常快的 grep 工具——一個如此普遍有用的工具，我多年前就將它列入了我的現代 shell 命令的「聖三位一體」之中——他也曾在過去面臨過類似的問題，並寫了一篇名為「Index 1,600,000,000 Keys with Automata and Rust」的文章。（警告：內容冗長，極其有趣。）開頭就劇透了：
原來有限狀態機不僅可以用於表達計算。有限狀態機也可以用來緊湊地表示字串的有序集合或映射，這些集合或映射可以非常快速地進行 [前綴、模糊、後綴] 搜尋。
嗯，我心想，這聽起來很有希望。讓我們寫一個最小的 Rust 程式，將數據從那個 3GB 的資料庫中提取出來，並將其壓縮成這些 FST 小玩意之一。⁴ 我的意思是，這一直很明顯是一個權宜之計，但這是我當時在時間和精力允許下能做到的最好的權宜之計。我們能把它弄得多小？
十 _兆_位元組。空間縮減了 300 倍。即使在 fst crate 的使用者群體中，這個特定的應用程式——將高度黏著語言的變位和變格映射回其原始定義——也非常適合這個領域。與 Trie 不同，FST 可以壓縮前綴和後綴，而在像芬蘭語這樣的語言中，有極少數流行的後綴在字典語料庫中會被極其頻繁地重複使用。數據負載在運行時是靜態的，這克服了 fst 的最大弱點。
我確實想指出，當然，能夠廉價地進行實驗並偶然發現這種機遇的原因是，9 個月前，面對「做糟糕的簡單事情」或「做好的什麼都不做」的選擇時，我選擇了做糟糕的簡單事情。⁵ SQLite 資料庫確實有效！我理解它的工作原理，背後有 B-tree 和全文搜尋擴展。我認為我甚至使用了相同的 FTS 擴展來支援某些較少使用的功能，這些功能目前不在 tsk v2.0.0 的 alpha 版本中，並且如果意味著要犧牲現在令人垂涎的記憶體佔用空間，很可能會被完全刪除。
因為 v2 的專業版預計將約為 20MB，包含所有功能，這比 v1 的免費版要少三倍。我們將看看最終哪些功能會被保留下來。
tsk 最初是一個 TUI Go 程式——實際上它演變自一個更早的 fzf 原型，稱為 finstem，這是我迄今為止投資回報率最高的程式。¹ 「袖珍字典」的框架（taskusanakirja 在芬蘭語中字面意思是「袖珍字典」）一直是核心：如果它無法裝入一個人可能從叔叔那裡繼承來的塵土飛揚的筆記型電腦，那它就不是袖珍字典，而是一本碰巧能編譯的舊牛津字典。  ↩︎
語言學家將後綴觸發的變形稱為輔音遞變和元音和諧，芬蘭語同時運用這兩者。以 katu（「街道」）為例，其屬格不是 katun 而是 kadun——t 軟化為 d，因為音節閉合了。將此乘以 15 個格，然後是 2 個複數，然後是 6 個所有格後綴，然後是某些不確定的附加語數量，你就可以明白為什麼一個天真的 Trie 會失敗。它根本無法分攤成千上萬個以 -ssa-mme-kin（「在我們的 [X] 中，也」）結尾的單字的成本。  ↩︎
「用 Rust 重寫」已經是一個足夠流行的梗，以至於出現了整個類型的部落格文章來反駁它。這個梗的一個誠實版本是：如果你的問題處於「需要快速」、「需要可移植」和「現有工具的記憶體人體工學很糟糕」的交集，Rust 可能會讓你如魚得水。  ↩︎
使 FST 比 Trie 在自然語言數據上更緊湊的技巧是後綴共享：Trie 共享前綴（因此 kadun 和 kaduille 共享它們的前三個節點），但獨立儲存每個不同的後綴路徑，而最小的無環確定性有限狀態自動機則合併任何兩個結構相同的子樹。對於一個語料庫，其中 100,000 個單字都以相同的十幾個屈折模式結尾，這簡直是印鈔票的許可證。  ↩︎
這是我在這裡的筆記中不斷遇到的重複模式，即「解決一個問題兩次是可以的」。可以說，在我生命的頭二十五年裡，雖然我一直對程式設計著迷，但我總是無法克服一種罪惡感，那就是我不知道我現在正在構建的工具是否已經被別人 30 或 40 年前寫的某個好得多的實現所取代；例如，我可以編寫一個支援 TSV 的搜尋和替換，或者我可以了解 awk 並一舉解決整個類型的問題。我的核心觀點是這是一個陷阱。你需要重新發明幾個輪子才能達到我們對製輪知識的邊緣，而不是一千個輪子，也不是零個；在大多數領域，四五個輪子可能就足夠了，在數學或電腦科學等知識最嚴謹和發達的領域，可能接近二十或三十個。你重新發明的每一個輪子，以及沿途提出的每一個有針對性的問題，都將比花費相同時間進行空泛學習推動你更快地到達真正的邊界。這本質上是一種 Caplanian 的觀點：「如果學校教授的就業技能很少，學習的轉移大多是空想，教育對智力的影響基本上是空洞的，那麼人類如何才能在工作中變得出色呢？這和去卡內基音樂廳一樣：練習。」或者如果你喜歡格言，我最喜歡的令人不快的、但有效的建議是「做十倍的努力」。  ↩︎